（基础数学专业论文）生物分子数据的距离度量及其应用.pdf

大连理工大学博士学位论文 摘要 生物分子数据的比较是生物信息学最基本最重要的工具之一。通过序列比较，我 们可以从大量的序列数据中获取生物序列中的功能、结构和进化信息。生物信息学的 许多其它领域，如数据库搜索，系统树构建，蛋白质结构和功能的预测，序列片段的 拼接等都需要首先确定生物序列间的距离度量。目前广泛使用的序列比较方法是比 对，然而该方法存在着计算复杂度高，对序列进化模型的假设较为苛刻等缺陷。因 此，发展有效的不依赖于比对的序列比较方法，并探讨其在生物信息学其它领域中的 应用，特别是基于全基因组的系统发育分析，是一个非常有意义的课题。 本文就两类常用的“非比对 序列比较方法进行了探讨。论文的主要内容安排如 下： 第二章给出了两种基于序列中字符串出现频率的序列比较方法。第一种方法是对 经典相对熵方法的修正，该方法可以避免相对熵在确定两个字频率向量距离时，由于 字符类型缺失而导致的退化现象。第二种方法在字出现次数服从p o i s s o n 分布的假设 下，我们定义了字的表达水平，用字表达水平的差异来刻画两条序列之间的距离。通 过构建包含s a r s c o v 在内的2 5 个病毒全基因组的系统发生树，上述方法的有效性得 以验证。 第三章研究了基于符号序列复杂度的距离度量。该距离度量利用两条序列条件压 缩的思想，对序列的进化模型假设较少，因此一些进化操作，如基因组重排等，对此 度量影响较小。作为其应用，我们将其与k 近邻算法结合，预测了蛋白质的亚细胞位 点。另外，对于蛋白质结构的比较，我们提出了一种“符号化指派 的方法，可将蛋 白质结构的比较转换为符号序列的比较。同样利用此度量，我们构建了2 4 个蛋白质结 构的相似性树。 特征序列是d n a 序列的一种粗粒化描述，对特征序列的研究可以从不同的角度反 映初始d n a 序列中所含的生物信息。在本文的最后一章，通过构建3 个常用数据集的 种系发生树，我们对三种特征序列所含进化信息进行了探讨。 关键词：生物信息学；距离度量；系统发育分析；亚细胞位点预测；序列复杂度 生物分子数据的距离度量及其应用 d i s t a n c em e a s u r e so fb i o l o g i c a lm o l e c u l a rd a t aa n dt h e i ra p p l i c a t i o n s a b s t r a c t c o m p a r i s o no fb i o l o g i c a lm o l e c u l a rd a t ai so n eo ft h em o s tf u n d a m e n t a la n di m p o r - t a u tt a s k si nb i o i n f o r m a t i c s 。t h r o u g ht h ec o m p a r i s o no fm o l e c u l a rs e q u e n c e s ，o n ec a n o b t a i ns o m ef u n c t i o n a l ，s t r u c t u r a la n de v o l u t i o n a r yi n f o r m a t i o na b o u tt h ec o r r e s p o n d i n g s e q u e n c e s m a n yo t h e rr e s e a r c h a r e a si nb i o i n f o r m a t i c s ，s u c ha sd a t a b a s es e a r c h ，p h y l o - g e n e t i ct r e ec o n s t r u c t i o n ，p r e d i c t i o no fs t r u c t u r ea n df u n c t i o no fp r o t e i n s ，d n as e q u e n c e a s s e m b l y , a l ln e e df i r s tt oe s t i m a t et h es i m i l a r i t yb e t w e e ns e q u e n c e s t r a d i t i o n a la p p r o a c h t oa c h i e v et h i sa i mi ss e q u e n c ea l i g n m e n t b u tt h i sm e t h o ds u f f e r sf r o mt h ed r a w b a c ko f h i g hc o m p u t a t i o n a ll o a da n d i n h e r e n ta m b i g u i t yo ft h ea l i g n m e n tc o s tc r i t e r i a s ot h e r e i sag r e a tn e e dt od e v e l o pn e ws e q u e n c ec o m p a r i s o n sf r e eo fa l i g n m e n t a n di n v e s t i g a t e t h e i ru s ei no t h e rb i o i n f o r m a t i c sa r e a s ，e s p e c i a l l yw h o l eg e n o m ep h y l o g e n e t i ca n a l y s i s i nt h i sd i s s e r t a t i o n ，w ef o c u so nt w om a i nc a t e g o r i e so fa l i g n m e n t f r e es e q u e n c ec o m - p a r i s o n s t h em a i nc o n t e n t sa r ea r r a n g e da sf o l l o w s i nc h a p t e r2 ，w es t u d yt w od i s t a n c em e a s u r e sb a s e do nt h ef r e q u e n c i e ss t a t i s t i c s o fs h o r ts t r i n g si nb i o l o g i c a ls e q u e n c e s t h ef i r s tc a ub ec o n s i d e r e da sar e v i s i o no ft h e c l a s s i c a lr e l a t i v ee n t r o p y ( r e ) t h i sm e t h o da v o i d st h ed e g e n e r a c ya c c o m p a n i e db yt h e a b s e n to fs o m ew o r d sw h e nu s i n gr et om e a s u r ed i s t a n c e i nt h es e c o n da p p r o a c h ，u n d e r t h ep o i s s o nm o d e lo ft h ew o r do c c u r r e n c e s ，w ed e f i n e dt h e e x p r e s s i o nl e v e l ”o fa ni n d i v i d u a lw o r d t h e nt h ed i s t a n c eb e t w e e nt w os e q u e n c e si se v a l u a t e db yt h ed i s c r e p a n c yo f e a c hw o r di nt h e s et w o s e q u e n c e s t h ev a l i d i t yo fo u ra p p r o a c h e si ss h o w nb yc o n s t r u c t i n g t h ep h y l o g e n e t i ct r e eo f2 5v i r u s e si n c l u d i n gs a r s c o v s i nc h a p t e r3 ，w ei n v e s t i g a t ead i s t a n c em e t r i cb a s e do nt h ec o m p l e x i t yo fs y m b o l s e q u e n c e s t h i sm e t r i cu s e st h es a v i n gi nj o i n tc o m p r e s s i o na sam e a s u r eo fd i s t a n c e b e t w e e n t w os e q u e n c e s ，a n dm a k e sf e wa s s u m p t i o no nt h ee v o l u t i o n a r ym o d e l t h e r e f o r e ， i td o e sn o ts u f f e rg r e a t l yf r o ms o m ee v o l u t i o n a r ye v e n t s ，e g ，l a r g er e a r r a n g e m e n t sa n d t r a n s p o s o na c t i v i t y a si t sa p p l i c a t i o n ，w ec o n s t r u c tt h ee v o l u t i o n a r yt r e eo f2 4p r o t e i n s t r u c t u r e sa n dp r e d i c tt h ep r o t e i ns u b c e u u l a rl o c a t i o no f3w i d e l yu s e dd a t as e t s a d d i - t i o n a l l y , a st ot h ec o m p a r i s o no fp r o t e i ns t r u c t u r e s ，w ep r o p o s ea s y m b o la s s i g n m e n t a p p r o a c h ，w h i c hc a nt r a n s l a t ep r o t e i ns t r u c t u r e si n t os y m b o ls e q u e n c e s c h a r a c t e r i s t i cs e q u e n c ei sac o a r s e g r a i nd e s c r i p t i o no ft h ep r i m a r yd n as e q u e n c e 大连理工大学博士学位论文 o b v i o u s l y , a ni n d i v i d u a lc h a r a c t e r i s t i cs e q u e n c ew i l lk e e ps o m eb i o l o g i c a li n f o r m a t i o na n d l o s eo t h e r s b u tw h a tk i n da n dh o wm u c ha l li n d i v i d u a lb i n a r ys e q u e n c ec a r r i e s ? i nt h e l a s tc h a p t e r ，w eg i v e8 1 18 2 1 s w e rf r o mt h ee v o l u t i o n a r yp e r s p e c t i v et h r o u g hc o n s t r u c t i n g t h ep h y l o g e n e t i ct r e e so ft h r e ed a t as e t s k e yw o r d s ：b i o i n f o r m a t i c s ；d i s t a n c em e a s u r e ；p h y l o g e n e t i ca n a l y s i s ；p r o t e i ns u b c e l - l u l a rl o c a t i o np r e d i c t i o n ；s e q u e n c ec o m p l e x i t y 1 1 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：生遗垒多垫堡坚照壶查差垒壅左! 叠 作者签名：五p l 吼半上月上日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：生煎堡量塾监鱼受垦墨查量垒蔓垂! 叠 蚀善敛矽翔小壤 作者签名：尘2 ：! ! 三垒 导师签名：雾 6 7 日期：2 ：l 年月三日 日期：等l 年月兰日 大连理工大学博士学位论文 1 绪论 本章简要介绍了所研究问题的背景和现状，主要包括生物信息学的研究对象和主 要研究领域，常用的生物序列比较方法及其在生物信息学其它领域中的应用等。最后 介绍了本文的主要工作和论文安排。 1 1 生物信息学概论 1 1 1 生物信息学产生的背景 2 0 世纪5 0 年代之前，遗传信息的研究都是基于物种的外部形态特征或解剖学特 征，如孟德尔的豌豆实验，达尔文物种进化论的提出等。随着人类认识世界能力的逐 渐提高，许多物理化学实验、计算机技术等应用到生物学研究中来，使得人们可以从 微观层次上来研究生命现象。1 9 5 3 年，d n a 双螺旋三维结构和碱基互补配对理论的提 出，奠定了分子生物学蓬勃发展的基础，也标志着人们对于生物学的研究进入了一个 新纪元。人们认识到，地球上所有的生命形态，从万吨重的巨鲸，到肉眼看不到的细 菌、病毒，从万物之灵的人类，到花草树木，它们所有的遗传信息都储存在d n a ( 或 r n a ) 中。这些遗传信息以d n a 中四种碱基腺嘌呤( a ) 、鸟嘌呤( g ) 、胞嘧啶( c ) 和 胸腺嘧啶( t 1 的不同排列形式而存在，以d n a 的复制得以保存和遗传，以转录和翻译 为蛋白质来行使其生物功能。 2 0 世纪后期，许多分子生物学实验技术不断涌现和完善，如凝胶电泳、杂交、 克隆技术、聚合酶链式反应等d n a 分子提取工具，链终止法等d n a 测序工具。 这些方法为基因数据提取、自动化大规模测序、片段拼接提供了技术上的支持， 为基因组测序工作奠定了基础。从2 0 世纪8 0 年代末f 以h g p 的启动为标志) 到 现在，是生物分子数据的快速积累期，2 0 0 0 年6 月2 6 日，人类基因组草图绘制完 毕：2 0 0 3 年4 月1 4 日，美、英、日、法、德和中国科学家经过1 3 年努力终于完 成了人类基因组计划f h u m a ng e n o m ep r o j e c t ，h g p ) 。同时，模式生物基因组计划 ( m o d e lo r g a n i s mg e n o m ep r o j e c t ，m o g p ) 已完成了大肠埃希氏菌( e s c h e r i c h i ac o n ) 、 流感嗜血杆菌f h a e m o p h i l u si n f l u e n z a e ) 、酿酒酵母f s a c c h a r o m y c e sc e r e v i s i a e ) 、秀丽 线虫f c a e n o r h a b d i t i se l e g a n s ) 、果蝇( d r o s o p h i l am e l a n o g a s t e r ) 、拟南芥( a r a b i d o p s i s t h a l i a n a ) 的基因组序列测定和图谱绘制等工作。另外，小鼠f m u sm u s c u l u s ) 等哺乳动 物基因组计划也取得了很大进展。人类和其它模式生物基因组计划的实施给人们带来 了海量的数据，据统计从1 9 8 2 年至今，美国g e n b a n k 数据库的碱基数目大约每1 8 个 月翻一番。2 0 0 8 年1 2 月发布的第1 6 9 0 版g e n b a n k 中，d n a 序列总量已经超过了 9 9 0 亿个碱基，所有数据文件总的大小为4 0 7 g 比特。序列的积累不仅仅体现在d n a 序列方面，与其同步的还有蛋白质序列、结构数据等。 1 生物分子数据的距离度量及其应用 然而，得到上述分子数据只是理解复杂生命现象的第一步。随后更加艰巨的工作 就是对这些海量的数据进行存储、处理、分析和解释，并在此基础理解生命的物质基 础，探索固有的生物学规律，进而破译生命的奥秘。这就不是单个学科领域、小部分 人可以完成的工作，而是需要综合利用数学、计算机科学与系统科学、信息科学等学 科领域中的理论和方法，更需要世界各国的科学家共同的努力。因而产生了一门新的 交叉学科一一生物信息学f 或称计算生物学) 。它是现代生命科学与信息科学、计算机 科学、数学、物理和化学等学科相互渗透而形成的交叉学科，是应用计算机技术和信 息论的方法研究蛋白质及核酸序列等生物数据的采集、存储、传递、检索、分析和解 读，以帮助了解生物学和遗传学信息的科学。目前，生物信息学已经成为生命科学和 生物技术研发的必要工具，在生物学、医学、药物学、农学和环境科学等领域都发挥 了巨大的作用，是当今生命科学和自然科学的核心领域中最具活力的前沿领域之一。 1 1 2 生物信息学的研究对象 核酸 核酸是最主要的遗传物质，它是由称为核苷酸( n u c l e o t i d e ) 的小分子生成的聚合 物。核苷酸还可以进一步分解成核苷( n u c l e o s i d e ) 和磷酸，核苷进一步水解生成碱基 ( b a s e ) 和戊糖。所以，核酸的基本结构单位是核苷酸，其组成方式为碱基一戊糖一磷 酸。 核酸可分为脱氧核糖核酸( d n a ) 和核糖核酸( r n a ) 。它们之间的不同主要 体现在所含的戊糖不同：d n a 中的戊糖是脱氧核糖，而r n a 中的则是核糖。d n a 和r n a 在组成上的另一个区别体现在它们所含的碱基组成上。d n a 中的碱基有4 种，分别是腺嘌呤( a d e n i n e ，简写作a ) 、鸟嘌呤( g u a n i n e ，简写作g ) 、胞嘧啶 ( c y t o s i n e ，简写作c ) 和胸腺嘧啶( t h y m i n e ，简写作t ) 。r n a 中没有胸腺嘧啶 t ，取而代之的是尿嘧啶u ( u r a c i l ) 。d n a 主要存在于细胞核中，但也有少量的 d n a 存在于细胞质里的线粒体、叶绿体中，r n a 则主要分布在细胞质中。 可见，仅就d n a 或者r n a 分子而言，不同核苷酸之间的区别仅在于它们所含的 碱基不同。因此，a 、g 、c 、t ( u ) 也常被用来直接表示相应的核苷酸。核苷酸相互 连接形成长的多核苷酸链。由四种脱氧核苷酸连接而成的长链高分子多聚体为d n a 分 子的一级结构。d n a 分子中第一个核苷酸的3 ，一羟基与第二个核苷酸的5 ，一磷酸基脱水 形成3 ，5 ，磷酸二酯键，第二个核苷酸的3 ，一羟基又与第三个核苷酸的磷酸基脱水形成 3 ，5 ，磷酸二酯键，依此类推，形成线性多聚体。d n a 分子中第一个核苷酸的5 7 磷酸 与最末一个核苷酸的3 ，羟基都未参与形成3 ，5 ，一磷酸二酯键，故分别称为5 一磷酸端( 或 5 ，端) 和3 ，羟基端f 或3 ，- 端) 。 d n a 复制机制的关键是碱基的互补配对原则，即a 与t 配对，g 与c 配对。这 种配对是由于氢键作用，原理是d n a 单链( 按从5 ，到3 ，的次序) 与相反方向写的互补 2 大连理工大学博士学位论文 链配对。例如，单链碱基序列5 7 一a t g g t g c a c c 3 7 和3 7 t a c c a c g t g g 5 7 配对： 5 7 一 a tgg t i i 3 7一tacca gcac c一3 llj cgt g g一5 7 蛋白质 蛋白质是生物体的基本构件，也是生命活动的重要物质基础，几乎一切生命现象 都要通过蛋白质的结构与功能来体现。因此，在分子生物学中，深刻阐明蛋白质的结 构与功能，是探索生命奥秘最基本的任务。 蛋白质是由氨基酸( a m i n oa c i d ) 聚合而成的生物大分子。氨基酸是带有氨基的有机 酸，它的中心碳原子特称为q 碳( c a ) 。q 有四个键，分别连着一个氨基( n h 2 ) ，一个 羧基( c o o h ) ，一个氢原子和一个r 基团( 如图1 1 ) 。各种q 氨基酸的区别在于侧链r 基团不同，r 基团的特异性使不同氨基酸显示出不同的理化性质，进而决定了氨基酸 在蛋白质分子的空间结构中可能的位置。在蛋白质合成时，一个氨基酸的羧基和另一 个氨基酸的氨基缩水形成肽键f p e p t i d eb o n d ) 。所以，蛋白质也是有方向的一维链，带 氨基的一头称为端或记为，另一头带羧基称为c 端，常用c 7 表示。自然界中的 氨基酸种类很多，但参与蛋白质组成的常见氨基酸只有2 0 种。这2 0 种标准氨基酸的 英文三字母和单字母表示见表1 1 。 表1 12 0 种标准氨基酸的三字母和单字母表示 中心法则 d n a 携带遗传材料，即生物功能所要求的信息f 某些病毒除外，它们的遗传材料 是r n a ) 。信息从基因的核苷酸序列中被提取出来，用来指导蛋白质合成的过程对地球 上的所有生物是相同的，分子生物学家称之为中心法则( c e n t r a ld o g m a ) 。 3 生物分子数据的距离度量及其应用 n h 2 l h g c o o h r 图1 1 氨基酸分子结构示意图( 除脯氨酸外，均可用此通式表示) 生物体的遗传信息以密码形式编码在d n a 分子上，表现为特定的核苷酸排列顺 序，并通过d n a 的复制( r e p l i c a t i o n ) 使遗传信息从亲代传向子代。在后代的生长发育 过程中，d n a 分子中的遗传信息转录( t r a n s c r i p t i o n l 到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 ) 生成体内各种蛋白质，行使 特定的生物功能。翻译过程是在核糖体上进行的。这样，通过遗传信息从亲代传向子 代，并在子代表达，使得子代获得了亲代的遗传性状。r n a 也能通过复制过程合成出 与其自身相同的分子。此外，生物界还存在由r n a 指导下的d n a 合成过程，即逆转 录，这一过程发现于逆转录病毒中。通过基因转录和翻译得到的蛋白质分子可以反过 来作用于d n a ，调控其它基因的表达。分子生物学的中心法则见图1 2 ，它说明遗传信 息由d n a 分子到r n a ，再到蛋白质的传递过程。在翻译过程中，每三个碱基构成一 个三联体，对应一个氨基酸或者一个终止密码子，这种对应被称为为遗传编码。 n a 墨f 仑a 三蠡麓 气蒜v 图1 2 分子生物学中心法则 1 1 3 生物信息学的主要研究领域 序列比对 序列比对是将两个或多个序列的各个字符f 代表核苷酸或者氨基酸残基1 按照对应 等同或者置换关系进行对比排列，其结果是找出两个序列共有的排列顺序，是序列相 似性程度的一种定性描述，反映出在什么部位两个序列相似，在什么部位两个序列存 在差别。 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列 之间的相似区域和保守性位点，寻找二者可能的分子进化关系。进一步的比对是将多 4 大连理工大学博士学位论文 个蛋白质或核酸同时进行比较，寻找这些有进化关系的序列之间共同的保守区域、位 点和p r o f i l e ，从而探寻导致它们产生共同功能的序列模式。此外，还可以把蛋白质序列 与核酸序列相比来探寻核酸序列可能的表达框架；把蛋白质序列与具有三维结构信息 的蛋白质相比，从而获得蛋白质折叠类型的信息。 比对还是数据库搜索算法的基础，将查询序列与整个数据库中的序列进行比对， 能最快速的获得有关查询序列的大量有价值的参考信息，对于进一步分析其结构和功 能都有很大的帮助。近年来随着生物信息学数据大量积累和生物学知识的整理，通过 比对方法可以有效地分析和预测一些新发现基因的功能。 蛋白质结构比较和预测 蛋白质的结构比序列更加保守，通过比较蛋白质的空间结构，可以发现蛋白质的 结构共性，发现属于同一家族蛋白质的保守结构，以及与蛋白质功能密切相关的结 构域等。蛋白质结构比较的一个基本任务是在已知两个蛋白质对应结构特征的条件 下，寻找将两个蛋白质空间结构重叠的几何变换，从而进行三维结构的比对f s t r u c t u r a l a l i g n m e n t l 。在比对两条蛋白质序列时，一条序列平行地排在另外一条序列的上方，通 7 过插入或删除操作，使得每一列对应的氨基酸尽可能地相同；而在结构比对中，一个 蛋白质结构叠放在另外一个结构之上，通过结构的空间变换，使得两个结构中各个对 应的原子空间位置尽可能地重叠。序列比对的目的是为了发现序列之间的相似性，而 结构比对的目的则是为了发现结构之间的相似性。 从数学上讲，蛋白质结构预测的问题是寻找一种从蛋白质的氨基酸线性序列到蛋 白质所有原子三维坐标的映射。蛋白质结构预测主要有两大类方法。一类是理论分析 方法或从头计算方法f a bi n i t i o ) ，通过理论计算( 如分子力学、分子动力学计算) 进行 结构预测。该类方法假设折叠后的蛋白质取能量最低的构象。另一类蛋白质结构预测 的方法是统计方法，该类方法对已知结构的蛋白质进行统计分析，建立序列到结构的 映射模型，进而根据映射模型直接从氨基酸序列预测未知结构的蛋白质结构。 基因识别 基因识别的基本问题是给定基因组序列后，正确识别基因的范围和在基因组序列 中的精确位置。识别d n a 序列中蛋白质编码区域的方法主要有两类。一类是基于信 号的识别。真核基因外显子( 编码区域) 具有一些特别的序列信号，如内部的外显 子被剪切接受体位点和给体位点所界定，5 端的外显子一定是在核心启动子( c o r e p r o m o t e r ，例如t a t a 盒) 的下游，而3 端的外显子的下游包含多聚a 信号和终 止编码。根据这些序列特征信号确定外显子的边界，从而达到识别编码区域的目的。 另一类是基于统计度量的方法，对编码区进行统计特性分析。例如，统计说明，d n a 中密码子的使用频率不是平均分布的，某些密码子会以较高的频率使用，而另一些则 较少使用。这样就使得编码区的序列呈现出可察觉的统计特异性，即“密码子偏好性 5 生物分子数据的距离度量及其应用 ( c o d o l lb i a s e s ) ”。 分子进化和比较基因组学 分子进化是利用不同物种中同源基因序列或蛋白质序列的异同来研究生物的进 化，构建进化树。系统发生树的构建方法很多种。根据所处理数据的类型，可以将系 统发生树的构建方法大体上分为两大类。一类是基于距离的构建方法，利用所有物种 或分类单元间的进化距离，依据一定的原则及算法构建系统发生树。基本思路是列出 所有可能的序列对，计算序列之间的遗传距离，选出相似程度比较大或非常相关的序 列对，利用遗传距离预测进化关系。另一类方法是基于离散特征的构建方法，利用的 是具有离散特征状态的数据，如d n a 序列中的特定位点的核苷酸。建树时，着重分析 分类单位或序列间每个特征f 如核苷酸位点) 的进化关系等。 现有的构建进化树的方法一般是利用基因组中的部分d n a 序列片段或单条蛋白质 序列。随着大规模基因组测序的完成，从全基因组数据出发来构建物种的进化关系已 成为目前广泛关注的一个课题。然而由于基因组序列往往较长，这对现有的计算工具 是个挑战。 序列重叠群( c o n t i g s ) 装配 根据现有的测序技术，每次实验只能测出约5 0 0b p 的碱基序列。如人类基因的 测量就采用了鸟枪方法f s h o t g u n ) ，这就要求把大量的较短的序列全体构成了重叠群 ( c o n t i g s ) 。逐步把它们拼接起来形成序列更长的重叠群，直至得到完整序列的过程称 为重叠群装配。从算法层次来看，序列的重叠群是一个n p - 困难问题。 遗传密码的起源 通常对遗传密码的研究认为，密码子与氨基酸之间的关系是生物进化历史上一次 偶然的事件而造成，并被固定在现代生物的共同祖先里，一直延续至今。不同于这种 “冻结”理论，有人曾分别提出过选择优化，化学和历史等三种学说来解释遗传密 码。随着各种生物基因组测序任务的完成，为研究遗传密码的起源和检验上述理论的 真伪提供了新的素材。 基于结构的药物设计 人类基因工程的目的之一是要了解人体内约1 0 万种蛋白质的结构、功能、相互作 用以及与各种人类疾病之间的关系，寻求各种预防和治疗方法，包括药物治疗。基于 生物大分子结构及小分子结构的药物设计是生物信息学中的极为重要的研究领域。为 了抑制某些酶或蛋白质的活性，在已知其蛋白质三级结构的基础上，可以利用分子对 齐算法，在计算机上设计抑制剂分子，作为候选药物。这一领域目的是发现新的基因 药物，有着巨大的经济效益。 6 大连理工大学博士学位论文 基因表达数据的分析 分析基因表达数据是目前生物信息学研究的热点和重点之一。对基因表达数据迸 行分析、归纳，可以了解基因表达的时空规律，探索基因表达的代谢控制，理解遗传 网络，提供疾病发病机理的信息。目前对基因表达数据的处理主要是进行聚类分析， 将表达模式相似的基因聚为一类，在此基础上寻找相关基因，分析基因的功能，分析 基因的转录调控。所用方法主要有相关分析方法、模式识别技术中的聚类方法和分类 方法、人工智能中的自组织映射神经网络。此外，还有主成分分析方法，利用主成分 分析可以在多维数据集合中确定关键变量的特点，分析在不同条件下基因响应的规律 和特征。进一步的分析还可以探索基因的转录调节网络，发现基因在环境或药物作用 下表达模式的变化，阐明一些基因对另一些基因的调节作用。 1 2 生物分子数据的比较 生物序列( 或结构) 的比较是生物信息学中最基本和最重要的工具之一。通过序 列的比较，我们可以从大量的序列信息中获取生物序列中的功能、结构和进化信息。 生物信息学的许多其它领域，如数据库搜索，系统树构建，蛋白质结构和功能的预 测、序列片段的拼接等都需要首先确定生物序列之间的距离度量。目前广泛使用的序 列比较方法可以分为两类：( 1 ) 比对，( 2 ) 不依赖于比对的序列比较方法。 1 2 1 序列比对 序列比对的理论基础是物种进化学说。如果两个序列之间足够相似，那么就可以 推测二者可能具有共同的进化祖先，经过序列中残基的删除、替换，或者序列片段的 重组等分子进化操作分别演化而来【1 。 根据进行比对的序列数目，比对问题可以分为两序列比对和多重序列比对。双 序列比对有比较成熟的动态规划算法，比较经典的有n e e d l e m a n - w u n s c h 算法忙和 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 算法是典型的全局比对算法，适合于整 体相似度较高的序列。s m i t h w a t e r m a n 算法是典型的局部比对算法，它使用迭代方法 计算出序列之间的相似性分值，然后采用回溯技术找到最优的比对。该算法在识别局 部相似性时的灵敏度很高，是后来的各种局部比对算法的基础。同时多序列比对算法 在双序列比对算法的基础上得到开发，这些比对算法都需要定义适当的打分函数。由 于基于动态规划算法的序列比的操作过程很复杂，后来的比对算法便开始向其他方法 转变，如遗传算法1 4 】、模拟退火算法 5 1 、启发式算法等。 两条序列比对算法的要点是： 序列的扩张：令q 是一个有k 种字母的字符集，v = 劬a 2 o 。和w = b l b 2 既 是基于q 的两条序列。又令q 7 = q u 一) 为一扩展字符集( 这里u 是一个虚拟 7 生物分子数据的距离度量及其应用 的元素，代表插入一个空格或者删除一个字母) ，然后视y 和w 为基于字符集q 7 的序列。 打分函数：它是定义在k + 1 个字母上的一种度量函数。一般记作p ( a ，6 ) 。 比对问题：对于两个序列v 和彬，寻求它们的扩张序列v 和w ，使得它们的 得分值为最大。这里所用的是动态规划算法，即利用下面的递归关系做出一张序 列比对得分表。 f 现一1 j + p ( 瓯，一) d i j = m a x d t 一1 j 一1 + p ( a i ，b j ) ， ld i , j 一1 + p ( 一，如) 其中如和分别表示序列v 和w 的第i 和第歹个基，鼠j 表示序列v 的长为i 的字首与序列w 的长为j 的字首比对后的得分。 尽管人们在序列比对方面已经做了大量的工作，但有几个问题一直困扰着人们： 一是没有什么合适的理论模型能很好地描述空位问题，因此打分矩阵中空位罚分缺乏 理论依据而更多的带有主观色彩。一般的处理方法是用两个罚分值，一个是对插入的 第一个空位罚分，另一个是对空位的延伸罚分。对于具体的比对问题，采用不同的罚 分方法会有不同的效果。二是比对算法的时间和空间复杂度一直没有达到令人满意的 效果，特别是多重序列比对，目前尚缺乏快速而又十分有效的算法。此外，比对算法 假设序列片段之间是邻接保守的，但基因重排、转座等遗传操作大量存在，使得比对 算法在比较基因组时遇到了理论上的困难。序列比对的这些不足，促使很多人试图寻 找其它的方法来比较序列。 1 2 2 不依赖于比对的序列比较方法 人们最早提出的非比对序列比较方法是基于序列中短“字符串 出现的频率。早 在1 9 8 6 年，b l a i s d e l l 和k a r l i n 等就发现基因组中所有“双核苷酸”的相对频率是近 似恒定的删。据此，他们提出用“g e n o m es i g n a t u r e 来描述个基因组。g e n o m e s i g n a t u r e 实际上是由所有的双核苷酸相对频率m = 厶掣l 厶构成的一个向量。2 0 世 纪初，w a t e r m a n 等人系统研究了生物序列中短字的统计及概率性质，给出了字出现 次数的确切概率分布的推导和渐近逼近的估计，为深入研究基于字频率的序列比较方 法提供了理论依据嘲。2 0 0 3 年，v i n g a 和a l m e i d a 总结了基于字频率的序列比较方法 n o 】。这些方法首先利用滑动窗口方法统计出一定长度的字在序列中出现的频数，然后 通过适当的“正规化”操作，将生物分子序列映射到高维空间中的一个向量。这样， 一条生物序列就可以用其对应的“字频数向量”或“频率向量 来刻画，序列之间的 比较问题就转化为高维空间中向量之间的比较。 8 大连理工大学博士学位论文 2 0 世纪初，信息论中的符号序列复杂度概念和数据压缩的思想也被引入到生物 信息学的研究中，并取得了丰硕的成果。比较有代表性的是李明等人提出的k 复杂 度的方法u ”和o t ua n ds a y o o d 提出的l z 复杂度的方法p 斟。根据信息论和编码理 论，特别是柯尔莫哥洛夫复杂度理论，可以用联合压缩方法来度量两个序列的相似 程度。假设k ( s ) 表示序列s 的柯尔莫哥洛夫复杂度( k 复杂度) ，k ( s i t ) 是给 定? 下序列s 的条件k 复杂度( 或算法熵) ，两条序列s 和r 的距离可以定义为： 呔c ( st ) = 1 一k ( 可s ) - 育k ( s i t ) 此距离近似满足距离度量公理。李明等人把上述距离运 用在哺乳动物的完整线粒体基因组中，得到的序列距离和进化树与一致的发育关系相 符。然而，一条序列的k 复杂度定义为产生这一序列的最短程序的b i t 数，这个定 义没有通用的算法，因此很难由计算机来实现。目前只能采用一些近似算法，如利用 g e n c o m p r e s s 等软件程序。 另外一种常用的非比对方法是基于生物序列的图形化表示。此类方法首先将生物 序列( 或结构) 描述为二维或三维空间中的图形f 通常是点列或者曲线) ，然后提取图形 中的某些特征量作为“描述子”，生物序列之间的比较就转化为特征量之间的比较。 图形表示方法中比较有代表性的是张春霆等人提出的z 曲线方法。通过提取压曲线中 d n a 序列的某些数字特征，他们比较成功地研究了真核和原核生物基因组中若干重要 问题，包括人类基因组外显子识别，酵母基因组基因识别，细菌与古细菌基因组的a b i n i t i o 基因识别，s a r s - c o v 基因组基因识别等h 弘1 6 1 。r a n d i c 等人研究了分子图形表 示的某些特征量，发现用相应距离矩阵的最大特征值可以较好地描述分子的折叠程度 弘7 1 。由于生物分子的折叠与其结构和功能密切相关，因此对于序列图形表示和最大特 征值的研究得到了广泛的关注。沿用r a n d i c 等人的思路，郭晓峰、廖波、李春等人提 出了一系列新的、行之有效的图形化表示方法，并探索了其它的图形特征量在序列分 析中的应用1 h 。 1 3 本文的主要工作 综上可知，合理描述生物分子序列( 或结构) ，定义它们之间有效的距离度量是 进行生物信息学研究的一个核心步骤。本文针对传统比对算法中理论上和计算上的缺 陷，提出了一些新的生物序列比较模型，并将这些比较方法应用于分子系统发生分 析、蛋白质亚细胞定位、结构分类等生物信息学领域。 由于比对算法的计算复杂度较大，对进化模型要求较为苛刻，因此对于较长序 列，特别是全基因组系统发生分析，比对算法遇到了非常大的挑战。相对熵方法是描 述两个分布向量距离的经典算法，但当序列长度较短或不同字符类型出现频率相差较 大时，易出现“退化”现象。本文第二章提出了经典相对熵方法的一种修正一一加权 序列熵f w e i g h t e ds e q u e n c ee n t r o p y , w s e ) 。通过对包含s a r s 病毒的2 4 个病毒全基 因组的种系发生分析，我们发现，当所考虑的字长较小时，我们的修正与相对熵方法 9 生物分子数据的距离度量及其应用 得到了一致的结果。而随着字长的增加，相对熵方法得到退化的结果时，而我们的方 法依然有效，并且所得到的进化树的拓扑结构随着字长的增加呈一个收敛的趋势。在 第二章的第二节，基于随机d n a 序列中字分布的一个p o i s s o n 模型，我们提出了一个 基于不同“字表达水平的距离度量。该方法将序列之间的距离纳入到一个概率的框 架，避免了某些异常字带来的影响。 比对算法的进化论基础是点突变( 点插入、删除、替换) ，因此，进化中的一些 片段操作，如遗传重组等对比对的性能影响很大。而基于条件压缩的复杂度的距离度 量不需要苛刻的进化模型假设，因此可以克服上述缺陷。在本文的第三章，我们用基 于条件压缩的距离度量进行了蛋白质亚细胞位点的预测和蛋白质结构的分类。预测蛋 白质所处的亚细胞位点是蛋白质序列注释的一个重要步骤。传统方法是对蛋白质序列 进行特征抽取，将蛋白质序列向量化表示，然后采用一些机器学习或模式识别算法进 行位点的预测。而在特征提取的过程中，不可避免地要有信息的丢失( 特别是“序信 息 ) ，在本章的第二节，我们提出了一种基于复杂度的位点预测算法，可以避免特 征提取的过程。通过对三个常用数据集的预测实验，该方法得到了较高的预测精度。 对蛋白质结构进行比较，传统的方法是结构比对。然而此方法计算复杂度较高，模型 参数的设置也较为主观。本章的第三节中，我们首先对蛋白质主链二面角空间进行划 分，然后通过符号指派将蛋白质结构序列进行了符号化。这样处理符号序列的方法就 可以引入到蛋白质结构比较中来，我们采用的是基于符号复杂度的距离度量。该方法 对2 0 种蛋白质的分类效果较好。 对于复杂事物，人们往往只关注其一部分性质而忽略其它，这实际上就是物理学 中的粗粒化思想和代数学中的同态思想。通过对四种核苷酸的三种重要的性质分类， 可以得到d n a 序列的三种约化二元序列一一特征序列。显然，相对于初始d n a 序列 来说，每一个二元序列都会丢失一部分信息。而单个约化二元序列究竟包含何种生物 信息? 数量如何? 在本文的第四章，我们将从系统发生分析的角度对上述问题进行探 讨。 1 0 大连理工大学博士学位论文 2 基于“字频率”的序列比较方法 基于生物序列中短“字符串 组份的序列比较方法是目前最为常用的非比对方 法。通常来讲，与比对方法相比，该方法的计算复杂度较低，对进化模型的假设较为 宽松，因此适合处理较长的序列，特别是基于全基因组的种系发生分析。 本章中，我们提出了两种基于“