（计算机软件与理论专业论文）使用随机投影技术发现生物序列特征的算法.pdf

毪蛾大学镳器i 程学虢硅尊敬较粹专证碛- 学位诧直 摘要 “e 较数兆碱基的d n a 序列是发现和标记保守的基因组特征普遍使用的技 术，进行这样的比较可以发现长达几十兆的序列之间很多短的局部对齐。为有 效地处理这样的长序列，已有的算法通过扩展短的、不含替换及其他不同之处 的匹配碱基串来发现对齐。但是，精确匹配的碱基串太短，在重要的相似性中 出现的这种匹配串也会偶然出现在背景序列中，因此对于不含长的精确匹配串 的序列，算法必须平衡发现序列特征的效率和敏感性。，7 一- w 本文首先分析了两种降低相似搜索算法复杂度的方法：过滤试探法和确定 的排除法。f 对于高于用户指定闽值的相似性，确定的排除算法确保具有1 0 0 敏感性。但是，对于相似度低，但实际上有趣的相同度水平6 5 7 0 的大规模 全体成对问题，其敏感性不好。字匹配过滤试探法在实践中更有效一些，但其 敏感性无控制地依赖于有趣的相似性中突变的分布，并且当相同度在6 7 左右 时，其效率和敏感性显著衰退。厂j ， 在分析以上两种方法的基础上，本文提出了一种新的算法：r p a l l - p a i r 曼 算法? 该算法通过随机投影发现基因组序列中含有特定部分的替换的无间隔局 部对齐。( 这些对齐的长度和替换率可以选择，使其在重要的相似性中出现频繁， 而在背景序列中出现很少。r p a l l - p a i r s 使用位置敏感散列函数来获取d n a 序列的随机投影。在位置敏感散列函数下，两个串投影值相同的概率直接随它 们的相似度不同而变化。将随机方法应用于相似搜索打破了维的制约，在相似 度低至6 7 的无间隔相同度时，得到比确定性的排除算法( 如双过滤算法) 本 质上更好的性能在实践中标记基因组特征时，r p - a l l - p a r s 和字匹配技术 互为补充，使用它可发现用相对短的字长难以发现的生物学上有趣的相似性。 本文还分析了算法的性能，并在此基础上讨论了如何给r p a l l - p a i r s 选 择最优化的参数及算法实现的细节问题，通过实验证实了r p a l l a i r s 发现 d n a 序列特征时取得了较好的效率和敏感性的平衡。 关键词：基因组d n a 序列特痴数据挖掘j 随机投影y 效率和敏感性 强蛾 信蠹i 程学筏 锋擞赣糌专硪享拉诧文 a b s t r a c t c o m p a r i s o n o fm u l t i m e g a b a s eg e n o m i cd n as e q u e n c e s i sa p o p u l a r t e c h n i q u e f o r f i n d i n g a n d a n n o t a t i n g c o n s e r v e d g e n o m e f e a t u r e s p e r f o r m i n gs u c hc o m p a r i s o n se n t a i l sf i n d i n gm a n y s h o r tl o c a la l i g n m e n t s b e t w e e ns e q u e n c e su pt ot e n so fm e g a b a s e si nl e n g t h t op r o c e s ss u c h l o n gs e q u e n c e se f f i c i e n t l y ，e x i s t i n g a l g o r i t h m s f i n d a l i g n m e n t sb y e x p a n d i n ga r o u n ds h o r tr u n so fm a t c h i n gb a s e sw i t hn os u b s t i t u t i o n so r o t h e rd i f f e r e n c e s u n f o r t u n a t e l y ，e x a c tm a t c h e st h a ta r es h o r te n o u g ht o o c c u ro f t e ni ns i g n i f i c a n ta l i g n m e n t sa l s oo c c u rf r e q u e n t l yb yc h a n c ei n t h eb a c k g r o u n ds e q u e n c e t h u st h e s ea l g o r i t h m sm u s tt r a d eo f fb e t w e e n e f f i c i e n c ya n ds e n s i t i v i t yt of e a t u r e s w i t h o u t l o n ge x a c t m a t c h e s i nt h i sp a p e r , w ef i r s ta n a l y s et w os c h e m e st or e d u c et h ec o m p l e x i t y o fs i m i l a r i t ys e a r c h a l g o r i t h m s ：f i l t e r i n g h e u r i s t i ca n dd e t e r m i n i s t i c e x c l u s i o nm e t h o d t h ed e t e r m i n i s t i ce x c l u s i o na l g o r i t h m sa l ed e s i g n e dt o h a v e1 0 0 g u a r a n t e e ds e n s i t i v i t yt os i m i l a r i t i e sa b o v eau s e r - s p e c i f i e d t h r e s h o l d ，b u tt h e yd on o ts c a l ew e l lt ol a r g ea l l - p a i r sp r o b l e m sa tl o wb u t p r a c t i c a l l y i n t e r e s t i n gi d e n t i t y t h r e s h o l d so f6 5 7 0 p r a c t i c a lw o r d m a t c h i n gi sm u c h m o r ee f f i c i e n ti np r a c t i c e ，b u ti t ss e n s i t i v i t yd e p e n do n t h ed i s t r i b u t i o no fm u t a t i o n s i nt h e i n t e r e s t i n g s i m i l a r i t i e si na n u n c o n t r o l l e d w a y ，a n d i t s e f f i c i e n c y o r s e n s i t i v i t y a l s o d e c a y s s u b s t a n t i a l l yf o rs i m i l a r i t i e sa r o u n d6 7 i d e n t i t y b a s i n go nt h ea n a l y s i so f a b o v et w oa l g o r i t h m s ，w ep r o p o s ean e w a l g o r i t h m ，r p a l l - p a i r s ，w h i c hu s e sam e t h o do f r a n d o m i z e dp r o j e c t t of i n da n g a p p e dl o c a la l i g n m e n t si ng e n o m i cs e q u e n c ew i t hu pt oa s p e c i f i e d f r a c t i o no fs u b s t i t u t i o n s t h el e n g t ha n ds u b s t i t u t i o nr a t eo f t h e s e a l i g n m e n t s c a nb ec h o s e ns ot h a t t h e ya p p e a rf r e q u e n t l y i n s i g n i f i c a n ts i m i l a r i t i e sy e ts t i l l r e m a i nr a r ei nt h eb a c k g r o u n ds e q u e n c e r p - a l l - p a r so b t a i n sr a n d o m i z e d p r o j e c t s o fd n as e q u e n c e s b y 4 擐 l _ 天学信息i 程学硫诖苒艟赣蚌专韭碛学垃论文 l o c a l i t y s e n s i t i v eh a s hf u n c t i o n ，u n d e r w h i c ht h et w o s t r i n g sp r o j e c tt ot h e s a m ev a l u ev a r i e sd i r e c t l yw i t ht h e i rd e g r e eo fs i m i l a r i t y a d o p t i n ga r a n d o m i z e da p p r o a c ht o s i m i l a r i t ys e a r c hb r e a k st h r o u g ht h e c u r s eo f d i m e n s i o n a l i t y ， a c h i e v e d s u b s t a n t i a l l y b e r e r p e r f o r m a n c e t h a n d e t e r m i n i s t i ce x c l u s i o na l g o r i t h m s ，s u c ha sd o u b l ef i l t e r a t i o n ，a tl e v e l so f s i n f i l a r i t ya sl o w a s6 7 u n g a p p e di d e n t i t y i np r a c t i c e ，r p a l l - p a i r s c o m p l e m e n t sw o r dm a t c hf i l t e r i n gt e c h n i q u e s f o ra n n o t m i o nb e c a u s ei t f i n d sb i o l o g i c a l l ym e a n i n g f u ls i m i l a r i t i e st h a ta r ed i f f i c u l tt od e t e c tu s i n g e v e nr e l a t i v e l ys h o r tw o r d l e n g t h s i nt h i sp a p e r , t h ea n a l y s i so ft h ep e r f o r m a n c eo fr p a l l a i r si s g i v e n ，a n dh o wt o c h o o s eo p t i m a lp a r a m e t e r sf o rr p a l l - p a i r si s d i s c u s s e db a s e do nt h ep e r f o f i n a n c es t u d y o u re x p e r i m e n ts h o w st h a t r p a l l p a i r sa c h i e v e sab e t t e rt r a d e o f fb e t w e e n e f f i c i e n c y a n d s e n s i t i v i t yi nf i n d i n gf e a t u r e so f d n as e q u e n c e k e yw o r d s ：g e n o m i cd n as e q u e n c ef e a t u r e s ，d a t am i n i n g ，r a n d o m i z e d p r o j e c t ，e f f i c i e n c ya n ds e n s i t i v i t y 5 通 l l 大学糖昏i 程学硫计锋巍辕 牛专蛙蠢士学位诧熏 1 1引言 第一章绪论 从商务管理、行政管理到科学研究，计算机技术的应用已渗透到社会生活 的方方面面，万维网作为全球信息系统，使人们置身于数据和信息的汪洋大海 之中，存储的各类信息和数据呈爆炸式增长，如何从中挖掘到有用的“金子“一 知识和模式，这对新技术和自动工具提出了挑战，数据挖掘于是应运而生，数 据挖掘通常又称为数据库中的知识发现( k d d ) ，即自动方便地在大量数据信 息、海量数据库中发掘隐藏的模式和知识，用来为管理决策、科学研究等提供 有价值的信息。 数据挖掘是二十世纪八十年代后期出现的，在九十年代有了突飞猛进的发 展，并展示了十分广阔的前景。数据挖掘涉及多个学科，从多个学科汲取营养。 这些学科包括数据库技术、人工智能、神经网络、统计学、模式识别、知识库 系统、信息检索、高性能计算和数据可视化。 数据挖掘是一门广泛应用的新兴学科，数据挖掘的一般原理与针对特定应 用领域需要的有效的数据挖掘之间还存在不小的距离。在过去的十年里，生物 医学研究有了十分迅猛的发展，从新药的开发、癌症治疗的突破，到通过大规 模序列模式和基因功能的的识别来研究人类基因，在此过程中形成了基因组学 ( g e n o m i c s ) 和人类基因组计划( h u m a n g e n o m e p r o j e c t ，h g p ) ，其最终目的是 对生命进行系统地和科学地解码，以此达到了解和认识生命的起源，种间和个 体间存在差异的起因，疾病产生的机制以及长寿和衰老等生命现象。 近年来，随着分子生物学，特别是人类基因组计划的实施，不断产生出巨 量的分子生物学数据，如核甘酸序列。这些数据有着数量巨大和关系复杂等特 点，不利用计算机根本无法实现数据的存储和分析。 目前基因研究中的一个重点关注的内容是d n a 序列的研究，因为这种序 列构成了所有活生物体的代码，数据挖掘中存在许多有意义的序列模式分析和 相似检索技术，因此数据挖掘成为d n a 分析中强有力的工具。 1 2d m 在生物信息中的应用 二十一世纪初，大规模基因组成为理解有机生物学的重要工具，获取多种 完整的基因组序列帮助生物学家们形成和验证关于基因组是如何组织的，组织 6 器学信息i 撵学硫n 算挽软件手8 n _ r 学垃诧文 是如何进化的，基因组如何编码活组织的可观察的特性的。所要探索的关键问 题包括：基因组的什么部分编码如新陈代谓 、激增及程序化的死亡等主要功能 的? 非蛋白质编码的d n a 是如何组织的? 它的什么部分是功能重要的? 选择 的压力如何作用在基因复制和突变的随机过程来产生复杂得像：眼睛、翅膀和 大脑等机构的? 尽管人类与蠕虫和苍蝇有很多相同的基因，为什么看起来那么 不同? 九十年代以前，分子生物学家只能间接地探索基因组的含量和功能，不然 要花费很大代价。间接的技术有g i e m s a 和基于c o t 的测量基因组中得到的全 局信息提供的重复结构含量的方法。获得完整的序列后，发现只有其中一些短 的区域具有重要功能，常常需要进行长时间昂贵的连接绘图进行局部化，然后 克隆并最终排序出有趣的最小区域。排序d n a 花费的代价和时间使得它只是 在用其他的手段发现某一区域是重要的情况下，应用于特殊点的工具。 近来，高吞吐量排序使得能够用直接的方法研究基因组。应用这些新技术， 生物学家已获得愈来愈多的从病毒到原核生物到单细胞生物和多细胞真核生物 的大型完整的基因组序列。现在所获得的基因组包括高级的多细胞生物，如果 蝇、开花植物和智人。有这些生物体本质的完整常染色质为后盾，可直接探寻 碱基频率和重复结构的含量等全局特性，很快获得潜在有趣区域的序列，并且 对比两种或更多生物体之间相应的基因d n a 长片段，可能会发现最令人激动 的知识。数据挖掘技术为自动分析长的大量的基因序列提供了有力的武器。 目前d m 在生物信息中的主要应用包括基因区域的预测、基因功能的预测 和基因的分子进化的研究。有两种识别基因的计算策略：1 ) 外在方法，利用已 知的或推荐的基因和蛋白质库，通过数据库的相似性搜索来识别；2 ) 内在方法， 使用概率隐藏马尔可夫模型( h i d d e nm a r k o vm o d e l s ) 预测蛋白质编码区域，隐 藏马尔可夫模型把d n a 序列看成一个随机过程，由于编码和非编码的d n a 序 列在核苷酸选用频率上有所不同，故对应于不同的马尔可夫模型，这些马尔可 夫模型的统计规律是未知的，h m m 能够自动地找出它们隐藏的统计规律。 衡量发现生物序列特征算法优劣的标准除了在算法设计中所述的时、空复 杂度指标外，还有两个：敏感性和特异性。假设待测序列中有m 1 条序列是基 因序列，剩余的m 2 条为非基因序列。用程序对待测基因进行预测，n 条被预 测为基因，其中n 1 条确为基因( n 1 c m l ) ，其余n 2 条不是基因( n 2 c m 2 。) 敏感性定义为n 1 m 1 ，它表示程序预测的能力，特异性定义为n 1 n ，它表示 预测结果的可信度，它们是一对矛盾，应妥善处理敏感性和特异性之间的平衡。 1 2 1 基因区域预测算法 7 括坍天学信息i 程芋嚣i 于葬机获释专业嗣士芋蛀瞎文 所谓基因区域的预测，一般是指预测d n a 顺序中编码蛋白质的部分，即 外显子部分。现在基因区域的预测已经从单纯的外显子预测发展到整个基因结 构的预测，综和各种外显子预测算法和对基因结构信号的认识预测出可能的完 整基因。 预测外显子的算法早期有o r f ( o p e nr e a d i n gf r a m e ) 法，在细菌基因组中， 蛋白质编码基因从起始密码子到终止密码子的长度平均为1 0 0 0 b p ，而跃于3 0 0 b p 的o r f 平均每3 6 k b 才出现一次，故只要找出序列中最长的o r f ( 3 0 0 b p ) 就能相当准确地预测出外显子。 核苷酸字( n u c l e o t i d ew o r d s ) 选用频率的统计差异也可用来区分编码和非 编码区域( c l a v e r i ej ma n db o u g u e l e r e tl ，1 9 8 6 ；b e c h m a n ne ta 1 1 9 8 6 ) ，这是由于 编码和非编码区密码子的选用和周期特征存在差异。例如：6 核苷酸的选用存 在显著的差异，目前各种预测程序中这种方法使用广泛。 为预测整个基因结构，广泛地用来将预测出来的各个外显子和内含子拼接 成完整基因的算法是动态规划算法( d y n a m i cp r o g r a m m i n g ) ( g e l f a n dm sa n d r o y t b e r gm a ，1 9 9 3 ) ，它将各种可能的拼接进行记分，从而得出最可能的基因结 构。 除上述的算法外，用于基因区域预测的算法还有：法则系统( r u l e b a s e d s y s t e m ) ( g u i g or e ta 1 1 9 9 2 ) ；语言学系统( l i n g u i s t i cs y s t e m ) f d o n gsa n ds e a r l s d s ，1 9 9 2 ) ；决策树( d e c i s i o nt r e e ) ( s a l z b e r gs ，1 9 9 5 ) ；s p l i c e da l i g n m e n t 算法( g e l f a n d f se ta 1 ，1 9 9 6 ) ；傅立叶分析( f o u r i e r a n a l y s i s ) ( t i w a r ise ta 1 ，1 9 9 7 ) 等。 1 2 2 基因功能预测算法 预测出来的基因被实验手段证实后，第二步是要找出它的功能。将新发现 现的一段核甘酸序列进行数据库检索并作同源性比较，是预测新基因功能的重 要手段。同源性比较分整体对齐( 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 ) 两大类。整体对齐对两个序列的全长的相似性作出判断，局部对齐对两个序列 是否有局部序列的相似性进行判断，由于数据库中许多基因的序列是不完整的， 分子生物学家们对序列中的保守顺序比对非保守顺序更感兴趣，故数据库检索 的同源比较算法以局部对齐对主要手段。 目前最流行的可用于局部对齐的算法有s m i t h w a t e r m a n 算法，f a s t a 和 b l a s t 。 严格的动态规划算法，如s m i t h - w a t e r m a n 算法计算两个序列的最大可能的 相似性，可处理碱基替换和间隔( g a p ，包括缺失和插入) 具有最高的敏感性， 替蟪太学箍悫i 程学甓计篝掇赣 牛专址爵士譬杖诧霆 可以找出相似性较差的同源序列，但这种算法计算量相当大，对于一对长度分 别为m 和n 个元素的序列对齐需要0 ( r i l l l ) 次比较，所以用此算法进行大量 的数据库检索只能在超级计算机或大型并行计算机上才能实现。 f a s t a 及其早期版本f a s t p 牺牲了一点敏感性，但大大提高了速度。在 一些实际的检索比较中，f a s t a 的结果与s m i t h - w a t e r m a n 算法的结果的相关 系数达到0 , 8 5 0 9 9 ( b r u t l a gd l c ta 1 1 9 9 3 ) ，而速度可达到s m i t h - w a t e r m a n 算 法的2 0 倍，如果只运行前三步，f a s t a 的速度是s m i t h w a t e r m a n 算法的6 0 倍( p e a rw r ，1 9 9 1 ) 。 b l a s t 算法( a l t c h u ls fe ta 】，1 9 9 0 ) 速度可达到f a s t a 的几倍到几十倍， 它不考虑间隔问题，敏感性比f a s t a 更差。g a p p e db l a s t 和p s i b l a s t ( a l t s c h u ls fe ta 1 ，1 9 9 7 ) 是对b l a s t 算法的改进，不但可以处理间隔问题， 大大提高敏感性，同时提高了程序的速度，达到原b l a s t 算法的3 倍，但b l a s t 算法的很显著的优势是在检索中估计比较的统计显著性，这是g a p p e db l a s t 和p s i b l a s t 所不能取代的。 1 2 3 用d m 进行分子进化的研究 预测新基因只是生物信息学研究的一个方面，这门学科的根本目标是发掘 隐藏生物数据后面的生物学知识，对于基因组研究的一个重要的研究方向是分 子序列的进化，通过比较不同生物基因组各种结构成分的异同，可促进我们对 生物进化的认识。这方面的研究已逐步形成一个新学科一比较基因组学 ( c o m p a r a t i v eg e n 0 1 1 1 i c s ) ，各种基因结构成分的进化，密码子使用的进化，进 化树的构建及各种理论上和实验上的课题都等待研究。 1 3 研究的主要内容 在这篇论文中，我们着眼于应用相似性搜索与比较技术解决基因组学的特 殊问题：如何发现长d n a 序列的哪一部分编码特殊的生物特征，如基因。即 使获得整个序列后进行检查，发现这些特征也非常困难。如果对查找的特征一 无所知，或序列中这些特征表现很弱，要找出它们在理论上是难以做到的，实 际中也超出了计算时间和空间的限制。本文着重于用新技术发现理论上难以发 现的和已有算法不好处理的特征。 本文中提出的是建立在普遍技术基础上的随机投影的算法，利用这样一个 直觉：两个近乎一致的生物序列无论它们在何处不同，都不会有很多不相同的 特征。过去挖掘确定类型的序列特征代价太高，使这种序列特征难以发现，本 文给出如何应用上述的直觉降低发现确定类型的序列特征的代价，能够较容易 9 毽摊大学信息i 程字硫计篝鞔赣肆专韭聩圭学较诧吏 地挖掘更有趣的特征，为生物学家提供更完整的信息。 1 4 论文内容安排 第一章介绍d m 在生物信息中的应用现状，主要介绍了已有的关于基因区 域预测、基因功能预测使用的算法及k d d 应用于分子进化研究方面的情况。 第二章介绍生物学背景及重要性：说明基因组d n a 及其包含的几种有意 义的特征，然后讨论发现和标记这些特征的基本问题。 第三章描述基于序列相似性的比较标记的思想，讨论其优点及局限性，最 终集中阐述由此产生的计算问题。 第四章解决长基因序列全配对的局部对齐问题。给出了形式的问题及其一 些应用后，介绍用到的随机投影的基本理论。用此理论给出r p a l l - p a i r s 算 法，它能够有效地解决有较低相似性无间隔的局部对齐问题。然后说明如何在 实际中实现算法并在有趣的生物序列集上有效地执行。 第五章给出r h a l l p a i r s 实验结果及结论。 1 0 嚣博大学蓓塞i 控学碗讨算机鞍搏专照磺学位论文 第二章生物学背景 研究算法来发现基因组特征的前提是要明白在寻找什么和为什么寻找，在 此对基因组d n a 及其主要特征作简要的回顾。 2 1d n a 和基因组序列 基因组分析的最基础的物质是d n a ，即脱氧核糖核酸，d n a 是由一个聚 合分子构成的，聚合分子是由核苷酸一碱基构成的，碱基有4 个，用a 、c 、 g 、t 来表示。它们表示组成d n a 的字母( 分别表示腺嘌呤，胞嘧啶，鸟瞟呤， 胸腺嘧啶) ，实际的d n a 就由这些字母代表的物质组成，d n a 序列可抽象为 在字母表 a ，c ，g ，t 上的“串”，本文中“串”和“序列”两个术语可互换。 通常d n a 由两股互补的链组成，这种互补的链是由碱基对序列组成的， 碱基配对是确定性的：a 总与t 相配对，c 总与g 配对，因此一股链决定它的 另一股互补链的构成，描述d n a 序列时只需描述其中之一即可。由于这种配 对，碱基分为弱强两种( a t 弱，两个氢键连接，g c 强，三个氢键连接) 。还 有另外一种从化学结构分为嘌呤和嘧啶，一个未明确的嘌呤或嘧啶分别用r 和 y 来表示。 d n a 分子存在于原核生物的细胞浆和真核生物的细胞核，一个细胞全部 的d n a 序列就称为基因组，在多细胞生物中，实质上除了配殖体含有二套基 因组外，和物种之间的基因组的差异相比，一个物种生物之间的基因组序列差 异很小，因此谈及全部物种的基因组就很有意义。举个例子，人类基因组长度 为3 1 0 9 碱基对，在个体之间9 9 9 是相似的，而和人类最近的类人猿只有 9 8 - - 9 9 和人类是相似的。 生物体的遗传物质组成了少量互不相同的d n a 分子，即染色体，典型的 细菌有单股环状的染色体，它有几百万个碱基。真核生物细胞内有3 到1 0 0 个 线状的染色体，碱基从几千万到几十亿个不等。表1 1 列出了生物学家们普遍 研究的典型生物的碱基数目。一个物种内基因组分裂成染色体的变化不明显， 因此对染色体进行编号就很有意义，例如按长度的降序进行编号，如“人类1 号染色体”。 d n a 的一个很重要的特征是随着时间的推移，它不是静止的。化学物质、 射线、复制差错能造成d n a 序列的突变，生物学上普遍的突变类型包括替换， 即一个碱基被另一个碱基取代，还有移码突变( 插入和删除) ，即在序列中加 入或去除碱基。不同类型的突变发生的比率不同，如，转换替代一a 被g 取代 毽* 大学镶毽i 程学虢计篝执孰 牛专硪j - 学位诧史 或c 被t 取代一的发生率约是其它一般的替代( 称为颠换) 发生率的二倍。 表2 1 生物学家普遍研究的典型生物体基因组的大小，对于真核生物，表 中给出的是染色体的数目和大小 生物体俗称染色体号基因组大小 ( 组染色体)( 兆碱基) 大肠杆菌( 一种细菌) 1 4 4 s c e r e v i s i a e酵母菌 1 6 1 2 c e l e g a n s( 线虫) 6 1 0 0 4 1 2 0 ( e n c h r o n m a t i c ) d m e l a n o g a s t e r 果蝇 a t h a l i a n a 十字花科植物 5 1 2 5 m m u s c u l u s 2 0 实验小鼠 3 0 0 0 h s a p i e n s 2 3 ( 人的一种) 3 0 0 0 2 2 d n a 王国：基因组序列特征 一个基因组被抽象地认为是长的碱基串，但这样的抽象概念对于认识其在 细胞中的功能不太有用，好的模型就像一根线上的许多“珠子”，每个珠子” 代表一个序列特征。我们可以将一些生物学的解释和功能归因于基因组的一个 短子串，不是每个子串都落在基因组的特征范围内，序列中那些分隔基因组特 征的“串”的部分称作背景序列。 本文所考察的序列特征大致上分为三类：基因一编码完成细胞功能的 活性分子，调控位置一控制基因的行为，还有重复成分。 2 2 1 基因 基因是基因组序列的主要功能成分，编码结合其它的多聚合分子的指令。 从分子生物学的角度看，基因是负载特定生物遗传信息的d n a 分子片段，它 在一定的条件下能够表达这种遗传信息，产生特定的生理功能。基因的基本功 能是将其d n a 序列转录成相应的r n a 聚合体。除了碱基t 用u 替代外，r n a 分子的序列和其模板d n a 相同，如图1 1 a 基因被r n a 聚合酶转录，首先r n a 聚合酶读其d n a 序列，然后将细胞内游离的r n a 核甘酸聚合在一起转录出 r n a 序列。很多基因产生信使m r n a ，m r n a 可被翻译成蛋白质- - 2 0 种氨基 酸的聚合体，核糖体是另一种大分子的复合体，执行蛋白质的翻译，不像d n a 到r n a 的转录是1 ：1 的配对，翻译需要三个碱基也即密码子编码一个氨基酸， 毽 l l 太学信塞i 程学鞔诗肆歌软转专谴疆土学往诧熏 如图1 1 c 所示，这种组合其实是退化的结果，即多达6 个不同的密码子编码一 种相同的氨基酸，蛋白质的序列决定了它最终的三维形状，其三维形状决定蛋 白质在细胞中的功能。 并非每个m r n a 的碱基都参与编码蛋白质，m r n a 的翻译从第一个密码 子延伸至最后一个密码子，在这序列内，由于起始序列从a u g 密码子开始， 遇到三个终止子( u a a 、u a g 、u g a ) 之一结束，因此，编码序列是有限的， 真核基因经常是不连续的，由插入的内含子将外显子分开，整个基因包括内含 子和外显子，都转录成前体m r n a ，之后，内含子被切除，外显子连接起来成为成 熟的m r n a ，如图1 1 b 所示，剪接的过程由连接小体完成，连接小体能识别特殊 的序列模式作为信号来决定从什么地方切除。 一些基因的r n a 不被翻译成蛋白质，它们在生物学功能上却是活性分子， 此类r n a 包括t r n a 和各种各样的r r n a 及其它一些分子复合体，而t r n a 在翻译中匹配r n a 密码子特定的氨基酸，少数情况下，m r n a 也能逆转录成 d n a 。 基因组最基础的物质d n a 和背景序列相比必须具有显著的序列特征，编 码的外显子倾向于序列的构成：它们的位置取决于蛋白质中氨基酸使用的频 率，且其内部不能含有终止子。常用的氨基酸的密码子比其它密码子用得多， 更趋向于特定的序列，大多数基因有很多独特的信号序列，包括前面提到的切 除信号、起止和终止转录的信号，这些独特的基因特征已被计算机基因预测器 利用，如识别原d n a 序列中基因的g r e e na n dw i l i s o n 的g e n e f i n d e r , b u r g e 和 k a l i n 的g e n s c a n 。值得注意的是功能重要的基因只是高级真核生物基因组序 列的一小部分，特别是编码序列只占人类基因组的i 4 2 2 2 调控位置 一种生物并不是任何时刻或在它的各种组织中都使用基因组中每个基因 的产物。例如，每个有核人体细胞都含有分泌胰岛素的基因，但只有胰腺的一 些细胞能产生胰岛素，类似地，编码蛋白质的基因在细胞分裂过程中一直存在， 但它们的产物只在细胞分裂实际发生的细胞周期中的短暂时间内才产生，因此 细胞有一些调控机制来控制何时何地基因表达来生产其产物。 本文中仅着重考察一种特殊的调控形式：一组称为转录因子的蛋白质对基 因转录的控制。这些蛋白质附着在基因组d n a 的结合位点上，这些结合位是 几十个碱基长的含有特殊因子序列的区域。转录因子经常结合在基因开始的称 为启动子和增强子的几百个碱基处。转录因子在这些区域影响r n a 聚合酶启 1 3 秘媸天学话密i 狴学靛计算执鞍嚣专韭嗣士学毽诧文 图1 i 基因组编码序列形成蛋白质的处理过程。( a ) 基因序列被r n a 多 聚合酶转录形成前体m r n a ( b ) 内含子被切割酶从前体m r n a 切割出来， 产生过程m r n a ( c ) h a lm r n a 被核糖体翻译产生蛋白质。 动转录的频率如果转录因子提高基因的表达水平就称作增强子，若它降低基 因的表达水平称为抑制因子。 当细胞的环境如各种化学物质( 包括其它基因的产物) 的数量发生变化时， 转录因子常被激活，因此对变化的外部条件及响应特殊化学信号而执行的“程 序”如细胞分裂、分化、死亡，这些蛋白质能够协调细胞对上述情况进行转录 响应。转录因子将这些变化转换成另一种形式的精确机制也是变化的。很多因 子形成蛋白质复合体和r n a 聚合酶直接结合，增加或降低其与基因的启动子 和启动转录的亲和力。转录因子还改变了与它们相连的d n a 的形态，也改变 了聚合酶与d n a 的亲和力。 多个转录因子可以作用于一个基因，在这种情况下，几个不同的结合位可 能成簇聚在基因附近，这些因子的作用不一定是独立的，总的来说，它们形成 了一个复杂的顺式调控逻辑，这个顺式调控逻辑能很好地控制基因的转录强度 和何时转录。目前只有几个顺式调控逻辑被详细研究过，y u he ta 1 的文章对海 瞻的研究说明了在那样的逻辑中可能存在的复杂性。 转录因子的结合位点可作为重要的序列特征，但在原料基因组序列中它是 很难发现的，这些结合位很可能成簇地存在于启动子控制区，即转录起始位的 毪啦太学辖息i e 镜砖篝枫较棒专韭穰士学论文 儿百个到几千个的碱基，然而重要的调控区在别处也存在，如内含子和基因座 调控区。一般不能用p r i o r i 确定结合位像什么，它们的序列模式非常独立于其 连接的特殊因子。某些类型的转录因子要求结合位的结构是已知的t 如一些二 分同源因子要求d n a 遛文结构，但那样的结构非常少见。 常用的转录因子即使有相同的序列，这种序列的模式也很短，纯粹是在背 景序列中无蛋白质结合的地方偶然出现的。因此发现基因组序列中新的转录因 子聚合位的程序受到缺乏对这些位置特征的识别，以及这些位置是真正的结合 位还是偶然发生的序列模式的混淆两种因素的影响。 2 2 3 重复片段 大部分细菌基因组中9 0 以上的序列是基因的一部分或一个调控位点，但 要完全说明人类、果蝇或线虫的基因组的特征，其中的大多数序列仍无法解释。 这些生物中许多非编码序列源于第三种特征：重复片段或短的重复结构。 重复序列或片段是一个基因组中出现多次的d n a 序列，高等真核生物中 重复结构是非常普遍的，其原因也是众多的。重复片段大致可分为复制和转位 子获得的散在的重复结构两种，复制又分为功能性复制、非功能性复制。 复制具有非常多的特征，可能源于基因组复制时的历史原因，一条d n a 被复制成为2 倍时发生前后复制，可能是由于d n a 多聚酶引起的跳跃或间断， 包括短的前后重复，其中的模式像“c a t ”在任何地方都能复制几倍至几百倍， 以及复制为2 3 份拷贝那么长的前后重复结构，每1 0 0 个碱基中有l o 个碱基的 重复结构较大的前后复制结构业已发现删如人类2 2 号含有l c r - 2 2 重复家族 3 8 ，它有几十个到几千个不等的碱基，2 1 号染色体与4 ，7 ，1 6 ，2 2 号染色体共同拥 有的复制区域达5 0 k 到l o o k 不等的碱基【4 3 】。 含有基因序列的复制是产生假基因的源泉，但也产生了些与原基因功能 不同的新活性基因，源于历史性复制的重要基因( 活跃的和假的) 包括脊椎动物 t - 细胞受体【2 0 】和m h c 基因；在这两个基因族中，历史性意义的复制之后的突变 产生了成群的多种多样的受体分子，使其免疫系统能够识别各种病原体。 散在的重复片段是由完全不同于复制的过程引起的，它们是可置换的， d n a 序列能通过基因组自发地增殖自身。这些片段包括d n a 转座子，它能切 除自己并将自己重新插入基因组中；还包括反转录转座子，它能以r n a 中间体 为媒介，通过逆转录酶复制自己，多数散在片段是没有意义的可置换片段，因为它 们在插入过程中被切除或由于突变而失去了活性。 存在着许多可置换的基因族，这里提及的是众所周知的人体基因组中两种 毪 l l 大学话惑i & 字碗n 算8 g f 专n 强t 亨位诧文 类型的反转录转座子，它们是那里所发现的散在重复结构的根本原因。长的散在 核片段或l i n e 是反转录转座子，有几千个碱基，能进行自主复制产生反转录蛋 白人类l i n e 家族有l i n e l 和老的l 1 n e 2 。 只有l i n e l 显示出活性，l i n e 2 因突变而失去活性。每个l i n e 家族有一 个相应的s i n e ( 短散列核片段) ，s i n e 非常短，不能进行自主复制，使用l i n e 的机制复制自己。人类的l i n e l 的s i n e 是a l u ，它是人类基因组中最丰富的 重复序列，有成百上于份拷贝，l i n e 2 中的s i n e 是m i r 片断，它没有活性。 重复片段和散在重复片段在真核生物基因组序列中占了相当大的比例，人 类多达4 0 以上的非编码序列均为重复片段，其中的一些重复片段是最近被复 制出来的，故易于识别，那些过去的经多次突变已分叉的重复片段较难识别， 用于发现散在重复片段的主要策略是通过其相互之间的相似性定位它的多个 拷贝，然后根据这些能与同一重复族中的其他成员匹配的拷贝建立一个一致序 列。重复发现工具使用按此方式构建的标准重复序列库，重复发现工具包括 s m i t 和g r e e n 的r e p e a t m a k e r 和b e d e u , k o f f 和g i s h 的m a s k e r a i d 等。 1 6 毽* 大c 荸# i m 学筏n 募巍赣粹 焉 垃镕宴 第三章用比较标记法发现序列特征 现在从描述基因组进入关健的标记问题一如何识别原d n a 序列的特征， 本文主要研究用比较进行标记的算法，它比特征化难以发现的生物学特征具有 实质的优点。在这部分简要地列出比较标记的原理提纲，并描述比较d n a 序 列的常规基础，最后举例对比较标记方法的优点和局限进行更详细的讨论。 3 1 比较标记的原理 比较标记法识别特征基于特征的保守性，或依据生物特征在进化过程中变 化很少的事实。虽然所有d n a 序列都受突变的支配，但由于自然选择，现在 只能观察到其祖先的繁殖适应性未被强大的有害突变限制掉的个体。很多基因 或调控因子的突变可使它们功能不良，发生了有害突变的生物体会死亡或其可 生育的后代减少了。相反，非功能性序列中的突变可能对繁殖适应性无影响。 故我们今天所见的生物体的功能序列中的突变比其背景序列中的要少，或等价 地说更具有保守性。类似地许多突变可使转座子变得不活跃，阻止其自身复制， 所以今天所见的丰富的散在重复结构是由经历较少突变的转廖子复制的。 两个序列是相似的如果它们之间的不同之处很少，因为序列特征比背景序 列更具保守性，所以同一特征的两个不同拷贝历时后可能还是相似的。例如对 不同生物体( 比如人和鼠) 的序列进行对比可发现基因或调控区的特征，因为 生物体之间基因或调控区特征比它们的背景序列之间的特征更相似。类似地， 鼠的两个序列之间的对比可识别近期插入的重复结构，通过与背景序列对比， 这两个序列之间的高相似性来进行识别。搜索相似序列是一种有用的检测和标 记基因组d n a 中有生物学意义的特征的方法。 对齐是相似性度量的量化 如果要利用序列的保守性发现生物学上有意义的特征，就必须定义一个精 确的量化序列之间相似性的方法，这样的测量方法是根据序列对齐的概念得到 的。 假设祖先d n a 序列s 0 经突变衍生为分开的两行，产生了现在的序列s 和 8 2 ，如果知道了s - 和s 2