（计算机应用技术专业论文）生物序列的内在性质.pdf

摘要 摘要 生物信息学是多学科的交叉产物，以计算机为工具对生物信息进行存储、检索和 分析。本论文主要研究了生物序列可视化、比对以及蛋白质序列网络等有关问题。 从混沌游走中得到启发，引入c g r ( c h a o sg a m er e p r e s e n t a t i o n ) 的概念，定义了蛋 白质混沌游走表示法( p c g r , c h a o sg a m er e p r e s e n t a t i o no f p r o t e i n ) 。针对蛋白质序列的多 重分形性质及其r 6 n y i 熵率进行进一步研究。数学领域中的分形理论和信息论中的熵 率概念被引入到蛋白质序列的分析中：把2 0 种氨基酸以看作符号序列，由混沌游走表 示的二维可视化延伸到n 维空间中，用分形维数来体现蛋白质序列的性质；另外，蛋 白质序列也可以被看作一组信号，可以用信息熵的概念来进行刻画。然后把多重分形 维数和符号序列的r 6 n y i 熵率之间通过概率测度建立对应关系。 氨基酸按照不同的性质进行分类，其分类的依据和偏重不同，分类结果也不同。 文中介绍了两种分类：根据h p 模型分为4 类和依照理化性质分为7 类，结合提出的一种 新的比对算法，把分类过的两条蛋白质序列进行比对。利用蛋白质序列的p c g r 距 离，给定阈值k ，迅速判断相同片段的长度及所在位置，降低了计算复杂度也可以保证 比对效率，还可以根据比对结果判断序列的相似性。 另外结合分层聚类法，利用f c g r ( f r e q u e n c ym a t r i c e se x t r a c t e df r o mc g r s ) 距离和 二次偏差距离分别构造了2 6 种生物的种系发生树。不同的距离定义、相同的数据，得 到不同的种系树，可以探讨物种之间的进化关系。每个结点表示一段d n a 片段，每一 条连线都包含着片段之间的连接信息。通过复杂网络研究生物体的拓扑结构，主要通 过测量聚类系数构建网络的拓扑结构。结果表明所构建的复杂网络的度分布呈现幂率 性质，但是其幂率指数过小，这说明了d n a 序列有着稳定的结构，但是在遗传过程中 却存在大量的随机性和不稳定性。 关键词：蛋白质混沌游走表示法，多重分形维数，r 6 n y i 熵率，序列比对，二次偏差距 离，种系发生树，分层聚类法，复杂网络 a bs t r a c t b i o i n f o r m a t i c si st h ec r o s s p r o d u c to fam u l t i d i s c i p l i n a r y , w i t ht h ec o m p u t e ra st h et o o l o fb i o l o g i c a li n f o r m a t i o ns t o r a g e ，r e t r i e v a la n da n a l y s i s t h i sp a p e rs t u d i e st h ev i s u a l i z e d b i o l o g i c a ls e q u e n c e s ，a l i g n m e n ta n dp r o t e i nn e t w o r ka n ds oo n b e i n ge n l i g h t e n e df r o mc h a o sw a l k ，a n dc o m b i n i n gg e n es e q u e n c ea n dc h a o sg a m e r e p r e s e n t a t i o n ，w ed of u r t h e rs t u d yo np r o t e i ns e q u e n c em u l t i f r a c t a ln a t u r ea n di t sr 6 n y i e n t r o p yr a t e f r a c t a lt h e o r yf r o mm a t h e m a t i c sa n de n t r o p yr a t ef r o mi n f o r m a t i o nt h e o r yw a s i n t r o d u c e dt ot h ea n a l y s i so fp r o t e i ns e q u e n c e s ：t h e2 0k i n d so fa m i n oa c i d sa r ev i e w e da s s y m b o l s ，t h e nw ec a nu s ef r a c t a ld i m e n s i o nt oe x p r e s st h en a t u r eo fp r o t e i ns e q u e n c ew i t h e x t e n d i n gf r o mt w o - d i m e n s i o n a lv i s u a l i z a t i o no fc g r t on - d i m e n s i o n a ls p a c e ；i na d d i t i o n ， t h ep r o t e i ns e q u e n c ec o u l da l s ob es e e na sag r o u ps i g n a lw h i c hc a nb ed e p i c t e db y i n f o r m a t i o ne n t r o p y i te s t a b l i s h e sac o r r e s p o n d e n c eb e t w e e nm u l t i f r a c t a ld i m e n s i o n so fc h a o s g a m er e p r e s e n t a t i o no fp r o t e i n sa n dr 6n y ie n t r o p yr a t eo fs y m b o l i cs e q u e n c e sv i a p r o b a b i l i s t i cm e a s u r e i na c c o r d a n t ew i t hd i f f e r e n tn a t u r e ，a m i n oa c i d sc a nb ec l a s s i f i e d ，a n dt h eb a s i sa n d f o c u sf o ri t sc l a s s i f i c a t i o na r ed i f f e r e n t ，s ot h e r ea r es e v e r a ld i f f e r e n tc l a s s i f i c a t i o n s i nt h i s p a p e r , t h e r ea r et w ok i n d so fc l a s s i f i c a t i o n ：o n ei sd i v i d e di n t o4c l a s s e sa c c o r d i n gt oh p m o d e l ；t h eo t h e ro n ei sd e v i d e di n t o7c l a s s e si na c c o r d a n c ew i t ht h ep h y s i c o c h e m i c a l p r o p e r t i e s t h e nw i t han e wa l i g n m e n ta l g o r i t h m ，w et a k ea d v a n t a g eo fp c g rd i s t a n c e b e t w e e nt h et w oc l a s s i f i e dp r o t e i ns e q u e n c e sa n daf i x e dt h r e s h o l dkt oc o m p a r et h e s et w o s e q u e n c e s ，f i n dt h el e n g t ho fs i m i l a rf r a g m e n t sa n dl o c a t i o n s t h i sa l g o r i t h mc o u l dr e d u c e c o m p u t a t i o n a lc o m p l e x i t ya n dm a k es u r ea l i g n m e n te f f i c i e n c y i na d d i t i o n , i tm a ye s t i m a t e t h es i m i l a r i t yo fs e q u e n c e sw i t ht h e i ra l i g n m e n tr e s u l t s w i t hh i e r a r c h i c a lc l u s t e r i n gm e t h o d ，w eu s et h eq u a d r a t i cd i v e r g e n c ed i s t a n c ea n dt h e f c g rd i s t a n c et oc o n s t r u c tp h y l o g e n e t i ct r e e so f2 6s p e c i e s ，r e s p e c t i v e l y i tc a ne x p l o r et h e e v o l u t i o n a r yr e l a t i o n s h i p sb e t w e e ns p e c i e sf r o md i f f e r e n tp h y l o g e n e t i ct r e e s t h a th a v e d i f f e r e n td e f i n i t i o no fd i s t a n tb u tt h es a m ed a t as o u r c e e a c hn o d es t a n d sf o rad n a f r a g m e n t ； e a c hf r a g m e n tc o n n e c t i o nc o n t a i n si n f o r m a t i o nb e t w e e nt h et w on o d e s t h et o p o l o g y s t r u c t u r eo fo r g a n i s mc a nb es t u d yf r o mc o m p l e xn e t w o r k ，w h i c hi sc o n s t r u c t i o no ft h e n e t w o r kt o p o l o g ym a i n l yt h r o u g hm e a s u r i n gc l u s t e r i n gc o e f f i c i e n t t h er e s u l ts h o w st h a tt h e d e g r e ed i s t r i b u t i o no fc o m p l e xn e t w o r kt a k e so np o w e r - l a wc h a r a c t e r i s t i c ，b u ti t se x p o n e n ti s t o os m a l l ，w h i c hi l l u m i n a t e st h a td n a s e q u e n c e sh a v es t a b l es t r u c t u r e ，w i t hag r e a td e a lo f r a n d o m i c i t ya n di n s t a b i l i t yi nt h eg e n e t i cp r o c e s s k e y w o r d s ：c h a o sg a m er e p r e s e n t a t i o no fp r o t e i n ( p c g r ) ，m u l t i f r a c t a ld i m e n s i o n s ，r 6 n y i e n t r o p yr a t e ，s e q u e n c ea l i g n m e n t ，t h eq u a d r a t i cd i v e r g e n c ed i s t a n c e ，p h y l o g e n e t i ct r e e s ， h i e r a r c h i c a lc l u s t e r i n g ，c o m p l e xn e t w o r k i i 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 签 名：盈左址日 期：趁型l 三丝_ 一 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件扣 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名 互墨垒望 导师签名：车泓透一日期：啦l - 2 靼一 第一章绪论 第一章绪论 什么是生物信息学? 生物信息学( b i o i n f o r m a t i c s ) 是一门交叉科学，它包含了生物信 息的获取、处理、存储、分发、分析和解释等在内的所有方面，它综合运用数学、计 算机科学和生物学的各种工具，来阐明和理解生物序列所包含的生物学意义。生物信 息学这一名词的出现仅仅是几年前的事情，但是计算生物学这一名词的出现要早的 多。鉴于这两门学科之间并没有或难以界定严格的分界线，在这里统称为生物信息 学。 生物信息学是响应后基因组时代的呼唤而产生的。新的生物学研究模式的出发点 应该是理论的。部分科学家将从理论推测出发，然后再返回到实验中去，追踪或验证 这些理论假设。生物学家不仅必须熟悉使用计算机，而且也要改变他们研究生命现象 的途径。 1 1 背景介绍 现代科学研究表明生命起源于3 5 亿年前，最初的生命形式非常简单，但在几十亿 年的称之为进化的主动过程的作用下，生命发生了演绎并产生了多样性，因此今天我 们可以同时看到非常复杂和非常简单的生命体。 复杂和简单的生物有着相似的分子化学或生物化学。生物化学中的主要角色是被 称为蛋白质和核酸的分子。粗略地说蛋白质决定一个生物是什么和做什么，核酸则 负责编码产生蛋白质所必要的信息，并把这种信息传给后代。 生命的基本单位是细胞，它由细胞膜、细胞质和细胞核三者组成遗传信息储存在 细胞核中。人的细胞核中含有2 3 对染色体，d n a ( 脱氧核糖核酸) 和蛋白质。d n a 经螺 旋、扭曲、折叠等压缩到万分之一并与蛋白质一起组成染色体。d n a 是一种大分子， 由两股长链以螺旋式构成。这种螺旋结构是在1 9 5 3 年由j w a t s o n 和v c n c k 1 提出并 获1 9 6 2 年的n o b e l 奖，是2 0 世纪最伟大的科学发现之一。 d n a 分子上的一个个具有生物功能的片段是基因。基因由若干按一定顺序排列的 核苷酸组成。核苷酸由磷酸基团、脱氧核糖及碱基构成，有4 种不同的碱基，即：腺嘌 呤( a ) 、胞嘧啶( c ) 、鸟嘌呤( g ) 及胸腺嘧啶( t ) 。核苷酸按其所含碱基的不同也分为4 种。在d n a 的双链上a 、t 成对出现g 、c 也成对出现，每对称为一个碱基对。 遗传密码在d n a 的链上，密码由4 种不同的核苷酸按一定顺序排列而成，即可看 成由4 个字母a ，gc ，t 排列而成。据估计，人类的d n a 约含有3 0 亿个密码，排列组成 至少l o 万条基因。决定人体蛋白质的2 0 种氨基酸的遗传密码己找出，先由a ，gc ，t 中每3 个字母重复排列成一密码子，共有4 3 = 6 4 个密码子。每一密码子对应一种氨基 酸；但由于只有2 0 种氨基酸，故这种对应只能是多对一的。例如a g a ，a g g 都对应 于精氨酸，此种对应关系已完全确定，称为遗传密码字典。使人们惊叹不已的是，自 然界所有的生命形式都共用这本密码。在确定了三联体码在d n a 上线性串接的结合方 式后，发现了为蛋白质编码的基因结构。这些基因在d n a 上所处的位置，称为d n a 江南人学硕+ 学位论文 的编码区，约占整个基因组的3 5 ，其余部分习惯上统称为“废物( j u n k ) d n a 。在 对编码区上d n a 的结构所进行的4 0 多年的研究工作中，已造就了几十名n o b e l 奖获 得者。然而j u n kd n a 中包含的信息也许更多。总之细胞 细胞核3 染色体3 蛋白质 ( 含氨基酸) 、d n a ( 由核苷酸组成) 3 基因( 上有密码子，即由a ，gc ，t 组成的三联体 码) 。 1 9 8 7 年开始，美国启动人类基因组研究计划，任务有- -第一是“读出”人基因组 全部核苷酸的顺序，第二是“读懂”，即找出全部基因在染色体上的位置，了解它们的 功能。用数学的语言来说，人类基因组计划的最基本、最直接的结果是得到一个由a ， qc ，t 可重复排列而组成的长度为3 x1 0 9 的一维链。解读后，人们不仅获得静态的结 构信息，而且还能得到动态的四维( 时空) 调控信息。2 0 0 0 年6 月人类基因组计划中d n a 全序列草图完成，2 0 0 1 年完成精确的全序列图，如今人类将拥有本记录着自身生老 病死及遗传进化的全部信息的“天书。这本大自然写成的“天书”是按一定顺序排 成的长约3 0 亿的序列，其中没有“断句”也没有标点符号，除了这4 个字符表示4 种碱 基以外，人们对它包含的“内容知之甚少，难以读懂。破译这部世界上最巨量信息 的“天书 是二十一世纪最重要的任务之一。在这个目标中，研究d n a 全序列具有什 么结构，由这4 个字符排成的看似随机的序列中隐藏着什么规律，又是解读这部天书的 基础，是生物信息学最重要的课题之一。 虽然人类对这部“天书 知之甚少，但也发现了d n a 序列中的一些规律性和结 构。例如，在全序列中有一些是用于编码蛋白质的序列片段，即由这4 个字符组成的6 4 种不同的3 字符串，其中大多数用于编码构成蛋白质的2 0 种氨基酸。又例如，在不用于 编码蛋白质的序列片段中，a 和t 的含量特别多些，于是以某些碱基特别丰富作为特 征去研究d n a 序列的结构也取得了一些结果。此外，利用统计的方法还发现序列的某 些片段之间具有相关性，等等。这些发现让人们相信，d n a 序列中存在着局部的和全 局性的结构，充分发掘序列的结构对理解d n a 全序列是十分有意义的。目前在这项研 究中最普通的思想是省略序列的某些细节，突出特征，然后将其表示成适当的数学对 象。这种被称为粗粒化和模型化的方法往往有助于研究规律性和结构。 要找出这四个字符排成的看似随机的序列中的隐藏的规律，需要考虑如何省略序列 的某些细节，突出特征，找到合理有效的方法对序列集合进行分类。这里着重介绍一种 按a ，t 和c ，g 的含量来分类d n a 序列的一种的方法。近几年，d n a 序列的研究已 经成为生命科学中异常活跃的一个研究领域。现在，越来越多的科学家尤其是计算机 科学家已经认识到研究d n a 计算机的广阔前景，纷纷投入到该研究领域中来。 1 2 研究的目的与意义 随着人类基因组计划的实施，有关核酸、蛋白质的序列和结构数据呈指数增长。 面对巨大而复杂的数据，运用计算机管理数据、控制误差、加速分析势在必行。由 此，从2 0 世纪8 0 年代末开始，生物信息学逐渐兴起并蓬勃发展，它是多学科的交叉产 物，涉及生物、数学、物理、化学、计算机科学、信息科学等传统领域，目前还处于 2 第一章绪论 初期发展阶段。 生物信息学的重要研究课题：1 大规模基因组测序中的信息分析；2 新基因和新 s n p 的发现与鉴定；3 非编码区信息结构分析；4 遗传密码的起源和生物进化；5 完整 基因组的比较研究；6 大规模基因功能表达谱的分析；7 生物大分子的结构模拟与药物 设计：8 生物信息学分析方法的研究：9 建立国家生物医学数据库与服务系统；1 0 应用 与发展研究。 生物信息学是以计算机为工具对生物信息进行存储、检索和分析，它是当今生命 科学和自然科学的重大前沿领域之一，同时也将是2 l 世纪自然科学的核心领域之一。 其研究重点主要体现在基因组学( g e n o m i c s ) 和蛋白组学( p r o t e o m i c s ) 两方面，具体说， 是从核酸和蛋白质序列出发，分析序列中表达的结构与功能的生物信息。就人类基因 组来说，得到序列仅仅是第一步，后一步的工作是所谓的后基因组时代( p o s t g e n o m e e r a ) 的任务，即收集、整理、检索和分析序列中表达的蛋白质结构与功能的信息，找出 规律。 生物信息学的发展将会给生命科学带来革命性的变革。它的成果不仅会对相关基 础学科起到巨大的推动作用，而且还将对医药、卫生、食品、农业等产业产生巨大的 影响，甚至引发新的产业革命。 生物信息学研究是从理论上认识生物本质的必要途径，通过生物信息学研究和探 索，可以更为全面和深刻地认识生物科学中的本质问题，了解生物分子信息的组织和 结构，破译基因组信息，阐明生物信息之间的关系。基因序列到蛋白质序列的三联密 码关系是众所周知的，也是非常简单的，然而，基因调控序列与基因表达之问的关 系、蛋白质序列与蛋白质结构之间的关系则是未知的，也一定是非常复杂的。破译和 阐明生物信息的本质将使得人类对生物界的认识跨越一个新台阶。 生物信息学不同与传统生物学，它的出现将改变生物学的研究方式。传统的生物 学是一门实验科学，传统分子生物学实验往往是集中精力研究一个基因、一条代谢路 径，手工分析完全能够胜任。然而，随着分子生物学技术的发展，已经出现一些高通 量的实验方法，如基因芯片，利用基因芯片一次可以获取上千个基因的表达数据。生 物学已经从一次只分析一个生物分子的时代跳跃到同时分析成千上万个生物分子的时 代。对于高通量的实验结果，必须利用计算机进行自动分析。因而，在高通量实验技 术出现的时代，生物信息学必然要介入生物学研究和实验。再者，从生物分子数据本 身来看，各种数据之间存在着密切的关系，如d n a 序列与蛋白质序列、基因突变与疾 病等，这些联系反映了生物学的规律。但是，这些关系可能是非常复杂的，是我们未 知的，是简单的多元统计方法难以分析的。对于这些复杂的关系，必须运用现代信息 论、动力系统理论、复杂系统理论、分形理论等方法去分析，去研究。因而，随着分 子生物学研究的深入，必然需要生物信息学。另外，现在全世界每天都会产生大量的 核酸和蛋白质序列，不可能用实验的方法去详细研究每一条序列，必须首先进行信息 处理和分析，去粗取精，去伪存真。通过预处理，发现有用的线索，在此基础上进行 有针对性、有明确目的的分子生物学实验。 3 江南人学硕十学位论文 预测生物信息学的未来主要就是要预测它对生物学的发展将带来什么样的根本性 的突破。这种预测是十分困难的，甚至几乎不可能。但是人类科学研究史表明，科学 数据的大量积累将导致重大的科学规律的发现。我们相信新世纪生物信息学将得到巨 大的发展。生物信息学的发展在国内、外基本上都处在起步阶段，所拥有的条件也大 体相同，即使我国有关条件差一些，但差别也不大。因此，这是我国生物学赶超国际 先进水平的一个百年一遇的极好机会堙1 。 1 3 国内外研究状况 随着基因组计划的不断进展，我们拥有的海量数据必须通过生物信息学的手段进 行收集、分析和整理后，才能成为有用的信息和知识，也就是说，只有经过生物信息 学手段的分析处理，我们才能获得对基因组的正确理解，因此可以说是人类基因组计 划为生物信息学提供了兴盛的契机，创造了施展身手的巨大空间。 国外一直非常重视生物信息学的发展，各种专业研究机构和公司如雨后春笋般涌 现出来，生物科技公司和制药工业内部的生物信息学部门的数量也与日俱增。但由于 对生物信息学的需求是如此迅猛，即使是美国这样的发达国家也面临着供不应求、人 才匮乏的局面。 大量复杂的全基因组数据引发了数据可视化描述工具的发展，在生物信息学中主 要见于：( 1 ) 进行序列操作和分析的图形用户界面，通过便捷的桌面工具进行数据的浏 览和与数据间的互动；( 2 ) 专门的可视技术，灵活运用图形、颜色和面积等方法对大量 的数据进行描述，最大限度地利用人类的感官对特征和模式进行挑选；( 3 ) 可视编程， 属于特殊的、高级的、领域专有的计算机语言中的图形描述算法。分子生物学有发明 可视化技术的传统，例如利用点曲线进行序列比较( 如种系发生印迹技术) ，采用不 同的图形系统描述折叠的r n a 结构，使用螺旋轮来证明双岐因子的螺旋结构以及其它 的生物结构。有一些表达形式很流行并已经确立了自己的地位，成为新的分子生物的 图标，并且仍在不断地加以完善以适应新的需要，如连续序列所含信息的“序列标 识”。许多新的工具将软件和用于导航及数据转化的方法紧密联系起来，还有很吸引 人的名字，如双曲线数形察看器、警告变焦、神奇的透镜等。通常它们针对专业领域 的特殊要求，如描述通路、绘制图谱，也可以与那些处理大量的序列数据的商业可视 化工具一样进行数据的解释。 针对d n a 序列内部结构分析的统计研究方法愈发显得重要，但对生物学研究人员 来说，d n a 序列可视化能够提供更加直观的信息。其可视化方法主要分为两种：图形 表示和图像表示。图形表示是指把d n a 序列映射成空间的线性结构，如d n a 序列的 一维、二维、三维以及多维行走等，多为曲线表示形式；而图像表示则是把d n a 序列 映射到空间的一个区域或体域，多为2 d 或3 d 图像表示形式。本文主要研究d n a 序列 的平面分形图像表示方法。 在d n a 序列可视化表示方面，j e f f r e y 首先提出了一种称之为混沌游戏表示( c g r c h a o sg a m er e p r e s e n t a t i o n ) 3 】的子序列结构可视化方法，它是一种以d n a 序列驱动简 4 第一章绪论 单迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) 产生分形图像的经典方法。文献 4 ，5 中，郝柏林院士等提出了另一种基于d n a 子序列出现频率的可视化方法，同 样能产生类似的分形图像。这些分形图像充分表明d n a 序列具有整体和局部的结构性 和长程相关性。2 0 0 0 年，d a n i e la s h l o c k 提出并研究了新的基于迭代函数系统的d n a 序列分形表示方法【6 ，。7 1 ，并引入演化计算思想，对混沌自动机进行演化以对序列进行可 视化分类。 目前，绝大部分的核酸和蛋白质数据库由美国、欧洲和同本的3 家数据库系统产 生；他们共同组成了d d b j e m b u g e n b a i l l 【国际核酸序列数据库，每天交换数据，同 步更新。其他一些国家，如德国、法国、意大利、瑞士、澳大利亚、丹麦和以色列 等，在分享网络共享资源的同时，也分别建有自己的生物信息学机构、二级或更高级 的具有各自特色的专业数据库以及自己的分析技术，服务于本国生物医学研究和开 发，有些服务也开放于全世界。 ( 1 ) 美国生物技术信息中心的g e n b a n k b 主主巳；zz 塑：旦曼坠i ：卫! 里：i b ：g q y z 型堡垒鱼金卫坠垒旦然zi 望鱼皇丕：b 主翌! ( 2 ) 欧洲分子生物学实验室的e m b lb 主主巳；么么塑：金也! 二b 金i 鱼金! 坠皇! g ：韭 两个数据库中的数据基本一致，仅在数据格式上有所差别，对于特定的查询，两个数 据库的响应结果差不多。 1 4 研究的主要内容 本论文主要研究了生物序列可视化、比对以及蛋白质序列网络等有关问题，内容 总体上分为七章： 第一章为绪论部分。首先简要地介绍了生物信息学的定义、研究背景；其次介绍 了研究生物信息学的目的和意义；最后介绍了当前国内外对于生物信息学研究的现 状。 在第二章中，重点介绍了基因序列的可视化研究方法。首先，从混沌游走中得到 启发，结合基因序列产生混沌游走表示，并简单描述了其定义和性质。基于可视化的 表示方法，就如同身份证一样，可以把混沌游走表示视为一种基因签名。其次，介绍 了郝百林教授提出的另一种基因可视化方法七串理论，从不同的角度研究基因序 列。两种可视化方法得到的图形很直观地体现出分形的性质，下一章在此基础上进行 了理论探讨。 第三章研究了蛋白质序列的多重分形性质及其r 6 n y i 熵率。数学领域的分形理论 和信息论中的熵率概念被引入蛋白质序列的分析中来。蛋白质序列是2 0 种氨基酸组 成，可以看作符号序列。由混沌游走表示的二维可视化延伸到n 维空间中，使二维分 形性质得以发展；另外，蛋白质序列也可以被看作一组信号，可以用信息熵的概念来 进行刻画。然后把多重分形维数和符号序列的r 6 n y i 熵率之间通过概率测度建立对 应关系。 氨基酸按照不同的性质进行分类，分类的依据和偏重不同，分类结果也不同。第 5 江南大学硕十学位论文 四章中介绍了两种分类：根据h p 模型分为4 类和根据理化性质分为7 类，提出一种新的 比对算法，然后把分类过的两条蛋白质序列进行比对。利用蛋白质序列的p c g r 距 离，给定阈值k ，迅速判断相同片段的长度及所在位置，降低了计算复杂度也可以保证 比对效率。 第五章是在前两章的基础上，结合分层聚类法利用p c g r 距离和二次偏差距离分 别构造了2 6 种生物的种系发生树。不同的距离定义、相同的数据，得到不同的种系 树，可以探讨物种之间的进化关系。 在第六章中引入复杂网络的概念，每个结点表示一段d n a 片段，每一条连线包含 着片段之间的连接信息。通过复杂网络研究生物体的拓扑结构，主要通过测量聚类系 数构建网络的拓扑结构。结果表明所构建的复杂网络的度分布呈现幂率性质，但是其 幂率指数过小，这说明了d n a 序列有着稳定的结构，但是在遗传过程中却存在大量的 随机性和不稳定性。 最后，第七章总结了全文，并对生物信息学的研究方向加以了展望，提出了有待 解决的问题。 6 第二章基冈序列的可视化方法 第二章基因序列的可视化方法 2 1c g r 综述 随着人类基因组的展开，人们也越来越关注于算法的研究。在这里我们将介绍一种 新的序列比较的方法：混沌游走表示。 c g r 是一种迭代映射技术，它把序列中的每一个单元，如蛋白质序列中的氨基 酸，d n a 中的核苷酸，映射到一个连续的坐标空问中去。c g r 不只是一种简单的序列 的图形化表示方法，它是一种功能强大的尺度独立的序列分析方法。 k 串理论是郝百林先生提出的一种d n a 序列可视化方法。二者都是把每个碱基坐 标化，通过可读框( o r f ，o p e nr e a d i n gf r a m e ) 来读取数据和定义图的大小，从而使 d n a 序列可视化。实际上，c g r 和k 串理论使等价的，只是碱基的坐标转化方法方法 不同而以：从视图上来看，前者采用的是散点绘图，后者则使用的是色彩渐变条来表 一 不o 2 2 混沌游走 混沌游走( c h a o sw a l k ) 是一个可以产生分形结构图片的算法【8 】。我们可以在一张纸 上执行这个算法。算法如下： ( 1 ) 在一张纸上任意确定不在同一直线上的三个点，我们称这三个点为顶点； ( 2 ) 标记第一个顶点为1 ，2 ；第二个顶点为3 ，4 ；第三个顶点为5 ，6 ； ( 3 ) 在纸上任选一个起始点，画上这个点； ( 4 ) 掷一个六面标有1 ，2 ，3 ，4 ，5 ，6 的骰子，得到一个数字n ，在n 对应的顶点与前一次 画上去的点的中点画上一个点。 ( 5 ) 一直执行步骤( 4 ) ，不断地往图里画点。 图1 三个点的混沌游走效果图 7 江南人学硕士学位论文 如果我们在电脑里执行这个过程，用产生随机数来代替上面的骰子，执行上千次 之后将得到( 见图1 ) 的结果它看上去不是一些随机的点，而是一个图案，数学上称为 s i c r p i n s k i 三角。 现在我们改变初始点的个数，由三个改为五个、六个或七个时，这个算法得到了 一些其它的图案。但是改为四个顶点时，情况却大不相同，画出的点均匀随机的分布 在正方形内。 2 3c g r 的构造与逮代函数 正方形的四个顶点对应四种核苷酸。在这里，我们不是通过产生随机数1 ，2 ， 3 ，4 来完成作图，而是用d n a 序列代替随机数，即每一个碱基的坐标都可以来确定 下一个碱基的位置。 c g r 算法： ( 1 ) 在坐标平面上画一个l x l 正方形，标记四个顶点为a ( 0 ，0 ) ；t ( 1 ，0 ) ：g ( o ，1 ) ： c ( 1 ，1 ) ； ( 2 ) 取正方形中心( 05 ，o 5 ) 作为起始点，设置d n a 序列的第一个字符为当前字符； ( 3 ) 在序列的当前字符对应的顶点与前一次画的点( 第一次为初始点) 连线的中点画上 一个点： ( 4 ) 设置d n a 序列的下一个字符为当前字符，继续执行( 3 ) 直至基因序列结束； 囤2 人类第1 1 号染色体上的口蛋白球区d n a 序列的c g r 下面给出c g r 的迭代函数，也可以认为是c g r 算法的公式化形式【9 】。对于一个序 列s = j 1 屯，s ，e a t g 。c ) 可以通过下面的迭代过程得到该序列的c g r ： 令a = 仉o ) ；1 气1 ，0 ) ；o = ( 0 ，1 ) ；c - - ( 1 ，1 ) ，对所有的i = 1 ，王，n ，令c 6 喝= c g r v i + 毋 其中c g = ( o 5 , 0 5 ) ，毋6 ( 0 ，0 ) ，( 1 ，0 ) ，( o i ) ，( 1 ，1 ) t 毋与s ，相对应。 图2 给出了人类第1 1 号染色体上的口蛋白球区的d n a 序列的c g r 。我们可以看到 它的点的分布并不是均匀的随机的，而是有一定的图案的，比较明显的就是它的右上 第二章基因序列的可视化方法 角的“d o u b l e s c o o p 和图形的自相似性。 2 3 1c g r 的性质 c g r 是d n a 序列的可视化表示，我们希望能够通过c g r 来研究d n a 序列。 c g r 和d n a 序列很多方面的联系我们还没有发现或者是缺少数学的解释，下面给出 c g r 的几点基本性质： ( 1 ) c g r 中画出的第k 个点对应序列开头的k 个字符组成的序列，也就是序列的长为k 的前缀。两者一一对应。 ( 2 ) 序列中邻接的字符，在c g r 中不一定靠得近。在c g r 中靠得近的点，并不表示他 们对应的字符在序列中邻近。所以在c g r 中欧拉距离有了不同的内涵。 ( 3 ) 在边长为l 的c g r 中，如果两个序列具有相同后缀，相同后缀的长度为k ，那么它 们必在同一个边长为2 靠的正方形格中。对于正方形格的中心，我们递归的定义如下： 后缀长为0 的正方形的中心为( 1 2 ，1 2 ) ； 如果包含后缀0 3 的正方形格的中心在( x ，”，那么： 包含后缀0 3 a 的正方形格的中心在( x 2 ，y 2 ) ； 包含后缀0 3 c 的j 下方形格的中心在( x 2 ，( y + 1 ) 2 ) ； 包含后缀0 3 9 的正方形格的中心在( ( x + 1 ) 2 ，y ) ； 包含后缀仞t 的正方形格的中心在( ( x + 1 ) 2 ，( y + 1 ) 2 ) ( 4 ) 由于c g r 跟序列的对应关系，c g r 中的每一个细节都反映了一定的序列结构。一 个区域的点分布的越稠密，说明与该区域对应的后缀的数目越多，相反地一个区域的 点分布的越稀疏，说明与该区域对应的后缀的数目越少。 总之，c g r 给出了序列中字符出现频率的统计特征，同时也给出了序列的相关性 质，如：一个字符出现在一串后的概率等等。 在用具体的数据运行c g r 算法的过程中，我们发现从来没有出现这样的情况：在 一次运行过程中，某一个图案产生了，然后又变模糊，图案消失了；某一图案产生 了，但随着点数的增加又变成了另一个图案。这些不可能发生的情况说明了基因中部 分序列的所具有的特征可以用来代表整个序列的特征，这就很好的为c g r 的基因签名 提供了依据，下一节我们就来看看c g r 的基因签名。 2 4c g r 基因签名 2 4 1 基因签名介绍 k a r l i n a n db u r g e 提出了基因签名的概念。基因签名这个概念是在用二核苷酸相对 含量d r a p s ( d i n u c l e o t i d er e l a t i v ea b u n d a n c ep r o f i l e s ) 1 0 】研究物种的时候提出的。二核 ， 苷酸x y 的相对含量表示为p x r = 号等，其中厶表示序列中二核苷酸x y 出现的频 j x j l ， 率，厶， 分别表示序列中单核苷酸x ，单核苷酸y 出现的频率。通过研究发现来 9 江南大学硕十学位论文 自相同组织的d n a 序列样本的d r a p s 比来自不同组织的d n a 序列样本的d r a p s 彼 此更加相似。从中我们得到这样的结论：d r a p 的值组成了一个组织的基因签名。 实验显示，同一个基因的不同片断的c g r 图的差异比不同基因的c g r 图的差异 小。这些事实为基因签名提供了有力的证据，证明c g r 提供了一种独特的基因序列的 可视化模式，它是一种功能强大的分析工具。 2 4 2c g r 的频率矩阵一一f c g r c g r 原来的形式用计算机来处理不是很方便。这罩我们介绍从c g r 抽取的频率矩 阵( f c g rt h ef r e q u e n c ym a t r i xe x t r a c t e df r o mac g r ) 1 1 】。一个序列s 的k 阶f c g r 是一 个2 七2 七的矩阵，记作f c g r k ( s ) 。为了得到f c g r ，我们首先画出序列s 的c g r ，然 后把得到的c g r 分成2 七2 七个网格，这样，每一个网格就对应了矩阵中的一个元素， 数出每一个网格中的点的数目，网格中点的数目就是相应矩阵位置的元素。我们不数 网格线上的点，它们是由序列的前缸1 个字符产生的。在足够长的d n a 序列中，我们 可以忽略这髓1 个点。f c g r 是一个数字矩阵，而不像c g r 那样得到一个图。 。 f c g r 也能够直接得到，。不需要先画出c g r ，然后把c g r 转换为f c g r 。我们可 以通过数出序列中每个长为k 的低聚核苷酸的出现次数，再把它们放到矩阵中的相应 位置，这样得到得的f c g r 上一中方法得到的f c g r 相同。 下面给出了1 阶和2 阶f c g r ： 一心，= 眨甜一= n c c n 1 c n c n u n g c n r c n g n e n c g n b g n c f n t n g g n 阳 n g t n r r 删m 的计算可以通过把脚小) 中的每个元素以川- - i ( n c 删x 跫卜换得到。 2 5 后串理论的介绍 把任意七个字符组成的连续的字符串叫做k 串，字母集为 g ，c ，a ，t ) ，给定值就 可以得到4 个不同的k 串。为了计算出已知d n a 序列中每种k 串出现的频率，这里引 入一个2 x 2 的计数矩阵，每个位置都对应一个计数器。 当肛l 时，矩阵m = 写； ：而拓2 时，即为两个m 相乘 1 0 第二章基冈序列的可视化方法 为了方便计算，用二迸制数0 、l 表示矩阵元素的下标。例如： m o o = g ，m o i = c ，m i o 2a ，m i l = t 那么m 似中的一般元素的二进制下标即可表示为 m 羚= m l m i 2 矿m k j i ， 其中i = f l 如，j = 五五五。如此一来，每个k 串都一个计数器对应于m 似中下标 为( 歹，歹) 的元素。每个计数器都被分配了两个指标，索引值i n d e x 和整数型坐标( x ，y ) ( 对 应的二进制值为( ，j ) ) 。这里所采用的坐标轴，x 轴的方向是自上向下，y 轴的方向是 自左向右。 定义一个映射 口： g ，c ，a ，丁) i - - ) 0 0 ，0 1 ，1 0 ，1 1 ) ， 假设现有一长为的d n a 序列 s i s 2 s 3 ，s k s n i , s n 其中s j g ，c ，a ，t ) 。模拟一个宽度为k 的滑动窗口，使其沿着d n a 序列滑动，这样 就可以读取所有的k 串。有些d n a 序列是线型的，有些d n a 序列是循环的( 例如细 菌) ，所以搜