（农业机械化工程专业论文）生物序列比对算法研究.pdf

摘要随着多种基因组计划的逐步实施，产生的有关核酸、蛋白质序列和结构的“海量”数据，对生物信息学研究既是机遇也是挑战企图完全通过生物实验的方法来确定所有序列的结构、功能非常困难，同时也不经济。因而利用序列比对寻找与功能未知序列同源的已知序列，用己知预测未知就显得尤为重要。在这个过程中，提高序列比对的有效性、减少运行时间和存储空间具有重要的理论意义和实用价值。本文利用动态规划，概率统计等方法对多序列比对问题进行了研究在理论方面：提出了相对多序列比对差异性、压缩矩阵等概念；对算法中部分迭代公式进行了归纳、抽象给出了基于压缩矩阵的表达递推形式。在算法方面：设计了具有监控机制的多序列比对遗传算法；提出了多序列比对的刹面广义相关隐马尔可夫模型。主要工作和研究成果如下：1 为了描述一个多序列比对是否具有某种特征统计特性，提出了多序列比对相对于某己知特征统计矩阵的代价概念，并给出了具体定义在此基础上，定义了一组多序列比对差异性量化指标，用于种群多样性判别。2 针对多序列比对的遗传算法中缺少利用已知种群先验信息的问题，提出了一种利用种群多样性监控、指导多序列比对的遗传算法执行步骤的比对算法结果表明，新算法在避免局部最优解方面有较好的表现，且比对结果宜具有区块性。3 针对剖面隐马尔可夫模型中状态转换及符号输出的特性，以及目前基于此模型的迭代表达公式过于繁琐的问题，提出了压缩矩阵、向前、向后概率向量等概念。其中状态压缩矩阵是由一个阶数为3 ( l + 1 ) 3 ( l + 1 ) 的矩阵压缩后得到的阶数为9 ( + 1 ) 的矩阵( l 为正整数) 。且保留原有矩阵的全部信息。显然，原矩阵阶数越大，压缩矩阵节省的存储空间就越多，为编程实现提供了节省存储空间的理论依据此外，给出了基于压缩矩阵表示的递推关系式，使迭代过程直观化、模块化。易于编程实现4 针对割砸隐马尔可夫模型没有考虑输出的观测字符依赖前一时刻输出的观测字符，而生物序列中的字符实际上又不是相互独立的这一矛盾，将语音识别领域的双重分次约束隐马尔可夫模型用于多序列比对，建立了用于多序列比对的剖面广义相关隐马尔可夫模型，新模型更符合生物序列固有的特性。5 ，设计并实现了一个基于w i n d o w s 操作系统的序列比对系统。该系统采用v b 6 0 和e x c e l进行开发系统界面友好，操作简单有便捷的工具栏、系统菜单、帮助等模块。为研究、利用多序列比对人员提供了一个平台关键词：生物信息学，多序列比对，遗传算法，跨马尔可夫模型，剖面隐马尔可夫模型a b s t r a c td a t ac o n c e r n i n gw i t hs e q u e n c e sa n ds t r u c t u r e so fd n aa n dp r o t e i nh a sa s c e n d e de x p o n e n t i a l l yn o w a d a y s , w i t ht h eg r a d u a l l yi m p l e m e n t i n go ft h eh u m a ng e n u i n ep r o j e c tt h eh u g eb i o i n f o r m a t i c ed a t a b a s eb r i n g su pa v c c h a l l e n g et ot h ee x i s t e dm e t h o d sa n da b i l i t yo fd a t ap r o c e s s 吨t h ew o r ko nb i o l n f o r m a l i c em a i n l ya i m sa td i g g i n go u tt h ev a l u a b l eb i o i n f o r m a t i c s0 0d i s v c ff u n c t i o n a la n ds t r u c t u r a lk n o w l e d g er a t i o n a l l yi nd n aa n dp r o t e i ns e q u e n c e s p r e s e n t l yt h et e c h n i q u e so fg e n el o c a t i n g r e p e t i t i v es e q u e n c es e a r c h , a n dg e n eg r o u ps p l i c i n ga r ea l lb a s e do nt h es e q u e n c ea l i g m e n t ,w h i c hd e m o n s t r a t e st h es i g l 吐矗髓n o fi m p r o v i n gs e q u e n c ea l i g m e n tv e r a c i t ya n dr u n n i n ge f f i c i e n c y m a i nr e s e a r c h e si nt h ep a p e ra r eo om u l t i p l es e q u e n c ea l i g m e mb ye m p l o y i n gd y n a m i cp r o 舢m i n g p r o b a b i l i t ya n ds t a t i s t i c s t h e 州譬州佃so fd i f f e r e n c e sa n dc o m p r e s sm a t r i xf o rm u l t i p l es e q u e n c ea l i g m e n ta r ed e s c r i b e df i r s t a n dt h e e , s o 嘶o fg e n e r a l l ye x p r e s s i o n * a l ep r o v i d e da f t e rb o t ht h ei n d u c t i o na n dt h ea b s t r a c t i o na r ea p p l i e dt o 对g o l i t h m 缸m u l t i p l e u e l l c ca l i g n g n lag o n e r a l i z e d - m u t u a l i t yp r o f i l eh m mm o d e l 缸p r e s e n t e da l s o l a s t l y , m u l t i p l es e q u e n c ea l i g n m e n tb a s e do ng e n e t i ca l g o r i t h mw h i c hh a sm o n i t o r i n gc h a n t c t e r i s t l e si sd e a l g n e 正t h em a i nw o ai s剐阳m 剐d z c da 5f o l l o w s ：1 i m p r o v i n ga n de x t e n d i n gt h ec o n c e p t i o no ft h e 醴t h a tr e l a t e st otm g l as e q u e n c ef o rk n o w ne i g e n - m a t r i x t h e d e f i n i t i o n o f t h e c o s tr e l a t e d t o m u l t i p l es e q u e n c e a l i g n k - m t f o r k n o w n e m i s g i v e n a i rw e l l au m i l e g i c a li n d e xt oi d e n t i f yt h ed i f f e r e n c ef o rm u l t i p l es e q u e n c ea l i g m c n ti sp r e s e n t e d i tc a l lb ea ni d e n t i f i c a t i o no f v a r i o u ss p e c i eg r o u p s 2 a m 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 mb a s e do ng e n e t i ca l g o r i t h mi so b t a i n e d ，w h i c hi sb a s e di l o to n l yo i lt h em o n i t o r i n go fs p e d cg r o u pv a r i e t yb u ta l s oo i la n c e s t o ri n f o n u a f i o ni nt h em u l t i p l es e q u e n c e si t s e l f i ti sh a ss h o w nt h i sa l i g n m e n ta l g o r i t h mc a ns u p p r e s sp r e m a m r i t ya n dt h es e q u e n c ec m i l p a r er e s u l t sh a v ez o n ec h a r a c t e r i s t i c & 3 t h ef o r t h b a c kp r o b a b i l i t ye n ds t a t u s - c o m p r e s sm a t r i xa r ei n t r o d u c e di ns o l v i n gt h es t a t u s 1 a n s f e ra n dc h a r to u t p u t i n h h m m o d e l h e r e , s t a t u s - c o m p r e s s m a t r i xh a sa o r d e r o f o n l y9 x 伍4 - 1 ) ( w h e r eli sa ni n t e g e r ) , w h i c hi sa c h i e v e db yc o m p r e s s i n gt h ei n i t i a lm a t r i xw i t h4o r d e ro f3 ( 上4 - 1 ) 3 弛4 - 1 ) t h i sf a c tu n d e r l i e st h em e m o r ys a v i n gi np r o g r a m n m i n g i na d d i t i o n , t h ei t e r a t i o nb a s e do i lt h es t s t u s - c o m p r e s sm a t r i xi sp r e s e n t e d , w h i c hv i s u a l i z e st h ei t e r a t i o np r o c e d u r e ，a n df a c i l i t a t e sc o d i n g 4 i nh m mm o d e l ，e a c ho u t p u to n l yd e p e n d so i li t sp a r e n ts t a t u s c o n s i d e r i n gt h ed e p e n d e n c ea m o n gt h e l e h e r sf o rb i o l o g i c a ls e q u c u 铝, t h ed o u b l er e s t r i c t i o nt e c h n i q u ei ns p e e c hi d e n t i f i c a t i o ni sa l s oc o n s t r u c t e di nm u l t i p l es e q u e n c ea l i g m e n ta l i g n m e n t s t h i sm o d e lj sm o r ec o i n c i d e n tw i t ht h ei n t 血s i cc h a r a c t e r i s t i c so fb i o l o g i c a ls e q u e n c e s 5 as e q u e n c ea l i g m e n ts y s t e mb a s e do i lm i c r o s o f tw i n d o w sw a sd e s i g n e da n dp u t t e di n t op r a c t i c e i tw i l lb eag o o do p e r a t i o np l a t f o r mw i t hc o n v e n i e n tt o o l b a r , s y s t e ml r l 忙i l u ，a n dh e l pm o d u l et om u l t i p l es e q u e n c ea l i g m e n tr e s e a r c h e r s k e yw 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 e a l i g n m e n t ，g a ，h m m ，p r o f d eh m m图卜1 生物分子数据及其关系示意图图1 2 研究技术路线图图2 - 1 核酸的组成图2 - 2 核苷酸连接示意图插图清单27匿2 3d n a 示意图一1 0图2 4 全局比对( 或全局对位排列) 示例，图2 5 局部比对( 或局部对位排列) 图3 - 1 简单遗传算法基本流程框图图3 - 2 位串举例图3 - 3 交叉示意图图3 4 改进算法流程图图3 - 56 条待比对d n a 序列2 32 9图3 - 6c l u s t a l w ( 1 8 1 ) 的比对结果图3 - 7 实验结果一图3 - 8 实验结果二图3 - 9 多序列比对优化方法研究图4 _ l ( 口) 多序列比对( 6 ) 对应的正自u 表达式图4 - 2 路马尔可夫模型图4 - 3 隐马尔可夫模型图4 - 4 向前算法示意图图4 - 5 向后算法示意图图4 - 6 最优路径示意图5 l图4 - 7 用于多序列比对的匹配规模为l 的p r o f i l eh m m 图4 - 8 主状态数为3 的p r o f i l eh m m 的构型图5 - 1 相关隐马尔可夫模型图6 - 1 系统结构图凰6 - 2 系统流程囝图6 - 3m s g a 数据流程图图6 _ 4 输入数据格式例图6 - 5 输入数据格式例图6 - 6 系统数据输入界面图6 - 7 得分矩阵选择界面6 57 08 58 68 78 88 88 9图6 8 算法选择及参数设置界面例8 9图6 - 9 遗传算法评价函数最小值变化趋势图6 一l o 比对结果列表清单表2 - 1 标准氨基酸英文简写对照表表2 - 2 最简得分矩阵表3 - 1 一个已知多重比对马。6 表3 - 2 已知多序列比对的特征统计矩阵只。6 2 4表3 - 3 一个多重比对举例硅6表3 - 4 选择方案例表3 - 5d n a 序列得分矩阵表4 - i 状态转移概率矩阵和初始状态概率分布表4 - 2 观测符号概率矩阵表4 _ 3v i t e r b i 算法中问结果1 表4 - 4v i 蛐i 算法中间结果2表4 - 5 状态编号表4 - 6d n a 多序列比对表4 7 符号发出的频率表6 - ip a m 2 5 0 的对数概率矩阵v5 05 09 0中国农业大学博士学位论文第一章绪论第一章绪论1 1 问题的提出和研究意义1 1 1 “海量”生物数据产生的背景从1 9 5 3 年美国科学家w a t s o n 和英国科学家c r i c k 共同提出d n a 分子双螺旋结构模型至今，分子生物学一宣是生物学研究的前沿学科，成为当代最吸引人也是成果最多的学科之一2 0 0 0年6 月2 6 日。经过美、英、日、法、德和中国科学家的共同努力，在全球统一时间宣告完成了第一张人类基因组工作草图，约3 0 亿碱基对的测序工作被完成，这是人类科学史上又一个里程碑式的事件。2 0 0 3 年4 月1 4 日，人类基因组序列图绘制成功，人类基因组计划的目标全部实现。随后，其它模式生物基因组的测序工作也在迅速进展。总基因序列达4 3 亿的( 水稻) 籼稻基因工作框架图，是继人类基因组之后完成测定的最大基因组也是迄今铡定的最大植物基因组而由此带来的生物信息爆炸，处理生物数据的技术、方法的滞后，则成为困扰当今分子生物学等研究快速发展的一大问题。如何将复杂的生物信息转化成数字信息并利用辅助工具进行分析求解，如何在当前计算能力允许的范畴内对“海量”生物数据进行高速有效地信息处理、挖掘出有用的知识，由此催生了寻找、挖掘、分析生物信息的理论和方法的研究生物信息学这一交叉学科。1 1 2 生物信息学概述生物信息学是综合运用数学、计算机科学和生物学的各种工具。来阐明和理解大量数据所包含的生物学意义韵- - 1 3 学科。它包含了生物信息的获取、处理、存储、分发、分析和解释等诸多方面的研究内容( u s d e p a r t m e n t o f e n e r g y ，毗a 1 ，1 9 9 5 ) 作为一个新的科学领域。生物信息学拥有及其丰富的研究内容和广阔的应用领域，其成果不仅对相关的基础学科起巨大的推动作用，而且还将对基因工程、疾病诊断与治疗、药物开发等领域产生巨大的影响( 乔纳森，2 0 0 6 ；郝柏林。2 0 0 0 ；孙啸2 0 0 5 ：钟扬，2 0 0 3 ) 生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说就是从核酸和蛋白质序列出发，分析序列中表达结构、功能和进化的生物信息。生物信息学研究内容主要包括数据库搜索及序列比对、蛋白质结构预测、计算机辅助基因识别、非编码区分析和d n a 语言研究、分子进化和比较基因组学、序列重叠群装配，遗传密码的起源、基因芯片设计、基于结构的药物分子设计等( 张春霆，2 0 0 0 ；郝柏林，等，2 0 0 0 ) 。生物信息学所处理的生物分子数据主要是d n a 序列、蛋白质序列、大分子结构、基因组及基因表达数据这些数据是生物分子信息的具体表现形式，各数据之问的关系见图1 1 。序列数据、结构数据简单直观，而功能数据却是复杂多变的。在所有类型的数据中序列数据是最基本的( h t t p ：w w w 1 m b e s e o e d u e n ) 中国农业大学博士学位论文第一章绪论圉1 - 1 生物分子数据及其关系示意图1 1 3 研究序列比对的目的与意义序列比对( a l i g l l m e n t ) 又叫序列联配，是序列比较的基本操作序列比对是指待比对序列的各字符问的一种一一对应关系或字符对比排列，这是序列相似程度的一种定性描述。对于两条序列的比对称为双序列比对( p a k - w i s e q u e n c ea l i g | l m e m ) ，对于参与比对的序列数目大于2 的比对，统称为多序歹1 j 比对( m u l t i p l es c 口u e n a i i g n m e n t ) 在分子生物学中，相似性通常简单地指核酸或蛋白质序列的相似性，而不考虑遗传上的联系。虽然相似性和同源性在某种程度上具有一致性，但它们是完全不同的两个概念( a t t w o o dda 1 。著，罗静初等，译，2 0 0 2 ) 在生物学研究中，人们普遍遵循的规律是序列决定结构，结构决定功能。因此，对于功能未知的分子生物序列，通过搜索序列数据库。找到与功能未知序列同源的已知序列。并跟据同源性推测功能未知序列的结构和功能。为生物学研究人员实验确定未知序列的结构和功能提供指导是一种常用的方法。此外，通过比较不同种属的同源序列。还可以得到它们由共同祖先进化而来的信息，这些正是研究序列比对的初始起因。可以说序列比对的根本目的是对不同的生物序列寻找它们的演变规律与特性，了解这种演变规律与特性及这个过程对生命过程的作用。但是从生物信息学的内容与发展来看，序列比对的意义已远不止于此由于自动化的数据测定技术发展，大量生物数据被测定，各种不同的数据库的建立及每年数据测定的量正在以指数级数增长以o e i l b a n k 数据库为例，1 9 9 5 年的数据量为5 0 0 0 万个碱基对，至2 0 0 0 年已达到l 亿个碱基对。面对如此庞大的数据量。搜索同源序列，寻找保守序列模式以解决( 1 ) 序列结构变化与病变的关系；( 2 ) 基因定位问题；( 3 ) 重复序列的搜索问题：( 4 ) 基因组的拼接等问题可想而知不是一件容易的事情，由此可见序列的突变与比对问题已不再是简单的生物进化问题，而是涉及整个生命系统的基因、蛋白质与各种生物大分子结构的信息关系的分析问题。因此我们把序列比对问题看成是近代生命科学与生物信息学的一个重要的基本问题( 沈世镒，2 0 0 4 ) 由此可见，序列比对算法的研究在生物信息学中具有极其重要的理论意义和实用价值。目前。双序列比对已有比较成熟的动态规划算法，而多序列比对目前缺少快速有效的方法。人们虽已提出众多的多序列比对算法，但由于问题自身的计算复杂性，它还尚未得到彻底解决，仍是生物信息学中一个重要且具有挑战性的研究课题。一般评价生物序列比对算法的标准是：运算速度、存储空问，比对效果。本文研究的目标是后两者2中国农业大学博士学位论文第一章绪论1 2 相关理论综述生物信息学本身就是综合运用数学、信息科学和生物学的各种工具，阐明和理解大量数据所包含的生物学意义的一门交叉学科。序列比对实际上就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配残基数。1 2 1 动态规划方法动态规划( d y n a m i cp r o g r a m m i n g ) 是2 0 世纪5 0 年代提出的一种解决多阶段决策问题的最优化方法( 姜衍智，1 9 8 8 ；孙啸，2 0 0 5 ) 该方法可按时间或空间把复杂的问题划分为若干相互联系的阶段。通过逐步分段求解，且现阶段的解决定下一阶段的初始状态，最终获得全局最优解所谓多阶段决策问题是指这样一类活动过程：它可以将问题分为若干个相互联系的阶段，在每个阶段上都要做出决策，而每个阶段的决策，决定下一阶段的的决策。从而决定整个过程的走向。当所有阶段的决策确定以后。就完全确定了该问题的活动过程。各阶段的决策全体构成一个决策序列称为该问题的一个总体决策，简称为一个总体策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优动态规划的理论和方法在求解多阶段决策问题中是卓有成效的，顺序递推和逆序回溯这两个过程是动态规划基本方法的核心动态规划也是生物信息学中一种基本的优化方法，在d n a 序列或者蛋白质序列的比对、基因识别r n a 结构预测、隐马尔可夫模型求解、生物分子探针优化设计等方面有着重要的应用。动态规划解决问题的基本过程是：将一个问题的全局解分解为局部解，顺序递推求出局部最优解，随着执行过程的推进，“局部”逐渐接近“全局”，最终获得全局最优解。在计算机中，以“图”作为求解动态规划问题的数据结构图中的每个顶点代表一个局部问题。其中有一个顶点( 起点) 代表特别的局部问题。即问题的开始阶段，另有一个顶点( 终点) 代表全局问题。这样，一个优化问题可以转化为在图中求出一条从起点到终点的最短路径通过顺序递推求出最短路经的长度，然后，通过逆序回溯找出最短路经1 _ 2 2 数理统计方法概率论与数理统计( p r o b a b i l i t yt h e o r ya n dm a t h e m a t i c a ls t a t i s t i c s ) 是研究和揭示随机现象及其统计规律的数学学科，应用广泛。其主要内容之一是通过对某些现象的频率的观察来发现该现象的内在规律性，并作出一定精确程度的判断和预测。而生物活动常常以大量的、重复的形式出现，既受到内在因素的制约，又受到外界环境的随机干扰，因此概率论和数理统计是现代生物学研究中一种常用的分析方法。无论是传统的生物学还是现代分子生物学，都需要对大量实验数据进行统计分析，发现研究对象内在的规律或者对象之问的联系。通过综合分析，建立合理的数学模型，定量地描述生物活动过程、活动规律或者本质特征在生物信息学领域中，许多分析工作如分析d n a 语言中的语义、分析密码子使用频率、识别基因等，都要用到数理统计方法。其中。隐马尔可夫模型( h i d d e nm a r k o vm o d e l ) 在序列分析方面有着重要的应用。与隐马尔可夫模型相关的技术是马尔可夫链( m a r k o vc h a i n ) ，对于生物分子序列分析马尔可夫链是一个很好的数理中国农业大学博士学位论文第一章绪论统计模型，因为马尔可夫链本身就是相继发生事件的序列，其特征是对于事件序列中的任何一个事件都有一个发生概率，而这个概率依赖于该事件之前的若干个事件( 唐守正等，2 0 0 2 ：孙啸，2 0 0 5 ) 。1 3 比对算法研究进展按序列比对的范围划分，序列比对的数学模型可以分为两类一类是从全长序列出发，考虑序列的整体相似性，即全局比对( g l o b a la l i g n m e n t ) ：另一类是考虑序列部分区域的相似性，即局部比对( 1 0 c a l a l i g n m e n t ) 局部相似性比对的生物学基础是蛋白质功能位点往往是由较短的序列片段组成的，这些部位的序列具有相当丈的保守性，尽管在序歹l j 的其它部位可能有插入、删除或突变。此时，局部相似性比对往往比整体比对具有更高的灵敏度，其结果更具有生物学意义区分这两类相似性和这两种不同的比对方法，对于正确选择比对方法是十分重要的1 3 1 双序列比对经典的双序列比对算法是n e e d l e m a n 和w u n s c h ( 1 9 7 0 ) 最早提出的动态规划比对算法：n e e d l e m a n - w u n s e h 算法，其基本思想是使用迭代方法计算出两个比对序列的所有可能的子比对的相似性分值，存于一个得分矩阵中。然后根据这个得分矩阵，通过动态规划的方法回溯寻找最优的全局相似性比对继该算法之后，s m i t h 和w a t e r m a n ( 1 9 8 1 ) 在改进n e e d l e m a n w u n s e h 算法的基础上，给出一种可以实现局部最优比对的动态规划算法。其基本思想与n e e d l e f n a l 卜w u m c h算法基本相同。区别是局部比对最优片断可以独立生成。这两种算法一直是序列比对的基础算法算法的优点是灵敏度高，缺点是耗时较久为了提高运行速度，l i p m a n 和p e a r s o n ( 1 9 8 5 ) 提出了局部比对的f a s t a 算法。f a s t a 只搜索很短一段相同的序列片断，称为j 元组( t 一切) 其基本思想是一个能揭示出真实序列关系的比对至少包含一个两个序列都拥有的字( f i - 段) ，把查询序列中的所有字编成索引，然后在数据库搜索时查询这个索引，以检索出可能的匹配，这样那些命中的字就能很快地被鉴定出来。f a s t a 对d n a 序列搜索的结果要比对蛋白质序列搜索的结果更敏感，因为它对数据库的每次搜索都只有一个最佳的比对，这样对于蛋白质序列而言，一些有意义的比对可能被错过。a l t s e h u l 等人( 1 9 9 0 ) 提出了b l a s t ( b a s i c l o c a l a l i g n m e n t s e a r c ht 0 0 1 ) 启发式算法。它的着眼点是序列片断对，即两条序列的子序列，它们长度相同，且可形成无空位的完全匹配。其基本思想是通过产生数量较少的但质量更好的匹配片段来提高速度。此外，b l a s t 算法的改进版本已有许多。如同源性比对的p s i b l a s t 算法( a l t s c h u l 。e ta 1 ，1 9 9 7 ) ，它是种可以用来处理空位的b l a s t 算法。自动态规划比对算法首次提出以来，双序列动态规划比对算法得到了广泛的应用和改进，成为序列分折的一个重要理论基础( o i e g e r i e h 2 0 0 0 ；s a n k o f f , 2 0 0 0 ) 到目前为止。两条序列的比对问题己基本解决( g o s h ，1 9 8 2 ：m y e r s ，1 9 8 8 ) ，有成熟的算法和程序1 3 2 多序列比对尽管双序列比对是生物序列分析的基础，但是对于蛋白质家族的成组序列，必须进行多序列4中国农业大学博士学位论文第一章绪论比对才能揭示家族的特征。如果说序列两两比对主要用于建立两条序列的同源关系和推测它们的结构、功能，那么，同时比对一组序列对于研究分子结构、功能及进化关系更为有用。从理论上说，可用将双序列的动态规划比对算法推广到多序列比对中m u r a t a 等( 1 9 8 5 ) 曾成功地将动态规划比对算法推广到三重序列比对中，但是受多维动态规划的时间和空问复杂度的制约，该方法只能限制在数量较少而且序列较短的比对范围内( l i p m a n 。e ta 1 ，1 9 8 9 ) m u r a t a( 1 5 ) ，g o t o h ( 1 9 9 3 ) 曾指出：同时比较三个残基时酌度量( m e a s u r e ) 分值应是三个残基间两两比对的度量之和。将其扩展到斤条序列比对中，则疗条序列比对的度量分值是疗条序列中两两比对的度量之和，这种分值度量叫做s p 度量( s u m - o f - p a i r sm e a s u r e ) 己经证明基于s p 度量的多序列比对是一个n p 完全问题( w a n g e ta i ，1 9 9 4 p a o l a b o n i z z o n i ，2 0 0 1 ) 目前用于多序列比对的方法一般是启发式算法，其中具有代表性的是：渐进序列眈对，迭代序列比对。渐进比对是常用的启发式算法之一，与动态规划、两两序列比对紧密相连，其基本思想是：假设比对的序列是进化相关的，因此可以按其进化顺序，由近至远将序列或子比对结果按双重比对算法逐步进行比对。重复这一过程直到所有序列都加入为止。c l u s t a l ( f e n g 。e ta 1 ，1 9 8 7 ) 是一种典型的渐进比对算法这类算法的主要优点是：简单、快速：缺点是：在比对初期引进的空位无法在比对后期因加入其它序列而修正，易于陷入局部最优解t - c o f f e e ( n o t r e d a m a ，e ta i ，2 0 0 0 ) 是另一个有代表性的渐进比对算法。是现在所有的多序列比对方法中准确程度最高的一种方法该方法将局部比对与全局比对方法相结合，预处理了所有双序列比对数据，结合全局比对和局部比对的信息来创建扩展比对信息库。再利用扩展比对信息库中提取的信息取代替代矩阵进行渐近比对，使得在每一步渐近比对过程中用到的是所有序列之间的关系信息，而不只是仅考虑当前要比对的序列信息。这样的结果比别的单一方法更为准确，尤其是对于存在大量空位插入的情况，效果更为明显迭代比对是另一类有效的启发式算法，它是基于一种能产生比对的算法，并通过迭代方式精细多序列比对，直到比对结果不再改进为止。这类算法不能提供获得优化比对结果的保证，但却具有鲁棒性和对比对序列个数不敏感等特性。如基于遗传算法的多序列比对s a g a 算法( k o s m a s ，1 9 9 6 ) 其基本思想是将序列集中不等长的序罗i j 以两端加空位方式补齐，构造初始群体中的个体：共设有交叉，加空位，移动空位等2 2 个遗传算子，并根据上一代算子所起的作用，给其以一定的权值，根据权值的大小动态决定这一代是否使用该算子：选用w s p ( w e i g h t e ds u i i i so f p a i r s )度量作为适应度函数。该算法的优点是：原则上可以对任意多个序列同时比对，而不会受到限制：主要缺点是速度慢，易陷入局部最优解。其它算法还有：分治法( s t o y e ，e ta 1 ，1 9 9 7 ；s t o y e ，1 9 9 8 ) 、基于傅立叶变换( k a t o h ，2 0 0 2 )等方法此外，值得一提的还有隐马尔可夫模型( h i d d e n m a l k o v m o d e l ) 它在序列分析方面有着重要的应用是序列比对的另一个有力工具( z r o g h ，1 9 9 8 ：e d d y ，1 9 9 8 ：b i m e y ，2 0 0 1 ) 对于生物分子序列分析。马尔可夫链是一个很好的数理统计模型，因为马尔可夫链本身就是相继发生事件的序列，其特征是对于事件序列中的任何一个事件都有一个发生概率，而这个概率依赖于该事件之前的若干个事件。c h u r c h i l l ( 1 9 8 9 ) 将其引入计算生物学、e d d y ( 1 9 9 5 ) 和k r o 曲等( 1 9 9 4 )将隐马尔可夫模型引入生物信息学。隐马尔可夫模型( h i d d e nm a r k o vm o d e l 。h m m ) 是一种描述随机过程统计特性的概率模型。5中国农业大学博士学位论文第一章绪论一个训练好的隐马尔可夫模型，可以代表具有共同特征的蛋白质序列。h m m 主要可以解决三类基本问题。第一是路径寻优问题。即给定一个隐马尔可夫模型五= 钺s ，臼，彳，丑，万 和一个字符序列d ，在五= 五心，口，彳，8 ，石) 中为0 寻找一条最优路径，该路径从起始状态出发，结束于终止状态，这个问题的典型解决方案为v i t e r b i 算法：第二是路径生成概率问题，即对于给定的模型a ，求该模型产生字符序列d 的概率，一般采用向前或反向算法来解决；第三是参数估计问题，即对于给定的一个字符序列0 ，如何调整模型且的参数，使得概率尸( dl 五) 最大，一般采用b a u m - w e l c h 方法利用h m m 来进行序列分析具有以下优点：以概率理论为基础，模型中的每个状态都对应着一个概率输出函数，并且有对应的学习算法来训练h m m ；可直接从原始序列数据进行学习h m m 方法可以通过己知的观察序列来进行学习，该观察序列描述了一组隐藏的状态；与神经网络方法不同，h m m 对序列的长度没有限制，并且学习是在无监督情况下进行的：应用范围广；多序列比对、结构预测和模式发现等；可以以模块或者分层的形式应用虽然国内在生物信息方面起步较晚，但目前也有大批学者对序列比对问题进行了深入而广泛地研究南开大学数学科学学院的沈世镒教授提出了基于统计估计的相似序列比对的快速算法s a p p a ( 沈世镒，1 9 9 9 ) 。并给出基于熵的多序列比对的信息度量准则( 沈世镒。2 0 0 2 ) 。华中科技大学王能超小组对多序列比对算法进行了追踪研究( 郭卫斌，2 0 0 1 ；李小妹，2 0 0 4 ；陈莹，2 0 0 4 ：陈宁涛，2 0 0 6 ) 上海大学的顾燕红( 2 0 0 3 ) 提出了一个两阶段( 参数和构形) 交替优化算法。它能自动地从数据估计参数和优化构形，实现了机器学习的智能化。军事医学科学院贺福初小组在对b l a s t 程序的输出结果进行仔细分析的基础上，基于“求同存异”的思想，设计了一个多序列比对程序m b l a s t ( 孙焕东。2 0 0 1 ) 由于该程序是基于b l a s t 程序的输出结果，属于局部多序列比对，因此更容易检出序列的同源区域中科院计算技术研究所的张法开发了s m i t h - w a t e r m a n 的并行算法( 2 0 0 4 ) ，该算法把查询序列分为若干片段，并分配给相应的各个处理器，而后并行地按s m i t h - w a t e r m a n 算法与目标序列进行比对，再通过按一定规则的扩展过程求取序列的优化匹配。与其它并行算法相比，该算法有效地降低了内存空间的需求，并实现了对大规模序列的并行处理大连理工大学张敏( 2 0 0 5 ) 将信息熵度量序列间进化距离的f d o d 方法引入到多序列比对算法研究中，提出一种新的基于i p m s a 和信息差异度量的多序列比对算法m s a i d 该算法包含两部分：基于信息差异度量的渐进多序列比对算法m s a i d - i 和迭代渐进多序列比对算法m s a i d 。此外。北京工业大学的龚道雄( 2 0 0 3 ，2 0 0 4 ) 、西安电子科技大学的张鹏帅( 2 0 0 5 ) 等人也分别采取遗传算法、模拟退火及粒子群等优化算法对多序列比对进行研究西安电子科技大学的霍红卫( 1 9 9 8 ) ，中国农业大学的唐玉荣( 2 0 0 4 ) 等都分别从不同方面对多序列比对算法给予了研究总之，到目前为止，多序列比对仍是一个尚未完全解决的问题，不同的算法有不同的针对性和适用范围及待改进之处，因此需要人们去寻求新方法、新思路，促进该问题的有效解决。根据上述分析，本文将对基于遗传算法、隐马尔可夫模型进行序列比对的算法进行研究、改进。6中国农业大学博十学位论文第一章绪论1 4 研究技术路线、内容与特色1 4 1 研究的技术路线论文具体的技术路线如图卜2 所示。1 4 2 研究的内容图i - 2 研究技术路线围( 1 ) 生物序列比对问题的数学描述，进一步完善序列比对问题的定义体系，规范序列比对问题的数学描述。( 2 ) 分析多序列比对的特征，研究刻画种群多样性的指标，提出多序列比对相对于某已知特征统计矩阵的代价等概念。分析基于遗传算法的多序列比对算法的编码策略、遗传操作策略等特性，并将群多样性指标应用于基于遗传算法的多序列比对算法中，提出改进的算法。7，lil-中国农业大学博士学位论文第一章绪论( 3 ) 研究生物序列比对的剖面隐马尔可夫模型与隐马尔可夫模型的关系，及所应用领域中状态转换及符号输出的特性及迭代表达公式。研究其迭代变量、迭代关系，推导并简化递推关系。c 4 ) 针对生物序列中的字符存在相关性的问题，对语音识别领域的双重分次约束隐马尔可夫模型进行研究，建立用于多序列比对的剖面广义相关隐马尔可夫模型给出剖面广义相关隐马尔可夫模型和参数迭代的具体表达式c 5 ) 利用v b 和e x c e l 的优势，设计、实现一个基于 q v f i n d o w s 操作系统的序列比对系统为研究，利用多序列比对的人员提供一个比对平台。1 4 3 研究特色和创新与已有的同类研究相比，本论文的研究特色、创新之处体现在以下5 方面：( 1 ) 用数学语言对序列比对问题的描述和算法的表述进行了抽象、简化为了描述一个多序列比对是否具有某种特征统计特性，提出了多序列比对相对于某已知特征统计矩阵的代价概念，并给出了具体定义。在此基础上，利用偏差的概念定义了一组多序列比对差异性量化指标，该指标可以用于种群多样性的判别。( 2 ) 针对多序列比对的遗传算法中缺少利用已知种群先验信息的问题提出了一种利用种群多样性监控、指导多序列比对的遗传算法执行步骤的比对算法。结果表明，新算法在避免局部最优解方面有较好的表现，且比对结果宜具有区块性。c 3 ) 针对剖面隐马尔可夫模型中状态转换及符号输出的特性及目前基于此模型的迭代表达公式过于繁琐的问题，给出了剖面隐马尔可夫模型的参数压缩矩阵及迭代的抽象表达式，解决了分段表达过于繁琐的问题，并给出了向前、向后概率向量的向量递推关系。起到了直观化迭代过程的作用，并为算法实现中减少计算机使用空间奠定了理论基础( 4 ) 给出了利用多序列比对的遗传算法确定剖面隐马尔可夫模型匹配规模的策略，使该参数的设置减少了随机性( 5 ) 考虑刭生物序歹l j 相邻残基具有相关性关系，将语音识别领域的双重分次约束隐马尔可夫模型用于多序列比对，建立了用于多序列比对的剖面广义相关隐马尔可夫模型，并给出相应的求解递推公式。新模型更符合生物序列的固有特性。8中国农业大学博士学位论文第二章生物序列比较的基本概念与算法第二章生物序列比较的基本概念与算法生物序列是d n a 序列、r n a 序列和蛋白质序列的总称。生物序列分析的核心问题之一是对不同物种生物序列的相互关系进行研究，从而寻找与确定不同生物序列的稳定区域及变化规律。目前生物计算中的基因定位问题、重复序列的搜索问题及基因组的拼接问题等都是以序列比对为基础由此可见，生物序列比对问题已成为近代生命科学与生物信息学的一个重要的基本问题和必要的研究手段。本章在对生物序列的背景及表示方法归纳、总结的基础上，针对序列比对问题中存在表述不完善的问题，将补充完善其定义体系及数学描述。为后续章节的研究奠定基础。此外，对序列比对中几种有代表性的算法的基本思想和主要步骤进行描述2 1 生物序列的表示方法与数学描述2 1 1 生物序列的背景生物体是一个复杂的系统，同时也是一个信息系统，该系统控制着生物的遗传、生长和发育所有的信息都存贮在生物体内的遗传物质中由分子生物学( 阎龙飞等，1 9 9 7 ；朱玉贤等，2 0 0 2 ) 知，核酸是生物体内的高分子化合物，是由很多单核苷酸聚合形成的多聚核苷酸( p o l y n u c l e o t i d e ) ，包括脱氧核糖核酸d n a 和核糖核酸r n a 两大类。核苷酸是组成核酸的基本单位，组成d n a 的核苷酸是脱氧核糖核苷酸( d e o x y r i b o n u c l e o f i d e ) ，组成r n a 的是核糖核苷酸( r j b o n n d e o t i d e ) 核苷酸可以进一步水解为核苷( n u c l e o s i d e ) 和磷酸，核苷又可以水解为戊糖( p e n t o s e ) 和碱基( b a s e ) ( 图2 1 ) 。i 。i 戊糖核酸寸核苷酸 ”l 碱基【磷酸阳2 - i 核酸的组成人们已经认识到遗传信息的载体主要是d n a ( 在少数情况下核糖核酸( r n a ) 也充当遗传信息的载体) ，其基本组成是核苷，且不同核苷中变化的只有碱基碱基共有四种，