（计算机软件与理论专业论文）基于最大权值路径算法的dna多序列比对方法.pdf

摘要 序硇眈对跫璐我生秘信怠学中令豢基本豹磅究课瑟。逶过多亭到琵对，可 以预测鞭序列的结构邪功能，分析序列之闯的同源关系，以及进行系统发育分析。 目前还没有一个最佳的多序列比对算法，本文提出一个新的算法m w p a l i g n 解决 全竭翻藩帮熬多亭歹l 毙怼淫题。 本文酋先贪绍了序列比对涉及酾基本问题；空位霭分，臀换矩阵和比对结粜评 价标准。然后研究了双序列精确比对算法：动态规戈4 算法，劳具体实现了基于动 态规划方法豹双序列全局茅丑竭部比对算法。褒多痔到比对巾，主要对鏊予灏进方 法鞠逡静多窿甍魄鼹算法c l u s t a l w 帮基予圈涂鹣多序列魄对方法p o a 逡行了深入 的分誊斥。主要研究敬得的成果如下： 通过对圈论中的d eb r u i j n 圈和基于欧拉路径算法的序列装配方法进行了深 天磷究分析，本文捷 噩了纂予嫩太钗蕊臻径葵法的垒弱d 挂a 多序列 e 对方法。对 这个方法迸行实验分析，并和现有算法进行了比较，其时问复杂度优予观有方法， 并且对于大量变异率低于5 2 的序列，比对继果优于c l u s t a l w ，b c o 虢e 和 i m m t ，爨弛证明本算法是有效盼多序列全鼹毙对算法。 逸过对弱都魄对中静d e e l u m 翻n g 算法鞠溶裣分布在序弼既对结聚浮估中静 应羽进行了深入研究，对上述最大权值路径算法进行了扩艟，提出了熬于最大权 值路径算法的局部d n a 多序列比对方法，通过对模拟序列应用本算法，结果证明 了本蘩法戆是畜效黪多澎嚣局释跑黠雾法。 本文的研究内容是生物信慰学中创新的多序列比对冀法，经过具体躲实验分 析及比较，其生物敏感性及运辩效率都较现有方法有掰提高。 关键谣：生物缮惠学多序列跑靖调和稼副d e8 r u l j n 窝最丈校缓路径滚 松分张 a b s t r a c t s e q u e n c ea _ l i 弘m e n t i st h em o s tc o m m o n h d 咖e n t a ls u b j e c ti ni n o d e m b i o i i l f b h n a t i c s t h r o u 曲s e q u e n c ea l i g m e n t ，、ec a np r e d i c tt l l es 扛u c t u r ea 1 1 df h c t i o n o fn e ws e q u e n c e ，a 1 1 a l y s i st h ee v 0 1 u 廿o n a r yl i n k a g eo fs e q u e n c e s ，d op h y l o g e n e t i c a n a l y s i s s t i l lm e r ei sn o ta no p t i m a la l g o r i t l l mo fm m t i p l es e q u e n c ea l i g m e n t s w e p t e s e 毗an o v e la p p r o a c hc a l l e dm w p a l i g n t od o 醇o b a la n dl o c a lm u h i p l ea l i g n 础e n t 6 wd n a s e q u e n c e s f i r s t ly ，w ed e s c 曲em eb a s i cp r o b l e ma b o u ts e q u c n c ea l i g m e n tl i k e ：g 印p e n a l t y ， s u b s t i t m i o nm a t r i xa n ds t a l l d a r do fa s s e s s i n ga l i g m e n tr c s u l t s e c o n d ly ，m ea c c u r a t e m d h o dc a l l e dd y n a m i cp t o g r a i n m i n ga l g o r i m mo fp a i r w i s ea l i g 嘲e mi ss t l m i e da n d i m p l e m e n t e di nm ef o mo f9 1 0 b a la 1 1 d1 0 c a l f o r 血e 舢m p i es e q u e n c ea l i 鲫e m ，w e m a i n l y 咖d ya n dd e s c r i b em ea l g o r i t l l i nc l u s t a l w 砒l i c hi sb a s e do nt h ep r o g r e s s i v e a 王i g n m e n ts t r a t e g ya 1 1 dt h ep o aa l g o r i t l l mw h i c hi sb a s e do nt h eg r 印hn l e m o d t h e m a i np r o 捌o nc a nb eb r i e n ys u m m 甜i z e da sf o l l o w s ： n l r o u 曲a n a l y s i s i n gm es 廿u c t u r eo fd eb r u 匐ng r a p ha n dt h ed n af r a g m e n t a s s e m b l ya l g o r i m mb a s e do nt l e e l l l e r i a np a ma p p r o a c h ，、v ep r o p o s e dam a x i m 啪 w e i 曲t c dp a ma p p r o a c ht og l o b a 王m u h i p l ea l i g n m e n tf o rd n as e q u e n c e s w c i m p l e m e n t e dt h i sa _ i g o r i 也ma n dc o m p a r e di tw i mc u r r e n d yu s e dm c t m d ，也et e s u l t s h o wt l l a t0 1 l ra l g o r i m mg e tal o w e rc o m p u t a t i o ns p e e d ，a 1 1 df o rl a r g en 啪b e ro f s e q u e n c e s 、v i t hl o w c rm u t a t i o nr a t et l l a l l5 2 ，m w p a l i g ng e n e r 砒e sb e t t e ra l i g m e n t r e s u l t sa sc o m p a r e dt oc l u s t a l w ；t _ c o f r e e 锄dh m m 工 t h r o u g hr e s e a r c h i n gt h ed e c h l m p 证ga i g o o f p a i r w i s ea l i g 工l m e n ta n d 也e a p p l i c a t i o no ft 1 1 ep o i s s o nd i s t r i b u t i o ni na s s e s s i n gs e q u e n c ea l i g m e n tr e s u l t ，w e e x t c n d0 1 l rm a x i m u m w e i 曲t e dp a t h 印p r o a c h ，a n dp r o p o s e dam a ) ( 油啪w e i g h t e dp a n l a p p r o a c ht ol o c a lm u l t i p l ea l i g n m e n tf o rd n as e q u e n c e s w e 印p l yt h i sl o c a lm e m o dt o 也es i m u l a t e ds c q l l e n c e s ，也er e s u l ts h o wt h a to u rm 酣m di sa f e a s i b l el o c a lm u m d l e s e q u e n c ea l i g n m e ma l g o r i t l l m t h er e s e a r c hc o n t c m sa r ei n n o v a t e d a l g o r i t l l i n s o fs e q u e n c e a l i g 珈：i l e m i n b i o i 州b n l l a t i c s t h e s e a l g o r i m m s 村ea d v a l l c e dm o r ee v i d e n t l vm a nt r a d i t i o n a l a l g o r i m m si nb i o l o 斟s e 璐i t i v 姆a n dc o m 】州n ge 伍c i e n c y k e y w o r d ：b i o i n f b r m a t i c s s e q u e n c ea l i g n m e n t c o n s e n s u ss e q u e n c ed eb r u i j n g r a p h m a x i m u mw e i g h t e dp a t hp o i s s o nd i s t r i b 挂t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书面使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的晓明并表示丁谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：当坌鱼日期竺! 乏丝 关于论文使用授权的说明 本人完全了解诬安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 高校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保暂的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：西坌堡日期型f 导师签名 蕴生2 l日期2 “卅 第一章绪论 第一章绪论 l + i 弓| 言 = 十世纪九十年代，随着人类基因组计划( h u m a ng e n o 晡糙p 蛹e c t ) 的顺利实施， 班及多静模式生物鐾毽缰渊穿工律豹簇裁最野，谈酸霹蛋囊蔟等生秘数攒夔霸关 信息出琥了爆炸髅增妖，遍韬霈簧辩海量生物信息进行憝溪。鑫1 9 弼霉科学家破 译了垒长为1 8 0 万榱甘酸的嗜j 衄流杆菌基因缌蛆来，到目前已有大约6 0 个微生物 和若千真孩生物，毅：酵母，线瞧，果蝇，拟南分的完整蘩瓣组完成测黪。至2 0 0 l 每戆嚣天，器学豢又公毒了入类基遴缝静绝六帮分廖蘩，邸：a 类蒸秘缀戆工佟 草图。这些成就意睐着基因组的研究将全面进入信息提取和数据分析的崭新阶段。 根据隔际数据库的统计，1 9 9 9 年1 2 月d n a 碱基数目为3 0 亿，2 0 0 0 年4 月d n a 碱基数蘧是稻钇，强在逮一数瓣澄这i 4 0 多亿。襄薅，嗽予诗冀惑芯片怼予数字 处理能力的增长瞧糟当于每l s 个月骶一番。因貌，诗算枫能够有效煎管理和运行 海量数据。 瞧是，更为举攒豹原因是錾戮组数据的复杂牲。所谓装静生物毂基困缠就是 撩该釜携掰毒蘧嬷锈震蕊葱露。生辏翡遗簧耘爱是一类繇为麓氯菝糖核酸f 溅鼬 的生物犬分子，它怒由4 种核甘酸串接起来组成的，通常用字符a ，t ，g ，c 代 表。通俗的说，生物的遗传密码就是这4 个字符连接起泉的线性长链。这种长链 往簌缀长；毙蠢：入嚣遗传密秘藏含骞3 2 磁令字符，穆它嚣j 罐踅亲裁褥成了一黎 1 0 0 彰万页，每贾离3 0 0 0 字符的“天书”。这本“天书”像禽了a 体的缩构和功能 以及擞命活动过獠的大量信息，却仅仅由4 个字符组成，既无词法叉滗句法，还 没蠢据点耱号，爨怒来每一夏秘楚耦穆敦。皴键读懂它楚个羧丈匏难题。基嚣缀 霹辩滚终是要把娄物学薅题转纯成藏鼗字旃号翡筵理阕麓。要簿决这襻靛瓣蘧蓑 必须擞耀新的分析理论，方法，技术，工具，就必须依靠计算机的信息处理。 为i | ： ：，生物数撂分析对数摊处理工作提出了前所未谢的要求。生物信息学就 曩在炎獒萋交缝诗捌箍囊节产生黪一门囊兴交叉学释，它练含了分予篷耪学，数 学和计算机等拳耕的理论和方法，对这些“海营”生物数据所包含的生物意义进 行分析，阐明和璩懈。美国火搽基因组计划嶷施五年后黼总结报告中，对生物信 息学傺了窝下定义： 宝物售患学魁一门薪兴黪交叉学科，它戳核酸，蛋茸蒲等生赘太分子秀主要 研究对象；以数学，物理，化学等自然科学和信息科学，计算机科学锥工程科学 为主娶手段；以计辣机硬件，敬转和计算机雕络为主要工鼹i 对生物丈分子数据 2 基于最大权值路径算法的d n a 多序列比对方法研究 进行存储，管理，注释，加工，以达到阐明和理解大量数据所蕴涵的生物学意义 为目的；并通过对序列和结构数据及相关文献的查询，搜索，比较，分析，从中 获取基因编码，基因调控，代谢途径，核酸和蛋白质结构功能及相互关系等理性 知识。在大量信息和知识的基础上，探索生命起源，生物进化以及细胞，器官和 个体的发生，发育，病变，衰亡等生命科学中重大问题，发现它们的基本规律和 时空联系。 生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说 就是从核酸和蛋白质序列出发，分析序列中表达结构，功能和进化的生物信息1 2 】。 研究内容主要包括序列比对，分子进化和比较基因组学，蛋白质结构预测，计算 机辅助基因识别，基因芯片设计，基于结构的药物分子设计等。其中序列比对是 生物信息学研究中最基本，最关键的问题。 生物信息学中，对各种生物大分子的一级结构( 即序列) 进行分析是一项最基本 的工作，为叙述方便，下面将组成d n a 的碱基，以及组成蛋白质的氨基酸统称为 残基( r e s i d u e l 。比较未知序列同已知序列的相似性是分子生物学的主要研究手段， 为研究这些生物大分子在结构，功能以及进化上的联系提供了重要的参考依据。 分子生物学家在研究一个新序列时，通常想知道它与结构或功能已知的序列之划 的关系，并以次推断新序列的结构和功能，最后通过实验手段来验证这些推断。 为此，要将所有相关序列并列排在一起，希望不同序列中的同源残基能排在同一 列上，以确定这些序列之间的相似区域。这是理论分析方法中最关键的一步。对 于非常相似的序列( 如相似度大于9 5 ) ，这种比较可以通过肉眼来完成，但是随着 相似性的降低，以及要比较序列条数的增多，序列相似性比较的难度将随之加大。 对于蛋白质序列中氨基酸同一性水平降至大约2 5 时，其相似性研究仍具有生物 意义，但此时的相似性比较研究需要求助于计算算法。在生物信息学中常使用序 列比对( s e q u e n c ea l i g n m e n t ) 方法来完成这一相似性比较研究。由此可见，序列比 对特别是多序列比对算法研究在生物信息学的理论研究中具有极其重要的理论意 义及使用价值。 序列比对问题根据同时进行比对的序列数目分为双序列比对( p a i r w i s e s e q u e n c ea l 培啪e n t ) 和多序列比对( m u l t i p l es e q u e n c ea i i g n m e n t ) 。双序列比对有比较 成熟的动态规划算法，而多序列比对目前还没有快速且十分有效的方法。一般来 说，评价生物序列比对算法的标准有两个：一为算法的运算速度，二为获得最佳 比对结果的敏感性( s e n s i t i v e ) 或准确性( a c c u r a c y ) 。人们虽然已经提出了众多的多序 列比对算法，但由于问题自身的计算复杂性，它还尚未得到彻底解决，所以，序 列比对问题尤其是多序列比对问题已经成为生物信息学中一个非常重要且具有挑 战性的研究课题。 分子进化和比较基因组学是生物信息学研究的另一个前沿课题，主要是利用 第一章绪论 不同物种中同一基因序列的异同来研究生物的系统发育( 进化) ，重构系统发育树 ( 进化树) 。近年来由于较多模式生物基因组测序任务的完成，为从整个基因组的角 度来研究分子发育提供了条件。重构完整基因组的系统发育树需要新的思路和方 法。 1 2 生物信息学研究内容及现状 生物信息学的研究对象主要是d n a 和蛋白质序列；主要任务是分析研究序列 数据中的各种信息，特别是d n a 序列中的遗传及调控信息，研究蛋白质序列与结 构及功能的关系；研究内容【3 】主要包括序列比对、结构比对、蛋白质结构预测、计 算机辅助基因识别、非编码区分析和d n a 语言研究、分子进化和比较基因组学、 序列装配、基于结构的药物设计等。下面主要个研究内容做简要介绍： 序列比对 基本问题是比较两个或两个以上符号序列的相似性或不相似性。序列比对是 生物信息学的基础，非常重要。两个序列的比对有较成熟的动态规划算法，以及 在此基础上编写的比对软件包：b l a s t 和f a s l l a 。这些软件在数据库查询和搜索 中有重要的应用。有时两个序列总体并不很相似，但某些局部片断相似性很高。 s m i 1 一w a t e r i n a n 算法是解决局部比对的好算法，缺点是速度较慢。两条以上序列 的比对目前还缺乏快速而又十分有效的算法，因此众多的启发式算法被提出来以 改进比对结果和比对速度，但都不是十分有效，所以这个领域也就成为生物信息 学中最有挑战性的研究方向，也是本文的研究重点。 结构比对 基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相似性。 蛋白质结构预测 从方法上来看有演绎法和归纳法两种途径。前者主要是从一些基本原理或假 设出发来预测和研究蛋白质的结构和折叠过程。分予力学和分子动力学属这一范 畴。后者主要是从观察和总结己知结构的蛋白质结构规律出发来预测未知蛋白质 的结构。同源模建和指认( t h r e a d i n g ) 方法属于这一范畴。虽然经过3 0 余年的努力， 蛋白结构预测研究现状远远不能满足实际需要。主要的预测包括2 级和3 级结构 预测。 计算机辅助基因识别( 仅指蛋白质编码基因1 基本问题是给定基因组序列后，正确识别基因的范围和在基因组序列中的精 确位置。这是最重要的课题之，而且越来越重要。原核生物计算机辅助基因识 别相对容易些，结果好一些。从具有较多内含子的真核生物基因组序列中正确识 别出起始密码子、剪切位点和终止密码子，是个相当困难的问题，研究现状不能 4 基于最人权值路径算法的d n a 多序列比对方法研究 令人满意，仍有大量的工作要做。经过2 0 余年的努力，提出了数十种算法。 非编码区分析和d n a 语言研究 在人类基因组中，编码部分仅占总序列的3 5 ，其它通常称为“垃圾”d n a ， 其实一点也不是垃圾，只是我们暂时还不知道其重要的功能。分析非编码区d n a 序列需要大胆的想象和崭新的研究思路和方法。d n a 序列作为一种遗传语言，不 仅体现在编码序列之中，而且隐含在非编码序列之中。 分子进化和比较基因组学 早期的工作主要是利用不同物种中同一种基因序列的异同来研究生物的进 化，构建进化树。既可以用d n a 序列也可以用其编码的氨基酸序列来做，甚至于 可通过相关蛋白质的结构比对来研究分子进化。以上研究已经积累了大量的工作。 近年来由于较多模式生物基因组测序任务的完成，为从整个基因组的角度来研究 分子进化提供了条件。可以设想，比较两个或多个完整基因组这一工作需要新的 思路和方法，当然也渴望得到更丰硕的成果。这方面可做的工作是很多的。 序列装配 一般来说，根据现行的测序技术，每次反应只能测出5 0 0 或更多一些残基对 的序列，这就有一个把大量的较短的序列全体构成了重叠群( c o n t 追s ) 。逐步把它们 拼接起来形成序列更长的重叠群，直至得到完整序列的过程称为重叠群装配。拼 接e s t 数据以发现全长新基因也有类似的问题。已经证明，这是一个n p 一完备性 算法问题。 遗传密码的起源 遗传密码为什么是现在这样的? 这一直是一个谜。一种最简单的理论认为， 密码子与氨基酸之间的关系是生物进化历史上一次偶然的事件而造成的，并被固 定在现代生物最后的共同祖先里，一直延续至今。不同于这种“冻结”理论，有 人曾分别提出选择优化、化学和历史等三种学说来解释遗传密码。随着各种生物 基因组测序任务的完成，为研究遗传密码的起源和检验上述理论的真伪提供了新 的素材。 基于结构的药物设计 人类基因组计划的目的之一在于阐明人的约l o 万种蛋白质的结构、功能、相 互作用以及与各种人类疾病之间的关系，寻求各种治疗和预防方法，包括药物治 疗。基于生物大分子结构的药物设计是生物信息学中的极为重要的研究领域。为 了抑制某些酶或蛋白质的活性，在已知其3 级结构的基础上，可以利用分子对接 算法，在计算机上设计抑制剂分子，作为候选药物。这种发现新药物的方法有强 大的生命力，也有着巨大的经济效益。 基因表达谱分析、代谢网络分析、基因芯片设计和蛋白质组学数据分析等， 也逐渐成为生物信息学中新兴的重要研究领域。这里不再赘述。 第一章绪论 统计学，包括多元统计学，是生物信息学的数学基础之一；概率论与随机过 程理论，如近年来兴起的隐马尔可夫链模型( h m m ) ，在生物信息学中有重要应用； 运筹学，如动态规划方法是序列比对的基本方法，最优化理论与算法，在蛋白质 空间结构预测和分子对接研究中有重要应用，拓扑学，这里指几何拓扑，在d n a 超螺旋研究中是重要工具，在多肽链折叠研究中也有应用；函数论，如傅里叶变 换和小波变换等都是生物信息学中的常规工具：信息论，在分子进化、蛋白质结 构预测、序列比对中有重要应用，而人工神经网络方法则用途极为广泛；计算数 学，如常微分方程数值解法是分子动力学的基本工具；群论，在研究遗传密码和 d n a 序列的对称性方面有重要应用；组合数学，在分子进化和基因组序列研究中 十分有用。原则上讲，各种数学理论或多或少或直接或问接都应该在生物学研究 中有各种各样的应用，其中包括生物信息学，这种情况j 下像过去的一、两个世纪， 数学应用于物理学一样。而且，生物信息学的发展，又为数学的发展提供了一个 新的机遇，可能会产生一些新的分支科学。 1 3 本文所做的工作 本文针对当前国际上流行的多序列比对算法进行了细致分析和深入研究。首 先在图论基础上，结合基于欧拉路径算法的序列装配方法，提出了基于最大权值 路径算法的d n a 多序列比对的全局和局部比对方法，并实现了这个方法。最后通 过实验和现有的多序列比对方法进行了比较，验证了本方法的有效性和可行性。 本方法最大的优点就是几乎线性的时间复杂度。 论文内容具体安排如下： 第一章主要介绍序列比对问题的背景知识，序列比对的意义和研究现状，最 后对本文所做工作进行了简要的介绍。 第二章主要介绍序列比对中涉及到的一些基本概念和问题，包括：序列比对 问题的形式化的描述，序列比对中涉及的空位罚分，替换矩阵，评价标准等问题。 然后对序列比对进行分类，详细介绍了每一类比对的问题和现有研究现状，并重 点对多序列比对中的主流算法进行详细介绍。 第三章在对基于欧拉路径算法的序列联配方法和d eb m i n 图进行分析的基 础上，提出了基于最大权值路径算法的全局d n a 多序列比对方法。然后使用模拟 的数据对算法进行了测试，并且和现有的方法进行了比较分析。 第四章对d e c l u m p i n g 算法和泊松分布估计在序列局部比对中的应用进行了 详细的分析，在第三章提出的基于最大权值路径算法的全局d n a 多序列比对方法 的基础上，进一步深化了最大权值路径算法的应用，提出了基于基于最大权值路 径算法的局部d n a 多序列比对方法，并利用模拟序列数据对算法进行了测试分析。 6 基丁虽火权值路径算法的d n a 多序列比对方法研究 向。 第五章对整篇文章进行了总结，分析方法中的不足，并指出了今后的研究方 第二章生物序列比对 第二章生物序列比对 2 1 序列比对概述 比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能 具备的特性。在生物信息学研究中，比较多个相似生物序列的任务是由序列比对 来完成的。序列比对的理论基础是进化学说。许多生物学的事实表明：不同的核 酸或蛋白质序列可能源于同一原始序列，经过序列内残基的取代，残基或序列片 断的缺失，以及序列重组等遗传变异过程分别演化而来。在残基和残基比对中， 可以明显看到序列中某些残基比其它位置上的残基更保守，这些信息揭示了这些 保守位点上的残基对序列的结构和功能是至关重要的。因此，序列比对可用于蛋 白质的功能域识别，二级结构预测，基因识别，以及分子系统发育分析等方面的 研究。 进行序列比对要让人们能够判断两个序列之问是否具有足够的相似性，从而 判定二者之间是否具有同源性。值得注意的是，相似性和同源性虽然在某种程度 上具有一致性，但它们是完全不同的两个概念。相似性是指一种很直接的数量关 系，比如部分相同或相似的百分比或其它一些合适的度量，而同源性是指从一些 数据中推断出的两个基因在进化上曾具有共同祖先的结论，它是质的判断。基因 之间要么同源，要么不同源，绝不象相似性那样具有多或少的数量关系。 由于受到研究进化关系这一目的的影响，大多数比对方法很自然地都希望能 够在某种程度上建立起分子进化的模型。我们通常都假定同源序列是从某一共同 祖先不断进化而来，但事实上，我们无法得知这个祖先序列到底是什么样子，除 非能够从化石中获得它的d n a ，我们所能够做到的只是从现存物种中探求真相。 从祖先序列以来所发生的变化包括变异、插入以及删除。在理想情况下，同源基 因或蛋白质序列在相互比较时，残基之间相互对应，从而使取代的情况很明显地 表现出来。在某些位簧，一个序列中拥有某些残基而另一个序列中缺少这些残基， 表明这些残基是插入到前者或是从后者中丢失的。这些空位在序列比对时用连续 的短线填补。例如下面就是一个简单的双序列比对的例子。 输入序列：s l = a t c g a g c t g g t ，s 2 = a t c g a g c g g t 。 插入空位前两序列匹配如下： s l ：at cgag1 ctggt ii il i llil s 2 ：atcg agcg gt 基于最大权德路径算法的d n a 多序列比对方法研究 其中爨线表示为鞠溺残基，其弯8 令稳弱残鏊 插入空位后两序列匹配如下： s 1 ：at cg a gc tg gt l | | | l| | | s 2 ：at cg a gcggt 插入空位后有1 0 个相同残基，在插入空位盾残基的匹配数比原来没有空位的 时候增加了，这就说明空位插入的必要性，也反应了j 莘列进化过程中的撼入及删 豫过程。毽是舞鹰送行空位静摇入麓是一个缦颡难懿阕题，魄是我褒要磅究的重 点。 2 土l 多序到比对阚题 根据上述描述可将序列比对问题描述为一个五元组： m s a 一( ，4 ，o ，f ) 英中：1 ) = lu 。 为多序穰磁对嚣耱号藤，l 一 a ，鼍c ，g ( 涨at | 挚翔) 或 1 = a ，c ，d ，e ，f ，g h ，l ，k ，l ，m ，n ，p ，q ，r ，s ，t ，v ，w ，y ( 蛋白质序列) 为组成序列的残基， 为空位符，表示比对过程中插入的空位。2 ) s 为待比对的序列集，每条序列由数 量不等懿羧基组残。s 一蕊l 产l ，2 ，嘲，是= ( 。n ，c i 0 ，其中， 为序剜熬长发， c 。为序列蜀中的第，个残基。3 ) “一( 盯彩。为多序列沈对的结果矩阵，篡中，8 。矩阵的每一列为个位点上的比对，矩阵的第f 行对应与参与比对的第f 条 序列，序列中非空谴残基的先后顺序在比对前艏不能发生变化。4 ) 0 为基本眈对 操作象，d = i n s e 墅g a p ，d e l e 晚g 神 ，帮插入帮测除空霞撩佟。5 ) f 为在基本操 作集上实现最优比对的方法，它确定一系列在特定位点上的掇位插入和删除操作。 ，即为所研究的核心问题，也就是本文所要提出的核心方法。 毽楚空位蹙理楚镑对淳囊遂佬过程中可筏发生鹣捶入亵缺失嚣设诗醵。捶入 和缺失可能只涉及1 个或2 个残赫，也可能是熬个功能域。弓l 入空位不仅娶考虑 到空位总数，还必须考虑连续空位的数量。所以必须对引入空位做适当的处理， 教引入蹙位罚分豹撅念。 2 1 2 空位罚分 所谬空位毳分，藏楚猜对予套垮麓毙对遘程中g l 入熬每个窆璧都要按照巢耱怒 则扣除定的分值作为惩罚，从而尽可能的逼遇现实生物避化规律。 假定，初始输入序列为j t 和s 2 ，比对后的输出序列为s l o 和s 2 0 ，且比对后的 痔到长发为三，掌矮鼹空位弱分嫒剩育三秘： 菊：二章生物序列比对 。鬻量空位弱分 这怒一种最简举的罚分策略，p 对插入比对序列的每个空位都赋予一个常数量 的罚分i 蕾，整个比对的空位罚分就是插入的全部空位数如的罚分之和，即x 磁。 这释弱分策略的优点是篱攀，不会增加额矫的时闻复杂崖。但是其缺点也是显 而易见的。因为在实际的生物分予进化中，撼因中不同位点的突变概率鼹不同的， 对每个空位使用相同的常量罚分鼹然是不能准确刻画序列比对的生物意义。 2 毽定空位臻分 这种罚分策略楚从整体上处理插入的空位，即序列中捕入的相连空格被着作一 个整体进行罚分。这样每个空位的罚分都娥与其长度无关的。具体计算如下： 遐f 表示甄怒或者不器愁戆霉分选，搬暖x ，o = o b 均= 0 ； 娜整个比对的得分计算公式为式( 2 一1 ) ： ：。盯0 。【f 1 b d + 卿s 式( 2 1 ) 其中g a p s 表示空位豹数鏊。 馕定空位罚分缀然可以避免常量空位罚分将锦分单纯依赖子空位长度的缺点， 但是却忽略了空位长度对比对结果的影响，可能造成插入过多空格导致割裂整个 比对片段。因此更合适的罚分策噱应当同时考虑g l 入空位长度的影响，但又要避 免擎筑鹃长度猿敖熬褥分。 3 仿射空位罚分 仿身寸型的空位罚分策略则把整个空位罚分分成两个部分进行罚分：一部分称 为开羧窆位爱分( 鳓o p e 难l l gp 。烈t y ) ，另一帮分穗为扩展空位嚣分( g a pe x e n s i p e n a l t y ) 。对于长廉为g 的空位，为开放空位罚分值，纵为扩展空位镯分值， 则总的罚分值的计算公式为；妒= 名。q 聪，这样熬个比对的得分计算公 式为式( 2 2 ) ： ：。盯t o l 嘞套十删十吼渺s s 式( 2 2 ) 其中g a p s 表示空位的数目，s p a c e s 表示空格的数目。 镄射型的空位躅分蒙略能够比较准确款反蚨真实豹生物基嚣变异援律，罄基 因产生插入和变异怒缀罕觅的，值当它们一虽发生，藏会影响到一系列辩近的残 基。 2 。1 3 替代矩阵 在序列比对中，我们可以用替代矩阵 4 】采增强弱势比对的敏感性。很显然， 在相关蛋皂质之闽，某些氨基酸可阻狠容易媳粳互取代丽不臻改变它们豹生理生 1 0 基于最大权德路径算法的d n a 多序列比对方法研究 诧挂溪。在诗篓毙对分馑时，稳溺戆氨基酸打分会毫于替l 弋躲氨基酸，露绦守懿 取代打分离于非保守变化，换句话说，设计了一系列的分德，而且，在眈辩非常 相近的序列以及差异极大的序列时会设计出不同系统的分值，考虑到这些因素， 使用骜代始阵会极为鸯剩，在这个矩阵中，任何氨基酸配对的分值会一目了然。 第一个广泛使藤鹣最优矩薛建立在遥往酶患突变模螫上( p a m ) 【5 l 。一个瓢m 就是一个进化的变异单位即1 的氨基酸改变，遮并不意味着缀过1 0 0 次p a m 后， 每个氨慕酸都发生变化，因为其中些位置可能会经过多次淑变，甚至可能变回 到蠹竞戆鬣基酸，嚣诧勇羚一些氮麓酸哥戆不笈生改交。魏鬃这些变毒 ：是疆壤戆， 那么每一种可能的取代频率仅仅取决于不同氯基酸的出现的频率( 称为背景频 率) 。然而，在相关蛋臼质中，已缀发现的替代频率( 称为目标频率) 大大地倾向 予那些不影确蛋白囊功能豹替代，挠句话说，这些点突变已经被进化所接受。 d a 媳。霞闷合作者们第一次使雳了l o g o 琵处理，在这种处理中，矩阵中静替代分 值同目标频率于与背辙频率的比值的自然对数成比例。为了评估目标频率，人们 用非常相近的序列( 比对时不需要静代矩阵) 来收集对应于个p a m 的突变频率， 然蜃褥数攥夕 摧至2 5 0 令p a 。溅然d a 舜。耍簿a 只发表了淞抛5 0 ，毽潜在豹 突变数据可以外推至葳它p a m 值，产生一组矩阵，在比较蓑辩极大的序列时，通 常在较高的p ：a m 值处得到最佳结果，比如在p a m 2 0 0 到2 5 0 之间，较低值的p a m 矩阵一般使建予高度樱似豹序列。 用丽样方式建立了b l o s u m 替代矩阵，僵在评信磊标频率时，应尾r 不阉的 策略，熬本数据来源于b l o c k s 数据库，其中觎括了局部多煎比对( 包含较远的 相关序列，同在p a m 中使用较近的相关序列相反) 。虽然在这种情况下，没有进 讫模型，侄它露往点在予可豉透过巍接蕊察获褥数疆露不是逶逶努稚获褥。溺麓m 模型一样，也有许多编号的b l o s u m 矩阵，这里的编号指的是序列可能糟同的最 高水平，并且同模型保持独立性。举例来说，b l o s u m 6 2 分值矩阵至少有6 2 瞧稳羁比铡豹彦奠被缀合藏一令露捌，因魏替代频率更燕受裂那些凌空位交仡还 大的序列的极大影响，替代矩阵在处理高度相似序列时使用高的闽值( 直至 b l o s u m 9 0 ) ，处理麓异大的序列时使用低的阈值( 直至b l o s u m 3 0 ) 。 2 1 。4 序剜跑对缭巢的评翔标准 目前还没有一个公认的方法来评价多序列比对结果的优劣嘲。本文为了评价多 序列晓对结果夔努坏，一毅爱实验瑷褥缝暴亵标壤跑对疼秘热转a 班b a s 秘孛懿参 考数据谶行比较，分别计算两个分值t l l es u mo fp a i rs c o r 。( s p d 和m ec o l 咖 s c o r e ( c f 7 1 。假定实验所得序列个数为，每条序列有m 列，而参考序列的列数 为强，第f 捌的残基表示为：c i i ，c ，e 冲则这瓶个值的计努方法分别攒透始下： 籀二章生物序列比对 强对一到上麓每一对残蒸啕帮e 静霆又尹壮，翅慕与s 瓣比聪上瑟籀藏， 则k 为1 ，反之为o 。则每一列的值s 的计辣公式如式( 2 - 3 ) ： s ；= 乙；。羔，p 社式( 2 - 3 ) 霰设爵僮为参考羧捶裹谴鹣蕊篷。蠢涮毽诗羹鲡公式( 2 4 ) ： 跚= 竺甄式( 2 4 ) 嬲如果每一列上的所有残慕都相等，则o ；= 1 ，否则c 严o ，则c s 谯计算如公 式( 2 5 ) ： 删= 麓卢式( 2 5 ) 假楚，如果没商标准拢对瘁俸参考， 多嵇方法对予同一输入数攥之阀瓣魄较， 刷强可按式( 2 6 ) 计算( 这秘计簿方法适合 不麓鞠来绝对辫鞭院对结莱酶俊劣) ： 娜= ：。s ，肛+ + ( 一1 ) 2 ) 式( 2 。6 ) 显然，s 嬲是残基嚣雄臻对齐戆毙率，露c s 莲是搿有序疑准确对齐戆毙率。 下面我们的实验中将采用这两个谯来评估本黧法的比对缩聚。 2 2 序列比对算法 目黼，进行序列比对的算法很多，而这黪算法大多是魁乎运筹学中动态规划 的算法思想，只是在其基础上进行了不同程艨的改进而已。根据同时进行比对的 序歹l 祭数，彦捌磁对分为双痔列魄黠( p 赫w i s es e 疆e 璐。a l i 辨搬嘟) 襄多痔列比对 ( m u l t i p l es e q u e n c e a l i g m e n t ) 。序列比对从眈对范围考虑也可分为全局比对( g l o b a l a l i g n m e n t ) 和局部比对( l o c a la l 域n m e n t ) ，全局比对考虑序列的全局相似性，局部 比对考虑序列片断之闻的相似性。 2 2 1 全局和局部比对 全髑毙对是扶头到逞全程毙技，考虑序列熬整体辐叛性。全是多序列毖对可 以簦羽成证明新序鳓与已有序剐家族的同源髋；帮助预测新蛋白质序硎的二级和 三级结构；是进行分子进化分析的重要前提。局部比对考虑序列部分区域的相似 性。局鄢比对的生物学基础是：蛋自质功能位点由较短的序列片断组成，尽管在 彦歹l 瓣葵它部位霹熊有箍入、嬲除或突交，餐建这些彦尉片断其有相当大的傈守 性a 此时，局部比对往往比全局比对具有更高的灵敏度，冀结果更具有生物意义。 局部多序列比对可以用来刻画鬣臼质家族和越家族。 1 2 基丁最大权值路径算法的d n a 多序列比对方法研究 2 2 2 双序列比对 双序列比对是指通过一定算法对两条d n a 或蛋白质序列进行比较，找出两者 之间的最大相似性匹配。其已经成为序列比对问题和数据库搜索的基础。 自从f “c h 引提出基于统计的方法，利用计算机来自动的比较蛋白质序列以取 代人眼的观察比较以来，国际上对序列比对的研究已有几十年的历史。最有代表 性的双序列比对算法有点阵图法【9 】和动态规划算法。 1 点阵图法 点阵图法是一种最简单且容易实现的双序列比对方法。该方法是通过将一条 序列排在上首，另一条序列纵列排在左端，两个序列在任何位置上若出现相同残 基，就在两个序列对应的交叉位置上标注一个点。结果排列成对角线的点列体现 出两条序列间具有相同的残基，从而形象的表明序列间的相似性。 点阵图法能较容易的显示插入缺失( 对角线水平或垂直偏移) 以及正向和反向 重复片断的存在。这种方法的主要优点在于可以找到两条序列间的所有可能的残 基匹配，但主要的局限是大部分的点阵计算机程序并不能显示真实的比对序列。 因此，实际比对区域需要用其它比对方法来检测，如动态规划算法，这些方法是 自动的。 2 动态规划算法 自从n e e d l e m a n 和w t l l l s c h 【1 0 】首次提出动态规划算法以来，双序列比对算法在 其后的三十多年中得到了广泛的应用和改进，成为序列分析的一个重要理论基础 】。基于动态规划思想的序列比对算法很多，其中最著名的有两个： n e e d l e m a i l w 吼s c h 算法( 1 9 7 0 ) ，为双序列全局比对提供了可以操作的算法； s m i t h w i t e 册a n 算法【1 刁( 1 9 8 1 ) ，是对n e e d l e m a n w u n s c h 算法的改进，为双序列局 部比对提供了有效的算法。下面就详细介绍动态规划算法。 动态规划算法非常适用于序列比对。比对的结果往往不止一种。长度为m 和 ”的序列s t 【l 啪】和s 2 1 n 在全长范围的比对结果，包含了j l 和的的前缀子序 列j l 1 f 】和【1 卅( 1 f m ，1 句n ) 的比对结果，这是一个递归的关系。因此 可以先求解子序列的最优值，根据递归关系求解更大规模的子问题( 更长的子序 列) ，直到求得序列s l 1 m 和s 2 1 n 】的比对最优值。然后根据各阶段最优值信息， 采用回溯方法，构造出最优序列比对结果。 假设对序列5 l 【l m 和j 2 1 h 利用动态规划算法进行比对。则我们首先构建 一个大小为+ 1 ) ( n + 1 ) 的矩阵，矩阵中的元素m f ，月( 0 f m ，o q 珂) 记录了前 缀子序列j l 1 司和叫1 胡的最优比对得分。则根据递归关系，a 饥m ，挖 就是序列 s l 和s 2 的最优比对得分。矩阵的第一行和第一列表示一个子序列同空位的比对分 第二章生物序列比对 值，因此计算矩阵元素的初始条件为： m o ，o _ 0 心f ，o 】= ：，盯0 。m ) ( 1 f m ，1 勺即) m o ，卅= ：。口( - ，j ：【，d ( 1 f 动，即点所代表的字符串长度为缸1 ，则我们可以采用如下规则 构造d eb r u i j n 图，即对字符串中每i 个字符组成上述两点一边的结构，然后将 此结构添加到d eb n l i j n 图中，添加规则为：如果d eb “j n 图中存在点或边代表的 字符串与结构中的点或边代表的字符串匹配，那么就把匹配的点或边融合成一个 点或边，而结构中未被融合的点或边将成为图中新的点或边。例如图3 2 就是一个 当后= 4 ，根据字符串“a c g t a c g t ”构造d eb m i n 图的一个简单例子： 图3 2 根据字符串“a c g t a c g t ”构造的d eb r u i j n 图 显然，当一个字符串可以被构造成图时，多个字符串也就可以根据上述规则构 造成一个d eb m u n 图。因此，多序列比对问题中的多条序列显然也可以被构造成 为一个d eb m u n 图，本文所提出的算法就是基于这个思想而将多序列比对问题中 的多条输入序列表示为一个d eb m u n 图，从而基于图模型解决多序列比对问题。 3 2 基于最大权值路径算法的全局d n a 多序列比对方法 3 2 1 算法的引入 在2 2 3 节描述的各种多序列比对方法都各有其不同的优点，但是它们有一 个共同的缺点：对于大量输入序列，其时空复杂度依然是实际应