（应用数学专业论文）生物序列、结构比较中若干数学模型研究及应用.pdf

大连理工大学博士学位论文 摘要 近年来。得益于基因组测序技术的进步和物质结构解析技术的发展，使有关生物序 列和结构的数据与日俱增面对海量的数据，如何对其进行科学的分析、处理和保存给计 算机科学、数学等学科提出严峻的挑战，同时也吸引大量的数理科学工作者转向生命科 学的研究领域，使得计算分子生物学应运而生计算分子生物学的研究内容十分丰富， 例如，序列比较、基因识别、分子进化、比较基因组学、r n a 和蛋白质结构预测等等， 其中大多数研究工作是以序列、结构的比较为基础，因此，生物序列、结构的比较不仅 是计算分子生物学中最基本、最重要的课题之一，而且对生命科学的研究具有深远的影 响本文以该领域中的若干数学模型为研究对象，主要成果有。 1 、在第二章，提出了d n a 序列的、7 n 几何表示模型，并设计一种算法，用来寻找 特定碱基含量丰富的片断；以相邻碱基对为对象，利用单元和系统的概念，设计了d n a 序列的p n n - 几何表示模型，并提取了一种简单有效的数值刻画量；指出了几何表示模 型中的距离矩阵在刻画曲线时存在退化现象，并利用曲率矩阵克服了距离矩阵的缺陷 2 、在第三章，构建了生物序列、结构的马尔可夫模型，比较了k 步转移概率在刻 画生物序列中的差异，并将模型拓展应用到结构比较、结构相似性搜索、进化分析等领 域；利用加权相对熵构建了字统计模型和马尔可夫模型的混合模型，利用有效的评价性 方法和大量实验表明混合模型提高了模型抽取信息的能力 3 、在第四章，根据序列、结构中元素的分布存在随机性，定义随机分布函数，并引 入回归分析模型来寻找分布函数之间的依存关系，进而发现序列、结构中元素的整体变 化规律另外，利用不同结构对应回归模型间的差异获得不同结构的相似程度，从而降 低了结构比较的复杂度 4 、在第五章，利用氨基酸打分矩阵，提出了“蛋白质空间”的定义以及“蛋白质空 间”的字统计模型，并设计了字的编辑距离用来比较不同蛋白序列通过系统的比较分 析，对如何构建有效的“蛋白质空间”，如何选择合适的度量等问题提出了合理的建议 关键词：几何表示模型；马尔可夫模型；回归分析模型；字统计模型；生物序列的比较； 生物结构的比较 生物序列、结构比较中若干数学模型研究及应用 s e v e r a l b i o l m a t h e m a t i c a lm o d e l sf o rc o g i c a ls e q u e n c e s s t r u c t u r e s a p p l i c a t i o n s a b s t r a c t o m d a r l s o no t ， a n dt h e i r r e c e n t l y , m a j o ra d v a n c e so fg e n o m i ct e c h n o l o g i e sa n dt h ed e v e l o p m e n to fa n a l y t i c a lt e c h - n o l o g i e so fp h y s i c a ls t r u c t u r eh a v el e dt oa ne x p l o s i v eg r o w t ho fb i o l o g i c a ls e q u e n c ea n ds t r u c t u r e d a t a b a s e s t h ed e l u g eo fd a t a b a s e s ，i nt u r n ，p r o d u c e sn e wq u e s t i o n ss u c ha sh o wt oa n a l y z e ， p r o c e s sa n ds t o r et h e s ed a t a ，w h i c ha r es e r i o u sc h a l l e n g e st oc o m p u t e rs c i e n c e s ，m a t h e m a t i c s ，a n ds oo n m e a n w h i l e ，m a n yr e s e a r c h e r sw h os t u d ys c i e n c ea r ea t t r a c t e db yt h e s ec h a l l e n g e s a n dg e ti n t e r e s t e di nl i f es c i e n c e s t h u s ，c o m p u t a t i o n a lm o l e c u l a rb i o l o g ye m e r g e sa san e w a n dd e v e l o p i n gi n t e r d i s c i p l i n e t h er e s e a r c ha r e ao fc o m p u t a t i o n a lm o l e c u l a rb i o l o g yi sv e r y w i d e ，i ti n c l u d e ss e q u e n c ec o m p a r i s o n ，g e n er e c o g n i t i o n ，m o l e c u l a re v o l u t i o n ，c o m p a r a t i v eg e - n o m i e s ，r n aa n dp r o t e i ns e c o n d a r ys t r u c t u r ec o m p a r i o n ，a n ds oo n m o s to ft h e ma r eb a s e d o ns e q u e n c ea n ds t r u c t u r ec o m p a r i s o n s os e q u e n c ea n ds t r u c t u r ec o m p a r i s o ni sn o to n l yo n e o ft h em o s tb a s i ca n di m p o r t a n ts u b j e c t s ，b u ta l s oh a sf u r t h e re f f e c to nt h es t u d yo fl i f es c i e n c e t h i sd i s s e r t a t i o nm a i n l ys t u d i e sm a n ym a t h e m a t i c a lm o d e l si nt h i sa r e a ，t h em a i nr e s u l t sc a n b es u m m a r i z e da sf o l l o w s ： 1 i nc h a p t e r2 ，w ep r o p o s e daw - g e o m e t r i c a lr e p r e s e n t a t i o nm o d e lo fd n as e q u e n c e s ， a n dd e v e l o p e da ne f f i c i e n ta l g o r i t h mt os e a r c ht h es e c t i o ni ns e q u e n c ec o n t a i n i n go n l yp a r t i c u l a r b a s e s w i t ht h ec o n s i d e r a t i o no fd u a lb a s e s ，ap n n - g e o m e t r i c a lr e p r e s e n t a t i o nm o d e lw a s p r o p o s e db a s e do nt h ec o n c e p t so fc e l la n ds y s t e m ，a n da ne f f i c i e n tn u m e r i c a ld e s c r i p t o rw a s e x t r a c t e d t h ed e g r a d a t i o np h e n o m e n ao fd i s t a n c em a t r i c e sw h i l ec h a r a c t e r i z i n gc u r v e sw a s p o i n t e do u t i no r d e rt oo v e r c o m et h i sl i m i t a t i o n ，w ep r o v i d e dan e wm a t r i x ，c u r v a t u r em a t r i x 2 i nc h a p t e r3 ，t h em a r k o vm o d e lo fb i o l o g i c a ls e q u e n c e sa n ds t r u c t u r e sw a sc o n s t r u c t e d ， t h ed i f f e r e n c e so ft h ek - s t e pt r a n s i t i o np r o b a b i l i t ya sf o rn u m e r i c a lc h a r a c t e r i z a t i o no fb i o l o g i c a l s e q u e n c e sw e r ec o m p a r e d ，a n dt h i sm o d e lw a sa p p l i e dt os o m ef i e l d s ，s u c ha ss t r u c t u r a lc o m - p a r i s o n ，s t r u c t u r a ls i m i l a r i t ys e a r c ha n de v o l u t i o n a r ya n a l y s i s w i t ht h eh e l po ft h ew e i g h t e d r e l a t i v ee n t r o p y , w ec o n s t r u c t e dam i x e dm o d e lb a s e do nw o r ds t a t i s t i c a lm o d e la n dm a r k o v m o d e l ，e x p e r i m e n t a la s s e s s m e n t ，p e r f o r m e dv i aaw i d e l ye m p l o y e de v a l u a t i o nm e t h o d ，d e m o n s t r a t e st h a to u rm i x e dm o d e li m p r o v e dt h ea b i l i t yo fe x t r a c t i n gi n f o r m a t i o n 3 i nc h a p t e r4 。b a s e do nt h er a n d o mo ft h ed i s t r i b u t i o no fe l e m e n t so fb i o l o g i c a ls e q u e n c e s a n ds t r u c t u r e s ，t h er a n d o m d i s t r i b u t i o nf u n c t i o n sw e r ed e f i n e d u s i n gl i n e a rr e g r e s s i o nm o d e l ， w ec o u l df i n dt h er e l a t i o n s h i p so ft h e s ef u n c t i o n sa n dt h eh o l i s t i cc h a n g e so ft h ee l e m e n t s t h e s i m i l a r i t yb e t w e e nd i f f e r e n ts t r u c t u r e sc a nb eo b t a i n e db yc o m p a r i n gt h ed i f f e r e n c e sb e t w e e n i i t h e i rc o r r e s p o n d i n gl i n e 8 1 r e g r e s s i 。nm o d e l s t h e r e f o r e ，i tr e d u c e st h e c o m p l e x i t y 。fs t r u c t u r a l c o m p a r i s o n s 4 i nd l 印t e r5 ，t h ed e f i n i t i o no f p r o t e i ns p a c e ”a n dt h ek - w o r ds t a t i s t i c a lm o d e l o f ，d 胁 t e l ns p a c e ”w e 阳p r e s e n t e db a s e do i lt h es c o r em a t r i c e so fa m i n oa c i d s t h ee d i t d i s t a n c eo f k w 0 r dw a sd e s i g n e dt 。c o m p a r ed i f f e r e n tp r 。t e i n s e q u e n c e s b ys y s t e m i cc 。m p 龇a t i v ea n a l l y s i s r e a s o n a b l es u g g e s t i 。n so i lh o wt 。c 。n s t r u c te m c i e n t p r o t e i n s p a c e a n dh o t 。c h o o s e r e a s o n a b l e l r l e a s u r e sw e r ep r o p o s e d k e y w o r d s ：g r a p h i c a lr e p r e s e n t a t i 。nr o o d e l ；m a r k o vm o d e l ；l i n e a rr e g r e s s i 。nm o d e l ；w o r d 8 t a t i s t i c 出m 。d e l ；b i 。l 孵c 出s e q u e n c ec 。m p a r i s 。n ；b i 。l 。g i c a ls t r u c t u r ec 。m p a r i s 。n i i i 大连理工大学学位论文独创性声明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任。 学位论文题 作者签名： 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论 文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保 留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或 扫描等复制手段保存和汇编本学位论文 学位论文题 作者签名： 导师签名： 大连理工大学博士学位论文 1 绪论 1 1 生物序列、结构比较的研究背景 随着人类基因组计划和诸如大肠杆菌、结核杆菌、啤酒酵母、线虫、果蝇等其它一些 模式生物的基因组计划相继完成或全面实施，以及蛋白质测序技术和物质结构解析技术 的发展，使有关生物序列和结构的数据与日俱增然而，数据并不等于信息，更不等于 知识，但却是信息和知识的源泉面对海量的数据，如何对其进行科学的分析、处理和保 存给计算机科学、数学等学科提出严峻的挑战随着后基因组时代的到来，生物科学家 的研究重心将从单个基因和蛋白的研究转移到在整体水平上对功能的研究；研究手段也 从传统的观察和实验为主过渡到计算机辅助与特定的算法相结合现在，越来越多的科 学家已经认识到生命科学就是一门信息科学现在和将来，科学家们将着重于研究d n a 序列信息、蛋白质结构信息以及它们之间的相互作用为了破译每一水平的生物信息， 许多与基因或蛋白质有关的数学问题被相继提出，吸引了大量的数理科学工作者转入到 生命科学的研究领域中来，使得计算分子生物学和生物信息学应运而生【1 2 1 生物信息学广义的概念是指应用信息科学以及计算机科学的方法和技术，研究生物 体系和生物过程中信息的存储、信息的内涵和信息的传递，研究和分析生物体细胞、组 织、器官的生理、病理、药理过程中的各种生物信息【】具体包括对生物信息的获取、 加工、储存、分配、分析和释读，并综合运用数学、信息科学、计算机科学、系统科学和 生物学工具，以达到理解数据库中各种数据的生物学含义的目的生物信息学狭义的概 念是指应用信息科学的理论、方法和技术来管理、分析生物分子数据通过收集、组织、 管理生物分子数据，使研究人员能够迅速地获得和方便地使用相关信息；通过处理、分 析、挖掘生物分子数据，得到深层次的生物学知识，加深对生物世界的认识【铷1 计算分子生物学作为一门由现代信息科学、计算机科学、生命科学、数学、物理学 和化学等多学科互相渗透形成的崭新学科，主要研究分子生物应用上与基因和蛋白序列 有关的复杂计算问题主要课题有：序列组合、序列比较分析、结构比较分析、数据库搜 索、基因识别、种族树的构建及结构预测 计算分子生物学作为生物信息学的孪生学科，人们常常不加区别地使用这两个学科 名称严格来说，计算分子生物学和生物信息学这两个概念既有联系也有区别相对于生 物信息学，计算分子生物学更加偏重于算法的设计以及分析工具的开发，其主要关注于 生物序列、结构比较中若干数学模型研究及应用 分子生物学应用上具有一定计算复杂度的问题而生物信息学是一个大的概念范畴，往 往还包括对各种生物信息存储和查询的研究它们都具有重大的科学意义和巨大的经济 效益它们既属于基础研究，以探索生物科学的自然规律为己任；又属于应用研究，许多 研究成果可以较快或立即产业化，成为价值很高的产品计算分子生物学( 生物信息学) 的这一特点，在现有的许多学科中几乎是独一无二的普遍认为，计算分子生物学( 生物 信息学) 既是当前生命科学和自然科学领域中最关键、最重要的部分，也是2 1 世纪自然 科学的核心领域之一 计算分子生物学大量地在生物学中引入数学模型，这标志着生物学已经从实验科学 向理论科学转变对于生物学本身而言，这就是一次从量变到质变的飞跃随着计算分子 生物学中数学模型和算法的不断完善，产生了许多强有力的生物信息分析工具例如，数 据库搜索( 从包含已知结构和功能序列的数据库中查找与查询序列同源性较高的序列， 并用它们来研究查询序列的结构和功能) 、进化分析( 研究物种之间的进化信息，同时也 能够帮助药物学家决定哪些药物拥有共同的性质) 、聚类( 按照某种生物意义进行分类， 如果一些物种被划分为一类，可以通过它们来研究这个家族的公共特征和进化信息) 、代 谢途径分析( 进行代谢途径相关基因的同源性分析，以及获取其它生物代谢途径的相关 信息) 等，部分有效的分析工具极大地依赖于生物序列、结构的比较序列和结构的比较 是最重要和最常用的原始操作，是许多其它更复杂操作的基础因为对于d n a 序列，即 使考虑它的个很短的片断，我们也不可能直接得出它表示的对象所具有的全部信息， 然而如果比较不同的生物序列就有可能得到某些重要信息这个问题非常复杂，至今还 有许多未解决的问题总之，生物序列、结构的比较是计算分子生物学中最基本也是最 重要的课题之一，同时对生命科学的研究具有深远的意义 1 2 分子生物学的一些基础知识 下面简述本论文涉及到分子生物学方面的一些基础知识 细胞 细胞是生命的基本单位在形态上细胞大体上由细胞核、细胞质及细胞膜三部分组 成根据细胞核的区别，生物可以分为原核生物和真核生物两大类其中原核生物的核 物质没有被一层核膜所包围，而是散布在细胞质中，没有形成明显的细胞核，因此才被 称之为原核生物原核生物主要包括细菌和古细菌 d n a d n a 又称脱氧核糖核酸，是英文d e o x y r i b o n u c l e i ca c i d 的简称，它是一种高分子化合 物，可组成遗传指令，以引导生物发育与生命机能运作其基本单位是脱氧核苷酸，核 苷酸组成成分是磷酸基、戊糖和有机基d n a 包含的碱基有四种：腺嘌呤( a ) 、鸟嘌呤 ( g ) 、胞嘧啶( c ) 和胸腺嘧啶( t ) 许多个脱氧核苷酸经3 _ 5 磷酸二酯键聚合而成为 d n a 链d n a 链通常以线性或环状的形式存在多数d n a 分子是双链结构，两条链缠 2 大连理工大学博士学位论文 绕在一起形成双螺旋，此著名的双螺旋( d o u b l eh e l i x ) 结构是由w a t s o n 和c r i c k 在1 9 5 3 年发现的两条链结合的机制是一条链的碱基与另一条链的碱基配对，碱基a 与碱基t 配对，碱基c 与碱基g 配对只有少数d n a 以单链形式存在，如某些噬菌体或病毒 d n a 的一级结构是指四种核苷酸的连接及其排列顺序 r n a r n a 又称核糖核酸，是英语r i b o n u c l e i ca c i d 的缩写，它是细胞生物遗传信息的中间 载体，不但参与蛋白质合成，还参与基因表达调控对一部分病毒而言，r n a 是其唯一 的遗传信息载体r n a 是由核糖核苷酸经磷酸双酯键缩合而成的长链状分子一个核糖 核苷酸分子由磷酸、核糖和含氮碱基构成r n a 的碱基主要有四种：即腺嘌呤( a ) 、鸟 嘌呤( g ) 、胞嘧啶( c ) 和尿嘧啶( u ) 与d n a 不同的是，r n a 一般为单股长分子，但在 一般水溶液中会形成分子内双螺旋结构此外，r n a 本身也需要通过碱基配对原则形成 一定的二级结构乃至三级结构来行使生物学功能r n a 的碱基配对规则基本上和d n a 相同，不过其中尿嘧啶在配对上的作用，相当于d n a 中的胸腺嘧啶 r n a 分子有三类结构信息；其一是r n a 一级结构，它是由碱基a 、u 、g 和c 组成的单链；其二是三级结构，它是碱基序列自身折叠形成的双螺旋空间结构r n a 二 级结构是三级结构的严格子集，它在一级结构和三级结构之间起着重要的作用，即起着 由r n a 一级结构推测三级结构的桥梁作用因此，r n a 二级结构有着非常重要的研究 价值，并且可以应用于诸如t r n a 和蛋白质的相互作用、m r n a 的稳定化处理以及r n a 干涉过程中【7 ，8 1 蛋白质 蛋白质( p r o t e i n ) 是由许多氨基酸聚合而成的生物大分子化合物，为生命的最基本物 质之一蛋白质广泛存在于各种生物组织细胞中，是生物细胞最重要的组成物质蛋白 质的种类很多，性质、功能各异，但都是由2 0 多种氨基酸通过肽键相连而成的，因氨基 酸的组合排列不同而组成各种类型的蛋白质蛋白质的一级结构决定了蛋白质的高级结 构，因此在测定了蛋白质一级结构后，就可能推测蛋白质的高级结构而分子结构又决定 了其功能，所以研究蛋白质的结构就很重要蛋白质的结构通常分为六个级别：一级结 构、二级结构、超二级结构、三级结构、四级结构及分子缔合体一级结构指的是蛋白质 序列；二级结构为蛋白质中多肽主链的规则排布；超二级结构为二级结构单元间的组合 方式；三级结构指蛋白质的三维空间结构；四级结构则是指蛋白质亚基间的相互作用 蛋白质的二级结构是从x 射线晶体衍射或核磁共振等物理手段解析出来的蛋白质分 子三维结构中的原子坐标出发，通过考察主链c q 碳原子的邻接位置关系而定义的蛋白 质的主链结构基于氢键模式和几何特征定义的“蛋白质二级结构辞典”( d s s p ) 是应用 最广泛的一种蛋白质二级结构定义它定义了八种类型的二级结构，分别为h ( a h e l i x 或 4 - h e l i x ) 、b ( f l - b r i d g e ) 、e ( f l - s t r a n d ) 、g ( 3 1 0 一h e l i x ) 、i ( 7 r - h e l i x 或5 - h e l i x ) 、t ( f l - t u r n ) 、 s ( b e n d ) 和c ( c o i l ) 另外，还有其它的定义方式在蛋白质二级结构预测中，通常将上述 八种类型归并为e 、h 、c 三种常用的归并方法有两种：( i ) e 和b 归为e ，g 和h 3 生物序列、结构比较中若干数学模型研究及应用 归为h ，其余归为c ；( i i ) e 归为e ，h 归为h ，其余归为c 在这两种方法中，又以 第一种方法最为常用 中心法则和遗传密码 c r i c k 于1 9 5 4 年提出了遗传信息传递的规律，d n a 携带遗传材料，即生物功能所 要求的信息( 某些病毒除外，它们的遗传材料是r n a ) d n a 分子中的遗传信息转录 ( t r a n s c r i p t i o n ) 到r n a 分子中( 即r n a 聚合酶以d n a 为模板合成r n a ) ，再由r n a 翻 译( t r a n s l a t i o n ) 生成体内各种蛋白质，行使特定的生物功能分子生物学家称之为中心法 则( c e n t r a ld o g m a ) 此外，生物界还存在由r n a 指导下的c d n a 合成过程，即逆转录， 这一过程发现于逆转录病毒中经过n i r e n b e r g 和m a t t h a i ( 1 9 6 3 ) 的努力研究，编码2 0 种 氨基酸的遗传密码得到了破译在翻译过程中，每三个碱基构成一个三联体，对应一个 氨基酸或者一个终止密码子，我们称这种对应为遗传编码 1 3 生物序列、结构比较中数学模型的研究概况 生物序列、结构的比较是计算分子生物学中最基本、最重要的部分它的基本思想 是基于分子生物学中的一条经验规则，即当两个分子享有相似的序列或结构时，由于进 化关系或者物理化学限制，它们将很有可能具有相似的三维结构和生物学功能因此， 生物序列、结构分析的首要任务是通过比较不同生物的序列、结构，找出可以扩展到功 能性质的序列或结构特征，从而阐明或长或短的字符序列及结构的生物学意义 从处理对象上看，生物序列比较主要包含核酸序列或蛋白序列的比较，而结构的比 较主要指r n a 二级结构和蛋白质结构的比较序列分析的核心就是序列的比较，这包括 同一序列内不同片段的比较，以及两个或多个序列之间的比较比较的内容，从序列组分 的变化，寻找特殊字段，到序列间字母的对应比较的主要目的在于阐明序列之间的同 源关系，以及从已知序列预测新序列的结构和功能由于生物的结构比其序列更保守， 序列变化不一定会改变结构，即相似的结构可能具有不同的序列，但相似的结构往往具 有相似的功能，因此结构比较更受重视另外，结构比较还为低序列相似性的生物序列 同源性和进化分析提供了有力工具 近年来，各种数学模型被引入到该领域中来解决不同的问题由于名目繁多，这里 只能是挂一漏万由于篇幅有限，所有模型不可能面面俱到，很多模型都是点到为止， 描述稍多的，也只侧重于交待基本思想到目前为止，这些数学模型没有得到合理的分 类，在此，我们按照所处理的对象对其进行分类，未必恰当其目的是凸显不同数学模 型在处理不同问题中出现的频繁程度 1 3 1 生物序列比较中数学模型的研究概况 生物序列一般是指d n a 、r n a 或蛋白质的一级序列，它们都是线性的，由四种碱 基或者2 0 种氨基酸排列组成因此在具体的研究中，它们常被视为线性字符串，对它们 的比较实际上就是对字符串的比较到目前为止，已经有大量的数学模型被提出： 4 大连理工大学博士学位论文 1 比对模型 序列比对是寻找序列相似性的过程，前提是找到一种最佳的比对方式，即使字符的 匹配数目最大，或者是，使两条序列间相互转换时所需要的编辑操作( 替换、插入或删除) 的次数最少的比对方式这在具体实现时往往表现为，对给定的打分函数进行优化的问 题序列比对中，为了度量两条序列之间的相似性，有时要考虑序列中字符之间的替代 关系，这通常由“突变矩降( m u t a t i o nm a t r i x ) 或叫打分矩阵 给出核酸序列比对时， 通常不使用打分矩阵，但是也允许使用一些简单打分矩阵例如，b l a s t n 程序蛋白 序列比对一般都会使用打分矩阵，有两个系列可供选择：p a m 系列 9 1 和b l o s u m 系列 ，其中尤以p a m 2 5 0 和b l o s u m 6 2 最为常用按照比对的序列数目，序列比对可分 为：双序列比对( p a i r w i s 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 ) ；按比 对的区域大小和优先次序，可以分为全局比对和局部比对 最早出现的用于双序列比对的方法是“d o tm a t r i x ，它是g i b b s 和m c i n t y r e 在1 9 7 0 年提出的一种可视化的方法【1 1 】，该方法可用于两条不同序列或序列与自身之间的比对， 并以直观的形式显示比对结果后来，在1 9 8 1 年，m a i z e l 和l e n k 使用了各种过滤和颜 色显示表，大大增强了该方法的实用性【1 2 】经典的比对模型是基于动态规划算法动态 规划算法的指导思想就是在多级过程的每一级上列出各种可行的局部解释，然后按照某 种条件舍弃那些肯定不能得到最优解的局部解该方法由n e e d l e m a n 和w u n s c h 提出，最 初用于求两个序列的全局最佳比对【1 3 】给定两个序列s 1 和函，算法不是直接确定既 和& 的整体相似性，而是建立在确定两个序列任意前缀的相似性上我们从最短前缀开 始，利用先前的计算结果求解更大前缀的相似性全局序列比对算法的缺点是：在一些局 部序列相似性较高而全序列相似性很小的情况下，前者常被后者的平均值效应所掩盖， 其同源性不易被发现后来，s m i t h 和w a t e r m a n 通过对n e e d l e m a n - w u n s c h 算法进行修 改，提出了寻找两个被比较序列的“最类似片段的局部序列比对方法【1 4 1 这种方法和 n e e d l e m a n - w u n s c h 算法的主要区别之处在于：( i ) 替代矩阵中必须包含负值；( i i ) 转化矩 阵中所计算的最小积分值为0 ；( i i i ) 优化路径可以在积分矩阵的任何一个位置终止，而 不是仅仅在最后一行或最后一列终止虽然，动态规划方法利用递推减少了运算量，有 效地抑制了计算量的组合爆炸，但其计算量仍正比于2 ，是问题规模的大小，比如 序列长度因此，在很长的时间里，人们无法使用此方法实现序列比对因此，比对算法 便开始向其它方法转变，如遗传算法1 1 5 】、模拟退火算法f 1 6 】和启发式算法等 f a s t a 算法【1 7 1 、b l a s t 算法【1 8 】及c l u s t a l 算法f 1 9 1 等属于比较好的启发式算 法f a s t a 算法是l i p m a n 和p e a r s o n 在1 9 8 5 年提出的双序列比对启发式算法，用于搜 索与待查询序列相匹配的很短的序列片断f a s t a 首先要建立一个所有可能的字典，执 行对序列库的快速初检，找出与待检序列高度相似的序列，然后采用全局动态规划算法 进行空位联配计算，得出分析的最后结论后来，在1 9 8 8 年，p e a r s o n 等人利用改进了 的w l l b u r l i p m a n 算法改进了此算法，使得算法能够集中反映具有显著意义的比对结果 f 2 0 】b l a s t 算法是a l t s c h u l 等人在1 9 9 0 年提出的双序列比对算法，历经几次改进，在 5 生物序列、结构比较中若干数学模型研究及应用 1 9 9 6 年由美国国立生物信息技术中心( n c b i ) 支持成为网络工具它首先寻找在两条序 列中都出现的字母块，然后试图扩展匹配的区域，直至打分函数的分值不再增加为止 b l a s t 的一项重要特性就是它利用极值分布的概念进行匹配序列的统计学显著性评分， 这是由k a r l i n - a l t s c h u l 算法实现的一般认为，b l a s t 运行较快，对蛋白序列的搜 寻更为有效；f a s t a 运行较慢，对核酸序列更为敏感后来不少学者致力于比对启发式 算法的改进，例如，a l t s c h u l a 在1 9 9 7 年提出的一个通过寻找蛋白质家族保守序列来提 高比对算法敏感性的算法一p s i - b l a s t ( p o s i t i o n - s p e c i f i ci t e r a t e db l a s t ) 2 2 j 算法，它在 原来的b l a s t 算法中增加了插入空位( g a p e d ) 和位置特异的迭代功能，从而成为目前 b l a s t 程序家族中敏感性最高的成员；由华盛顿大学的一个研究小组开发的相似性搜索 软件w u - b l a s t 2 0 ，利用k a r l i n - a l t s e h u l 和”统计量【2 3 】进行多相似区域的联合概率求 值，精选的统计量和启发式方法的结合使得w u - b l a s t 更灵敏；另外，南开大学的沈世 锰在2 0 0 2 年提出了s p a 比对算法【2 4 】，它使计算速度得到了很大的提高多重序列比对 比双序列比对的运算量大，因此更加困难，而且应用的规模也受到很大的限制常用的 多序列比对软件有c l u s t a l 系列【1 9 】和t c o 行碗【2 引为了确保序列比对找到的相似性有真 正的生物学意义，还要用比对分数的统计学特性来评估比对的可信性，即计算比对的统 计置信度 2 1 1 2 几何表示模型 以字符形式表示的生物序列，在发表、存储和提供计算机进行快速分析等方面具有 不容争议的优点，因而被广泛使用但是随着计算机技术的发展和可视化要求的提高， 它固有的缺点也随之暴露出来在生物序列的研究分析中，若能把生物序列转换成适当 的直观图象，让人眼参与比较和识别，则往往会收到事半功倍的效果基于这种思想， h a m o r i 和r u s k i n 在1 9 8 3 年，提出d n a 序列的h 曲线几何表示模型，该曲线形象地将 d n a 序列以图形的方式表示出来，实现了人眼参与直观比较【2 6 】例如，通过h 曲线， 局部的或整体的序列变化可以通过整个图形很容易被发现后来这一思想在研究领域迅 速渗透自此国内外不少专家学者如张春霆、郭晓峰、r a n d i 6 、n a n d y 以及廖波等人提 出了众多的几何表示模型 2 7 - 4 s 1 利用几何表示模型，r a n d i 等人试图寻找一些模型的 刻画量来刻画生物序列，进而比较它们的相似性，并取得较好的结果我国著名理论物 理专家张春霆院士也提出了一种d n a 序列的几何表示模型z 曲线【4 阳8 1 张春霆等人 建议用正六面体来表达碱基之间的对称性关系，并指出在正六面体的一个内接正四面体 内存在一点，该点的坐标恰好构成四种核苷酸频率归一化后三个独立参数的一种表示方 式他们还利用z 曲线研究了真核和原核基因组中若干重要问题，证明这样的思路是切 实可行的例如，在基因识别问题中，传统的方法是分别计算编码和非编码序列中大量 的概率和条件概率，通过对这些概率的比较来区别它们而他们则通过对编码与非编码 序列的z 曲线的比较来区别它们，方法既简单，效果又好随着不曲线系列软件【4 9 5 0 1 的推出，其影响越来越大，受到学术界越来越多的关注这种独树一帜别开生面的研究 思路己经得到国内外学术界的普遍好评和认可 6 大连理工大学博士学位论文 3 字统计模型 生物序列可以看作由四种碱基或者2 0 种氨基酸排列组成的线性序列，这四种核酸或 2 0 种氨基酸可以看成字母表集合例如，对d n a 序列来说，= a ，c ，g ，t ) 若 s = 8 1 s 2 s n ，s k 为长度为n 的生物序列，则s j + 1 s j + k 为序列s 的长度为k 的 子序列，称为k 一字，其中s j ，0 j 几一k 且k 几字统计主要是统计b 字在 序列中出现的频率所选字的长度依方法的不同而不同，可以是长度为2 的，也可以是 长度为3 的，也可以是多种长度的一起考虑这些长度为k 的字在序列中出现的频 率组成一个频率向量，被用来表征序列在1 9 8 6 年，b l a i s d e n 提出了一种基于字统计模 型的序列比较方法，通过计算频率向量的欧氏距离来量化序列之间的差异【5 1 j 现有字统 计模型有很多，它们的不同之处主要体现在向量和距离的定义常用的距离有欧氏距离 1 5 1 j 、m a h a l a n o b i s 距离( 协方差距离) f 5 2 】、夹角距离等侧普遍认为，m a h a l a n o b i s 距离 的灵敏度比较好，其次是欧氏距离另外还有基于信息论的度量，如k u l l b a c k - l e i b l e r 偏 差法删和p e a r s o n 相关系数【5 5 】等 4 马尔可夫模型 马尔可夫模型可以用来描述离散随机过程初始状态概率和转移概率都是模型的参 数，其数目由状态的个数和模型的阶数共同决定对于生物序列，将4 种碱基或者2 0 种 氨基酸看作4 种或2 0 种状态，则生物序列可以被看作是一个随机过程进而假设当前 碱基出现的概率只和前一个碱基有关系，根据马尔可夫性，便可以运用马尔可夫链来描 述生物序列对于d n a 序列来说，一阶马尔可夫链有4 个初始状态概率和1 6 个转移概 率，归一化后，共有1 5 ( = 3 + 1 2 ) 个独立参数3 核苷酸的2 阶马尔可夫链共有1 5 + 4 8 = 6 3 个独立的参数一般地，计算k 长d n a 字符串的( k 一1 ) 阶马尔可夫模型的初始状态概 率和转移概率，共需要确定4 1 1 个独立参数目前，许多寻找基因的程序中使用的5 阶马尔可夫链对应于k = 6 ，共有1 6 3 8 5 个参数，主要刻画d n a 序列中六核苷酸的统计 特征以上所讨论独立参数的数目，是针对齐次马尔可夫模型的，若模型为非齐次，即 转移概率与位置有关，则参数的数目还会增加一般说来，参数越多，需要的训练集就 越大齐次马尔可夫模型常用于描述非编码区，周期3 的非齐次模型则被用来描述编码 区【6 5 】后来，不少学者运用马尔可夫模型来比较生物序列例如，在马尔可夫模型的背 景下，通过度量两个序列的七字的匹配程度来作为两个序列的相似性分值1 5 7 ，鼹】，或者 计算两个生物序列对应的马尔可夫模型差异来比较两个生物序列【5 9 】 5 隐马尔可夫模型 隐马尔可夫模型，是一个双重的随机过程，其中一个过程服从马尔可夫模型，它是 不能直接观察的隐过程，但同时却控制( 或影响) 另一个随机过程，而后者则生成可观察 到的符号序列设为隐过程的状态个数，s = s 1 ，s 2 ，s n ) 为状态集合又用吼记 时刻t 时的状态设矩阵a = 【a i j n n ，其中a i j = p ( q t + 1 = s j i q , = & ) ，即状态转移的 概率矩阵设m 为可观察的符号个数，v = ，) 为所用符号的字母集设 b = b j ( k ) n m ，其中b j ( k ) = p ( o = k i q , = s j ) ，即当隐过程于时刻t 的状态为岛时可 7 生物序列、结构比较中若干数学模型研究及应用 观察符号的概率分布又设丌= l r i ) ，其中7 r i = p ( q 1 = & ) ( 1 i n ) 为初始状态分 布这样，一个隐马尔可夫模型可以简记为a = ( a ，b ，丌) 隐马尔可夫模型有三个基本问 题，即评估问题、解码问题和学习问题，分别用向前算法、韦特比( v i t e r b i ) 算法和向前 向后算法来解决隐马尔可夫模型的早期应用主要是在语音识别领域从2 0 世纪8 0 年 代后期起，人们开始将隐马尔可夫模型拓展应用于生物序列分析目前隐马尔可夫模型 在生物信息学的一系列问题都得到成功应用，例如，多序列比对、基因识别和蛋 白质二级结构预测【6 2 l 等在基因识别中，一般选取编码、非编码、编码之补等状态作为 隐含状态，而观察值就是四种核苷酸a 、c 、g 和t 从d n a 序列中识别出编码区 的问题，实际上就是一个解码问题，用韦特比算法求解近年来，隐马尔可夫模型已成 为基因识别领域的主流算法，著名的基因识别软件g l i m m e r 系列1 6 4 ，9 1 】和g