生物信息学中多序列比对等算法的研究--参考论文文献资料可复制黏贴.pdf

大连理工大学博士学位论文生物信息学中多序列比对等算法的研究姓名：张敏申请学位级别：博士专业：计算机应用指导教师：迟忠先20050501摘要“海量”的生物数据为生命科学研究提供了广阔前景，同时也对现有的生物数据处理能力提出了严峻挑战。如何从浩如姻海的生物序列数据中挖掘出有价值的生物信息，以获取基因、蛋白质结构、功能和进化等理性知识是生物信息学研究的主要目的。多序列比对和系统发育分析是生物信息学的重要研究领域，而提高分歧较大序列的多序列比对准确率和重构合理的全基因组系统发育树是该领域的主要研究课题，本文对此进行了深入研究和探讨，主要研究成果如下：本文深入、细致地研究了当今国际上各种多序列比对算法，系统地阐述了最具代表性的渐进比对算法c l u s t a l w 、t - c o f l e e 和d i a l i g n ，以及迭代比对算法p r r p 、m u l t a l i n和m u s c l e ，并具体地分析了各算法的优缺点。c l u s t a l w 是目前国际上使用最为广泛且有效的多序列比对程序，但存在着对分歧较大且进化距离非均匀的多序列比对准确率低的问题。针对上述问题，本文借鉴了m u l t a t i g n 算法，综合了迭代比对和渐进比对策略的优点，提出了一种新的迭代渐进多序列比对算法i p m s a 。并以国际通用的多序列比对基准数据库b a l i b a s e 中一千多条蛋白质序列构成的1 4 2 组参考多序列比对数据集为测试数据，将本算法同c l u s t a l w 和m u l a l i g n 进行了比较研究。研究结果表明，本算法能有效地提高多序列比对的准确性，其准确率分别比m u l t a l i n 和c l u s t a l w 高出1 9 6 3 1 13 1 。针对以往渐进比对算法中距离矩阵基于两序列比对来构建，而存在着无法反映序列间的结构信息差异，以及人为设定参数，难以客观、有效地反映序列间进化距离的问题，本文引入一种新的计算序列间迸化距离的信息理论方法f d o d 方法。该方法通过序列中相邻子序列分布( 完全信息集c i s ) 来描述序列，充分考虑到序列中相邻字符的相关性，从序列中可以提取有关组分以及结构等更多信息；同时，以子序列分布差异度量函数f d o d 计算序列距离，该函数计算简单、快速，且不需要人为设置参数，因此，能够更客观、有效地计算序列间的进化距离。此外，利用动态规划比对算法计算距离矩阵的时间复杂度为o ( n 2 r ) ，而利用信息差异度量函数计算距离矩阵的时间复杂度为o ( n 2 l ) ，所以采用信息差异度量方法计算距离矩阵可以降低相应比对算法的时间复杂度。本文首次将利用信息熵度量序列间进化距离的f d o d 方法引入到多序列比对算法研究中，提出一种新的基于i p m s a 和信息差异度量的多序列比对算法m s a i d 。该算法包含两部分：基于信息差异度量的渐进多序列比对算法m s a i d l 和迭代渐进多序列比对算法m s a i d 。以基准多序列比对数据库b a l i b a s e 中1 4 2 组参考比对作为测试数据集，与当前国际上著名的多序列比对算法c l u s t a l w 、d i a l i g n 、p r r p 、t - c o f f e e和m u s c l e 进行了比较研究。比较结果表明：m s a i d 显著地提高了比对的准确率，特别是对于没有大量空位插失的序列比对，其准确率为最高，分别比d i a l i g n 、c l u s t a l w 、t - c o f f e e 、p r r p 和m u s c l e 高2 29 、9 5 、9 1 、6 6 和28 。对于要求速度的比对应用，m s a i d 一1 是一个理想的选择，其准确率同c l u s t a l w 相比有一定程度的提高( 除了包含大量n c 终端扩展序列的第四类参考比对) ，同时降低了算法的时间复杂度。其中：c l u s t a l w 和m s a i d 1 的时间复杂度分别为：o 2 r j + o a r 3 j + o ( n l 2 ) 和o ( n 2l ) + o 圆3 ) + o ( n e ) 。全基因组系统发育分析是目前生物信息学研究热点之一。但是因为存在基因重组现象，使得基因组难以进行全局多序列比对，导致以往常用的基于多序列比对的重构系统发育树方法很难实现。为此本文根据三联体密码子简并性提出一种新的描述d n a 序列的密码子分布向量法，并给出基于信息差异度量计算基因组间进化距离方法。在此基础上提出一个重构全基因组系统发育树方法f n j ，该方法可以用于解决重构全基因组系统发育分析的需求。本文将该算法应用于s a r s 冠状病毒与其他冠状病毒的全基因组比较中，其应用结果表明：该算法能够有效地重构冠状病毒全基因组的系统发育树。本文针对多序列比对算法研究中对创新算法准确性评估的需求，依托创新算法i p m a s 和m s a i d 为基础，整合了多种序列比对软件包，设计并实现了一个基于w i n d o w s操作系统的生物信息学多序列比对算法研究及应用系统。该系统集成了c l u s t a l w 、t - c o f f e e 和m u s c l e 等国际流行的多序列比对程序，提供了多序列比对基准数据库b a l i b a s e ，并具有基于b a l i b a s e 参考比对的多序列比对算法准确性评估功能，能对算法准确性进行比较和分析，同时还提供了序列清洗以及数据文件格式转换等辅助功能。该系统不仅可以为多序列比对算法研究人员提供一个测试算法准确性的检测平台，而且也可以作为理论生物学家进行多序列比对工作的应用平台。关键词：生物信息学；多序列比对：渐进比对算法；迭代比对策略；f d o d 函数系统发育树i ia b s t r a c tt h ea c c u m u l a t i o no fb i o l o g ys e q u e n c ed a t ah a so f f e r e dab r i g h tf u t u r et ol i f es c i e n c e sr e s e a r c h ，b u ta l s oas e v e r ec h a l l e n g et od a t ap r o c e s s i n g i ti st h em a i ng o a lo fb i o i n f o r m a t i c sh o wt om i n ev a l u a b l eb i o l o g yi n f o r m a t i o nf r o mt h ev a s tb i o l o g ys e q u e n c ed a t a ，t ou n d e r s t a n d i n gt h es t r u c t u r e ，f u n c t i o na n de v o l u t i o no fg e n e sa n dp r o t e i n ，t oc o g n i t i o no u r s e l v e si nm o l e c u l el e v e la n dt ob e n e f i th u m a nb e i n gu l t i m a t e l y c o n c e r n i n gt h et w op r o b l e m so fm u l t i p l es e q u e n c ea l i g n m e n ta n dp h y l o g e n e t i ca n a l y s i s ，s o m er e s e a r c h e sa r em a d ei nt h i sd i s s e r t a t i o n t h em a i nw o r ki ss u m m a r i z e da sf o l l o w s ：i nt h i sp a p e r ，w ed e s c r i b ee x i s t i n gm u l t i p l ea l i g n m e n ta l g o r i t h m s ，s u c ha sc l u s t a l w ，t - c o f f e e ，d i a l i g n ，p r r p ，m u l t a l i na n dm u s c l e ，a n de x p o s et h ep o t e n t i a ls t r e n g t h sa n dw e a k n e s s e so ft h em o s tw i d e l yu s e dm u l t i p l ea l i g n m e n tp a c k a g e s c l u s t a l wi sam o s tw i d e l yu s e dm u l t i p l es e q u e n c ea l i g n m e n tp r o g r a m c o n s i d e r i n gi t sa c c u r a c yi sl o w e rt od i s t a n t l yr e l a t e ds e q u e n c e s ，r e f e rt om u l t a l i g n ，an e wi t e r a t i v e l yp r o g r e s s i v em u l t i p l ea l i g n m e n ta l g o r i t h mi p m s ai sd e v e l o p e d i no r d e rt ot e s tt h ea c c u r a c yo ft h ea l g o r i t h m ，i p m s ai st e s t e da n dc o m p a r e dw i t hc l u s t a l wa n dm u l t a l i g nb yu s i n gt h eb a l i b a s ed a t a b a s eo fm u l t i p l es e q u e n c ea l i g n m e n t t h er e s u l t so ft e s t i n gi n d i c a t et h a tt h ea c c u r a c yo fi p m s aa l i g n m e n ti s3 1 a n d19 6 m o r et h a nc l u s t a l wa n dm u l t a l i g nr e s p e c t i v e l y c o n s i d e r i n gt h ed i s t a n c em a t r i xb a s e do np a i r w i s ea l i g n m e n tc a n n o to b j e c t i v e l ya n de f f e c t i v e l yc a l c u l a t et h ee v o l u t i o nd i s t a n c e ，an e wf d o dm e t h o db a s e do ni n f o r m a t i o nt h e o r yi si n t r o d u c e d t h i sm e t h o dd e s c r i b e ss e q u e n c eb yt h ed i s t r i b u t i n go fs u b s e q u e n c e ，a n dc a l c u l a t e st h ee v o l u t i o nd i s t a n c eb yi n f o r m a t i o nd i s c r e p a n c y i ti ss i m p l e ，q u i c k ，o b j e c t i v ea n de f f e c t i v e f u r t h e r m o r e ，t h et i m ec o m p l e x i t yo ft w om e t h o d sa r eo ( n 2 r 、a n do ( n 2 三) r e s p e c t i v e l y t h ef d o dm e t h o di si n t r o d u c e dt h em u l t i p l es e q u e n c ea l i g n m e n ta l g o r i t h mr e s e a r c hf o rt h ef i r s tt i m e ，a n dan e wm u l t i p l es e q u e n c ea l i g n m e n ta l g o r i t h mm s a i db a s e do nam e a s u r eo fi n f o r m a t i o nd i s c r e p a n c ya n di p m s ai sd e v e l o p e d m s a i dh a st w op o r t i o n s ：m s a i d - 1a n dm s a i d m s a i d 一1a n dm s a i da r et e s t e da n dc o m p a r e dw i t ho t h e rp r i o rm e t h o d sb yu s i n gr e f e r e n c ea l i g n m e n t so fb a l i b a s e f o rt h ea l i g n m e n t sw i t hn ol a r g en c - t e r m i n a le x t e n s i o no ri n t e r n a li n s e r t i o n sm s a i dr e c e i v e dt h et o do v e r a l la v e r a g e t h ep h y l o g e n e t i ca n a l y s i so fg e n o m ei so n eo fb i o i n f o r m a t i c sr e s e a r c hf i e l d s i ti sh a r dt or e b u i l dp h y l o g e n e t i ct r e eb a s e do nm u l t i p l es e q u e n c ea l i g n m e n tb e c a u s eo ft h ei i ip h e n o m e n ao fg e n er e c o m b i n e an e wd e s c r i b ed n as e q u e n c em e t h o db a s e do nc o d o ni sd e v e l o p e da n dt h ee v o l u t i o nd i s t a n c ei sc a l c u l a t e db a s e do nu s i n gf d o d an e wm e t h o df n jo fr e b u i l dg e n o m ep h y l o g e n e t i ct r e ei sd e v e l o p e d ap h y l o g e n e t i ct r e eo fs a r s c o ya n do t h e rc o r o n av i r u s e si sr e b u i l tw i t hf n jm e t h o d t h er e s u l to fa p p l i c a t i o ns h o w st h a tt h em e t h o dc a nr e b u i l dap h y l o g e n e t i ct r e ee f f e c t i v e l y w ed e s i g nab i o i n f o r m a t i c sm u l t i p l es e q u e n c ea l i g n m e n ta l g o r i t h mr e s e a r c hs y s t e m t h es y s t e mi n c l u d e ss o m es e q u e n c ea n a l y s i ss o f t w a r e ，s u c ha sc l u s t n w ，t - c o f f e ea n dm u s c l ea n ds oo n ，p r o v i d e sm u l t i p l es e q u e n c ea l i g n m e n td a t a b a s eb a l i b a s e i tc a r te v a l u a t et h ea c c u r a c yo fam u l t i p l es e q u e n c ea l i g n m e n ta l g o r r h m ，c o m p a r ea n da n a l y s i st h e s ea l g o r i t h m s t h i si sat e s ts y s t e mf o rm u l t i p l es e q u e n c ea l i g n m e n ta l g o r i t h mr e s e a r c ha n da na p p l i c a t i o nf o rm u l t i p l es e q u e n c ea l i g n m e n t k e y w o r d s ：b i o i n f o r m a t i c s ；m u l t i p l es e q u e n c ea l i g n m e n t ；p r o g r e s s i v ea l i g n m e n ta l g o r i t h m ；i t e r a t i v ea l i g n m e n ts t r a t e g y ；p h y l o g e n e t i ct r e e ；f d o df u n c t i o n1 1 引言第一章绪论二十世纪九十年代，随着人类基因组计划( h u m a ng e n o m ep r o j e c t ) 的顺利实施，以及多种模式生物基因组测序工作的顺利展开，核酸和蛋白质等生物数据的相关信息出现了爆炸性增长，迫切需要对海量生物信息迸行处理。自1 9 9 5 年科学家破译了全长为1 8 0 万核苷酸的嗜血流感杆菌基因组以来，到目前已有大约6 0 个微生物和若干真核生物，如：酵母、线虫、果蝇、拟南芥的完整基因组完成测序。至2 0 0 1 年的春天，科学家又公布了人类基因组的绝大部分序列，即：人类基因组的工作草图。这些成就意味着基因组的研究将全面进入信息提取和数据分析的崭新阶段。根据国际数据库的统计，1 9 9 9 年1 2 月d n a 碱基数目为3 0 亿，2 0 0 0 年4 月d n a 碱基数目是6 0 亿，现在这数目己达1 4 0 亿，大约每1 4 个月翻一番。同时，电子计算机芯片对于数字处理能力的增长也相当于每1 8 个月翻一番。因此，计算机能够有效地管理和运行海量数据。但是，更为本质的原因是基因级数据的复杂性。所谓某种生物的基因组就是指该生物所有遗传物质的总和。生物的遗传物质是一类称为脱氧核糖核酸( d n a ) 的生物大分子，它是由4 种核苷酸串接起来组成的，通常用字符a 、t 、g 、c 代表。通俗她说，生物的遗传密码就是这4 个字符连接起来的线状长链。这种链往往很长，比如：人的遗传密码就含有3 2 亿个字符，将它们堆起来就构成了一部1 0 0 多万页、每页有3 0 0 0字符的“天书”。这本“天书”包含了人体的结构和功能以及生命活动过程的大量信息，却仅仅由4 个字符组成，既无词法，又无句法，还没有标点符号，看起来每一页都是相似的。如何读懂它是个极大的难题。基因组研究最终是要把生物学问题转化成对数字符号的处理问题。要解决这样的问题就必须发展新的分析理论、方法、技术、工具，就必须依赖计算机的信息处理。为此，生物数据分析对数据处理工作提出了前所未有的要求。生物信息学就是在人类基因组计划推动下产生的一门新兴交叉学科，它综合了分子生物学、数学和计算机等学科的理论和方法，对这些“海量”生物数据所包含的生物意义进行分析、阐明和理解。美国人类基因组计划实施五年后的总结报告中，对生物信息学作了如下定义：生物信息学是一门新兴的交叉学科，它以核酸、蛋白质等生物大分子为主要研究对象；以数学、物理、化学等自然科学和信息科学、计算机科学等工程科学为主要手段；以计算机硬件、软件和计算机网络为主要工具；对生物大分子数据进行存储、管大连理工大学博士学位论文生物信息学中多序列比对等算法的研究理、注释、加工，以达到阐明和理解大量数据所蕴含的生物学意义为目的；并通过对序列和结构数据及其相关文献的查询、搜索、比较、分析，从中获取基因编码、基因调控、代谢途径、核酸和蛋白质结构功能及其相互关系等理性知识。在大量信息和知识的基础上，探索生命起源、生物进化以及细胞、器官和个体的发生、发育、病变、衰亡等生命科学中重大问题，发现它们的基本规律和时空联系( 钟扬等，2 0 0 2 ) 。生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说就是从核酸和蛋白质序列出发，分析序列中表达结构、功能和进化的生物信息( 史忠植，2 0 0 2 ) 。研究内容主要包括序列比对、分子进化和比较基因组学、蛋白质结构预测、计算机辅助基因识别、基因芯片设计、基于结构的药物分子设计等。其中序列比对是生物信息学研究中最基本、最关键的问题。生物信息学中，对各种生物大分子的一级结构( 即序列) 进行分析是一件最基本的工作，为叙述简便，下面将组成d n a 的碱基，以及组成蛋白质的氨基酸统称为残基( r e s i d u e ) 。比较未知序列同已知序列的相似性是分子生物学的主要研究手段，为研究这些生物大分子在结构、功能以及进化上的联系提供了重要的参考依据。分子生物学家在研究一个新序列时，通常想知道它与结构或功能已知的序列之间的关系，并以此推断新序列的结构和功能，最后通过实验手段来验证这些推断。为此，要将所有相关序列并列排在一起，希望不同序列中的同源残基能排在同一列上的，以确定这些序歹之间的相似区域。这是理论分析方法中最关键的一步。对于非常相似的序列( 如相似度大于9 5 ) ，这种比较可以通过肉限来完成，但是随着相钕性的降低，以及要比较的序列个数的增多，序列相似性比较的难度将随之加大。对于蛋白质序列中氨基酸同性水平低至大约2 5 时，其相似性研究仍具有生物意义，但此对的相似性比较研究需求助于计算算法。在生物信息学中常使用序列比对( s e q u e n c e a l i g n m e n t ) 方法来完成这一相似性比较研究。由此可见，序列比对特别是多序列比对算法研究在生物信息学的理论研究中具有极其重要的理论意义和实用价值。序列比对问题根据同对进行比对的序列数目分为双序列比对( p a i r - w i s es e q u e n c ea l i g m n e n t ) 和多序列比对( m u l t i p l es e q u e n c ea l i g n m e n t ) 。双序列比对有比较成熟的动态规划算法，而多序列比对目前还没有快速两又十分有效豹方法。一般来说，评价生物序列比对算法的标准有两个：一为算法的运算速度，二为获得最佳比对结果的敏感性( s e n s i t i v e ) 或准确性( a c c u r a c y ) 。人们虽已提出众多的多序列比对算法，但由于阅题自身的计算复杂性，它还尚未得到彻底解决，是生物信息学中一个非常重要且具有挑战性的研究课题。分子进化和比较基因组学是生物信息学研究的另一个前沿课题，主要是利用不同物种中同一种基因序列的异周来研究生物的系统发育( 进化) ，重构系统发育树( 进化树) 。近年来由于较多模式生物基因组测序任务的完成，为从整个基因组的角度来研究第一章绪论分子系统发育提供了条件。重构完整基因组的系统发育树需要新的思路和方法。本文针对当前国际上多序列比对算法进行了细致分析和深入研究，将提高多序列比对的准确率作为本文的主要研究目标，首次将信息熵理论引入到多序列比对算法研究中，综合渐进比对和迭代比对策略的优点提出了多序列比对算法i p m s a 和m s a i d 。以多序列比对数据库b a i i b a s e 中的i 千多条蛋自质序列作为测试数据，并与c l u s t a l w 、d i a l i g n 、p r r p 、t c o f f e e 和m u s c l e 等多序列比对算法做了比较研究，比较结果表明i p m s a 可以有效地提高比对的准确率，而m s a i d 则显著地提高了比对的准确率，特别是对于没有大量空位插，失的序列比对，m a s i d 在这个测试集上可以达到最好的比对准确率。同时，我们针对分子进化和比较基因组所提出的新闯题进行了探讨，并在信息理论的基础上提出一个重构全基因组系统发育树算法f n j 。该算法能够有效地重构完全基因组的系统发育树。1 2 分子生物学概论从信息学的角度来看，生物分子是生物信息的载体。生命的最基本信息都存储在d n a 四种字符组成的序列中。遗传信息从d n a 序列向蛋白质序列的传递是人类已经基本了解的第一部遗传密码，而有人将蛋白质序列到蛋白质结构的关系称为第二部遗传密码( 邹承鲁，1 9 9 7 ) 。第一部遗传密码己被破译，但密码究竟处于d n a 序列的哪些区域还没有全面了解。至于第二部密码，则更是知之甚少。无论是第一部遗传密码，还是第二部遗传密码，都隐藏在生物分子之中。1 2 1 核酸、蛋白质和遗传信息脱氧核糖核酸d n a ( d e o x y r i b o n u c l e i ca c i d ) 大分子是由四种核苷酸聚合成的、高度有序的一维高分子链，每一个核苷酸由一个磷酸、个脱氧核糖以及一个碱基组成( 碱基共有4 种，分别是腺嘌岭a ，鸟嘌呤g ，胞嘧睫c 和胸腺嘧啶t ) ( 阎隆飞，1 9 9 7 ) 。遗传信息就编码在这些核苷酸的不同排列次序上。d n a 分子由两条互相平行的脱氧核替酸长链盘绕而成，呈双螺旋结构，这种双链结构依靠嘌呤和嘧啶之间的氢键连在一起，a 和t 配对，c 和g 配对，这样配对的一对碱基称为一个碱基对( b p ) 。基因组的大小通常使用碱基对的数量来表示：譬如，人类基因组包含大约3 0 亿个碱基对。d n a 结构见图1 1 。大连理工大学博士学位论文生物信息学中多序列比对等算法的研究图1 1 ad n a 平面结构图f i g u r e1 1ad n a p l a n es t r u c t u r ef i g u r ebd n a 双螺旋立体结构图bd n ad o u b l eh e l i xs o l i ds t r u c t u r ef i g t v e碱基间配对的特异性是d n a 精确复制的基础。在d n a 复制过程中。碱基之间的氢键首先断裂，双螺旋解旋分开，游离的核管酸分别以解旋的两条单链作为模板，严格按照碱基互补配对原则，即a 和t 配对，g 和c 配对，合成两条新的d n a 序列( 图1 2 ) 。这种严格的互补配对原则保证了新链是父链的一个精确拷贝。尽可能地降低了发生复制差错( 基因突变) 的危险( 这种突变可能会极大地改变生物体自身或后代的性状) 。图1 2d n a 复制过程f i g u r e1 , 2t h ep r o g r e s so fd n ar e p r o d u c e细胞分子中还有另外一种核酸r n a ( r i b o n u c l e i c a c i d ) 能够携带遗传信息。r n a和d n a 的相同之处在于其碱基也具有配对能力，但其使用碱基尿嘧啶u 来代替d n a中的胸腺嘧啶t ，即：在r n a 中腺嘌呤a 和尿嘧啶u 配对，鸟嘌呤g 和胞嘧啶c 配对。信使r n a ( m r n a ) 是一种r n a 分子，它的作用是：携带来自于d n a 的遗传信息到核糖体，并最终转录到蛋白质中。蛋白质( p r o t e i n ) 是一种复杂的有机生物大分子，是构成生物体的最直接的元素，它们是生命活动的实际执行者，参与基因表达的调节，以及细胞中氧化还原反应、电子传递、神经传递、学习记忆等重要生命过程，生物体之间的差异是直接由蛋白质的不同所造成的。第一章绪论表112 0 种氨基酸名称及字母符号t a b l e1 1t h en a m e sa n ds y m b o l so f 2 0a m i n oa c i d s氨基酸( a m i n oa c i d s ) 是蛋白质的基本组成单位。从细菌到人类，所有蛋白质都由2 0 种标准氨基酸组成。氨基酸聚合成大分子时，相邻的氨基和羧基缩水形成肽键。蛋白质就是由一个个的氨基酸首尾以肽键相连的链状分子。可以像描述d n a 分子一样用一条序列来描述蛋白质分子，序列上的元素就是氨基酸的名称。氨基酸有三字母和单字母两套符号，前者便于记忆，后者便于计算机处理。表1 1 中给出由i u b 和i u p a c共同制定的氨基酸标准符号( 郝柏林张淑誉，2 0 0 0 ) 。核酸( d n a 和r n a ) 和蛋白质是生物机体的两类最基本的生物大分子。它们都属于信息分子，但d n a 是遗传信息的原初载体，蛋白质是遗传信息的体现者。或者说，d n a 在机体中代表信息，蛋白质代表功能，但两者是相互依存的。蛋白质的功能是遗传信息规定的，而遗传信息的表达又依赖蛋白质的参与。大连理工大学博士学位论文生物信息学中多序列比对等算法的研究1 2 2 中心法则、遗传密码和变异d n a 双螺旋是遗传信息的携带者，它在一定条件下可以准确地自我复制。遗传信息只能通过最终的蛋白质产物来体现或表达生物结构和功能。d n a 的碱基排列顺序决定了蛋自质的氨基酸排列顺序，但d n a 信息并不是直接转化为蛋白质信息的，生物细胞内遗传信息的传递是分两步进行的。第一步是以d n a 为模板，将信息“转录”到单股的信使r n a ，即m r n a 链上。第二步是以m r n a 为模板合成蛋白质。遗传信息由m r n a 的碱基序列转变为蛋白质的氨基酸序列，这个过程叫翻译( t r a n s l a t i o n ) 。这种遗传信息传递方式是由d n a 双螺旋结构的发现者之f r a n c i s c r i c k 在事实尚不充分的1 9 5 7 年提出，后来被众多实验事实所证实和补充，成为分子生物学的中心法则( c e n t r a ld o g m a ) ( 图l3 ) 。d n a 。曼! l ，d n ai 转录c d n a功能反转录相互作用m r n al 翻译蛋白质l 折叠结构图1 3 分子生物学的中心法则f i g u r e1 3t h ec e n t e rr u l eo f m o l e c u l eb i o l o g yd n a 和蛋白质都是由重复单元组成的线性多聚体，4 种核苷酸组成的d n a 序列编码并存储了遗传信息，而d n a 复制则是遗传信息传递的分子机理。与此相比较，在细胞中真正执行功能的是蛋白质。因此，需要有一种机制，使得d n a 序列能够将4 种核苷酸的编码信息转化为2 0 种氨基酸编码的蛋白质序列。这是遗传信息得以表达的至关重要的一步，这一步转化的分子机理就是翻译。在翻译过程中，d n a 的编码序列首先通过转录合成m r n a ：在m r n a 中，每3 个核苷酸翻译成蛋白质中的个特定的氨基酸。称这3 个核苷酸为遗传密码或三联体密码( t r i p l e tc o d e ) ，每个三联码称为密码子( c o d o n ) 。但4 种核苷酸的所有三联体组合关有4 3 = 6 4 稀，而不同的蛋白质只有2 0种，因此，一定是几种三联体对应一个氨基酸，这种现象称为遗传密码的简并性( d e g e n e r a c y ) 。表1 2 按转录后的m r n a 给出通用的三联体密码，即t 已换成u 。6第一章绪论表1 2 通用遗传密码表t a b l e1 2h e r e d i t yc o d e s【第一密码第二密码第三密码ucagu u u l 砌p c ，u 叫a c u p 裟 劬ucau u cu c c- 曲a g a j 。终u g g 却。终止guu u a l ，u c au u g 三e “u c gc u uc c u c a u l h i so o uuc 比矗“嚣。c a cjc g cc。”删a c g a- a v gacc c g c a g 】c g ggc 己删c u ga u u la c u l倒u l 加们u l 脚ua彳 肌们c i 砌创c j们c jca彳删ia c 州g l 。州a a 。伽z g 洲g j a u gm e ta c ga g g 船gg u u g c u 洲u l 胁g g 【，ugg 叼l 砌，cm sg 敲 jg g cg 砂cg u ag c ag “l g mg 例ag u g g c gg a gg g gg其中，6 4 个密码子( c o d o n ) 中有三个终止密码子u a a 、u a g 和u g a ，其余6 1个密码子编码2 0 种氨基酸，因此有些氨基酸有多种编码( 简并) ：三种氨基酸有6 重简并编码：亮氨酸( l ) 、丝氨酸( s ) 和精氨酸( r ) ；五种氨基酸有4 重简并编码：缬氨酸( v ) 、脯氨酸( p ) 、丙氨酸( a ) 、甘氨酸( g ) 和苏氨酸( t ) ：有3 重简并编码的是异亮氨酸( i ) 和终止密码子；有9 种氨基酸有2 重简并编码：苯丙氢酸( f ) 、酪氨酸( y ) 、组氨酸( h ) 、谷氨酰胺( q ) 、天冬酰胺( n ) 、赖氨酸( k ) 、天冬氨酸( d ) 、谷氨酸( e ) 和半光氨酸( c ) ；只有甲硫氨酸( m ) 和色氨酸( w ) 是单重编码。尽管d n a 的复制是按着碱基配对原则严格进行的，但是在复制过程中仍会产生一些错误。变异是指在进化过程中这些不正确的复制逐渐积累，并遗传给后代，使d n a内容发生局部的改变。可遗传变异有三种来源：基因突变、基因重组、染色体变异，其中基因突变和染色体变异统称为突变。大连理工大学博士学位论文生物信息学中多序列比对等算法的研究突变的种类主要有以下几种：取代( s u b s t i t u t i o n ) ：在进化过程中，d n a 的复制出现错误，导致生物序列中的某一核苷酸发生了改变。取代能否改变蛋白质的序列，取决于其发生的位置。当取代发生在遗传信息编码区时，可能会改变后代蛋白质的序列，插入或删除( i n s e r t i o no rd e l e t i o n ) ：在进化过程中增加或者丢失一个或多个核萤酸，两者常简记为i n d e l 。重排( r e a r r a n g e m e n t ) ：d n a 或蛋白质的一些序列片段在合成过程中，连接的顺序发生了改变。在很多方面对变异的研究是很重要的：遗传的乱序和一些疾病( 例如癌症) 都是由于基因变异造成的。另外变异是造成物种多样性的基本原因之一。1 2 3 系统发育分析自从1 8 5 9 年d a r w i n 的物种起源( o r i g i no fs p e c i e s ) 发表以来，进化论成为人类自然科学和自然哲学发展中的最重大贡献之一。进化论研究的核心是描述生物进化的历史( 重构系统发育树) 和探索进化过程的机制。c = 芸嚣管麓嚣：鼍，图i 4 系统发育树f i g u r el ，4p h y l e g e n e t i ct r e ed a r w i n i a n 的进化理论表明：一切生物都能发生变异，并且至少有一部分变异能够遗传给后代；任何生物产生的生殖细胞或后代数目要远远多于可能存活的个体数目：而在所产生的后代中，那些最具有适应环境条件的有利变异的个体有较大的生存机会，并繁殖后代，从而使有利变异可以世代积累，不利变异被淘汰；在同一个种内，个体之间在结构、习性上越是歧异，则在适应不同环境方面愈是有利，因而将会繁育更多的个体，分布到更广的范围。由此一个种会逐渐演变为若干交种、亚种乃至新种；由于性状分歧和中间类型的绝灭，新种不断产生、旧种不断绝灭，种间差异不断扩大，第一章绪论形成时间、空间上的系统发育树。系统发育树( p h y l o g e n e t i ct r e e ) 是把物种按亲缘关系远近用图形表达而成的树状系统( 图1 4 ) 。经典的进化论研究方法是采用化石证据( f o s s i l ) 、比较形态学证据( c o m p a r a t i v em o r p h o l o g y ) 和比较生理学证据( c o m p a r a t i v e p h y s i o l o g y ) 。自2 0 世纪中叶以来，随着分子生物学的不断发展，进化论的研究也已从性状水平深入到分子水平。分子水平的进化表现为：d n a 及氨基酸序列的演化。这些生物序列具有可比较性，通过比较不同物种的有关序列，可以建立相关序列的演化模型。另外，基因组编码信息与生物形态、性状包含的信息相比，基因组序列包含更多、更复杂的信息结构。在分子系统发育分析( m o l e c u l a rp h y l o g e n e t i c s ) 的研究中，我们可以进行序列比较，研究源于同一祖先d n m 氨基酸序列的两条d n m 氨基酸，考察二者的差异( 进化过程中分子突变的痕迹) 。以累计在d n a 氨基酸分子上的历史信息为基础，研究分子水平的生物进化过程和机制( 图1 5 ) 。通过研究不同生物体的某种蛋白质或核酸分子结构，推断生物进化的历史，来探讨这些生物间的亲缘关系并以发育树的形式表达出来。图1 5 分子水平的生物进化过程和机制f i g u r e1 5 t h eb i o l o g i ce v o l u t i o n a lp r o g r e s sa n dm e c h a n i s mi nm o l e c u l el e v e r1 3 序列比对方法及多序列比对算法研究进展比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。在生物信息学研究中，比较多个生物序列相似性的任务是由序列比对来完成的。序列比对的理论基础是进化学说。许多生物学的事实表明：不同的核酸或蛋白质序列可能源于同一原始序列，经过序列内残基的取代、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。在残基一残基比对中，可以明显看到序列中某些残基比其它位置上的残基更保守，这些信息揭示了这些保守位a _ k n 残基对序列的结构和功能是至关重要的。因此，序列比对可用于蛋白质的功能域识别、二级结构预测，基因识别，以及分子系统发育分析等方面的研究。9大连理工大学博士学位论文生物信息学中多序列比对等算_ ；去的研究序列比对根据同时进行比对的序列数目分为双序列比对( p a i r w i s es e q u e n c ea l i g n m e n t ) 和多序列比对( m u l t i p l es e q u e n c ea l i g n m e n t ) 。序列比对从比对范围考虑也可分为全局比对( g l o b a la l i g n m e n t ) 和局部比对( 1 0 c a ia l i g n m e n t ) ，全局比对考虑序列的全局相似性，局部比对考虑序列片段之间的相似性。双序列比对的典型方法是动态规划比对算法( n e e d l e m a n & w u n s e h ，1 9 7 0 ：s m i t h & w a t e r m a n ，1 9 8 1 ) ，它是序列比对问题的理论基础；另一方面，双序列比对常用于生物序列的数据库搜索，如：f a s t a ( l i i ) m a i l p e a r s o n ，1 9 8 5 ；p e a r s o n & l i p m a n ，1 9 8 8 ) 和b l a s t ( a l t s c h u la le t ，1 9 9 0 ；a l t s c h u la le t ，1 9 9 7 ) 。通过序列比较，检测新序列与数据库中已知结构和功能序列之间的相似程度，并以某种可信度获得新序列的结构和功能信息。而对于构成家族的若干序列来说，为了系统发育分析或是推断家族序列的特征，要建立多个序列比对。由于多序列比对可以提高序列比对的信噪比，因此在阐明一组相关序列的重要生物学模式方面起着相当重要的作用。全局比对是从头到尾全程比较考虑序列的整体相似性。全局多序列比对可以鉴别或证明新序列与已有序列家族的同源性；帮助预测新蛋白质序列的二级和三级结构；是进行分子进化分析的重要前提。局部比对考虑序列部分区域的相似性。局域比对的生物学基础是：蛋白质功能位点是由较短的序列片段组成，尽管在序列的其它部位可能有插入、删除或突变，但是这些序列片段具有相当大的保守性。此时，局域比对往往比全局比对具有更高的灵敏度，其结果更具生物学意义。局域多序列比对可以用来刻画蛋白质家族和超家族。自从f i t c h ( 1 9 6 6 ) 提出基于统计方法、利用计算机来自动地比较蛋白质序列以取代人眼的观察比较以来，国际上对多序列比对的研究已有几十年的历史。序列比对的点阵图法( g i b b s & m c i n t y r e ，1 9 7 0 ) 是一弛最简单且容易实现的序列相似性比较方法。该方法是通过将一条序列排在上首，另一条序列纵列在左端，两个序列在任何位置上若出现相