（计算机应用技术专业论文）XAT软件系统设计与实现.pdf

摘要 摘要： 本文的主要工作是通过研究序列比对算法，实现一个c d n a m r n a 序列与 d n a 序列的跨物种比对软件x a t ( c r o s s - a l i g n m e n t t 0 0 1 ) 。本文主要借鉴了b l a s t z 软件的跨物种方法和s i m 4 软件的i n t r o n 与e x o n 的边界确定方法。本文实现的 方法允许多条c d n a m r n a 序列与整个基因组的比对，同时给出结果的统计值， 另外，x a t 软件通过设定配置文件，增加了用户的使用方便性和灵活性，x a t 软件用c 语言编写，容易移植。 本文首先介绍了序列比对的概念、数学模型和一些通用的算法，主要阐述 了一些已有的序列比对的算法和相应的软件。 针对本文实现的x a t 软件，介绍了它的意义，详细介绍了它的实现算法， 并用c 语言实现了x a t 软件，并介绍了x a t 软件的界面、配鬣文件和它的输 出结果的一些格式。 本文的重点是如何实现c d n a m r n a 序列与整个基因组序列的比对，如何 提高它的速度，如何实现它的跨物种特性和如何判定i n t r o n 与e g o n 的边界，如 何对于它的结果进行统计上的描述。在本文中都对它们进行了详细的描述。 最后，采用一种类似g e n e f i n d i n g 程序中采用的方法来对x a t 软件的结果 进行了分析，并且将x a t 软件和一些其他的序列比对软件的结果进行了比较。 关键词：序列比对、跨物种、比对算法、软件、x a t 摘要 a b s t r a c t ： t h ec h i e fw o r ko ft h i st h e s i si st or e s e a r c ht h es e q u e n c ea l i g n m e n ta l g o r i t h m a n d i m p l e m e n t x a ts o f t w a r ew h i c ha l i g nc d n a m r n a s e q u e n c e s w i t hd n a s e q u e n c e s w h i c hc a l lb en o t h o m o l o g o u s w i t hc d n a m r n as e q u e n c e s i t i n c o r p o r a t e ss e v e r a lh e u r i s t i ct e c h n i q u e su s e di nb l a a t za n d s i m 4s o f t w a r e s ，s u c ha s t h ec r o s s s p e c i e sm e t h o di nb l a s t za n dt h em e t h o dp o s i t i o n i n gt h eb o r d e rb e t w e e n i n t r o na n de x o ni ns i m 4 i tp e r m i t sm a n yc d n a m r n a s e q u e n c e sa l i g n i n gw i t h w h o l e g e n o m e ，a n do f f e r st h es t a t i s t i c a lv a l u eo f t h er e s u l t x a t p r o v i d e sc o n f i g u r e f i l e a n dx a ti sw r i a e ni nc l a n g u a g e , s o i t se a s yf o r m i g r a t i o n f i r s d y , t h i s t h e s i si n t r o d u c e st h e c o n c e p t o f s e q u e n c ea l i g n m e n t ，i t s m a t h e m a t i cm o d e la n ds o m e g e n e r a la l g o r i t h m t os o l v ei t i tm a i n l yi n t r o d u c e ss o m e a l g o r i t h m sa n d t h ea c c o r d i n gs o f t w a m se x i s t e dn o w a b o u tx a t i t sm e a n i n ga n d a l g o r i t h ma r ei n u o d u c o d i nt h i st h e s i s a n dx a t h a sb e e ni m p l e m e n t e dw i t hcl a n g n a g e t h ei n t e r f a c e ，c o n f i g u r ef i l ea n do u t p u t f o r m a t sa r ei n t r o d u c e dt o o t h ee m p h a s i so ft h i st h e s i si sh o wt o a l i g nc d n a m r n as e q u e n c e sw i t h w h o l eg e n o m e ，h o wt oi n c r e a s et h ev e l o c i t y , h o wt op o s i t i o nt h eb o r d e rb e t w e e n i n t r o na n de x o na n dh o wt od e s c r i b et h er e s u rs t a t i s t i c a l l y t h e yr r ei n t r o d u c e di n d e t a l li nt h i st h e s i s a t l a s t ，t l s i n ga m e t h o dw h i c hi ss i m i l a rt ot h a ta d o p t e di ns o f t w a r e g e n e f m d i n g , ia n a l y z et h er e s u l to fx a ta n d o o m p a r e i tw i t h q o m ca t h c rs o f t w a r e s k e y w o r d ：s e q u e n c e a l i g n m e n 4c f o s s - s p o e i c s ，a l i g n m e n ta l g o r i t h m ， s o f t w a r e ，x a t 第一章绪论 第一章绪论 1 1 课题的目的和意义 1 1 1 序列比对的意义 序列比对就是序列比较，通过比较给出序列之间的相似性。这里的序列比 较采用的不是序列之间的完全匹配，而是允许序列具有空位。如下面的两条核酸 序列： a ： c a c c a g g a a a c g g c c c g g a t c c c g g c a g c g g c c t g a c c b ：c a c c a g g a a a c 从c c g g a t t c c g g a t c c c g g c t g c g g c c t g a c c 二者的匹配如下： c a c c a g g a a a c g g c “”。- - c c g g a t c c c g g c a g e g g c c t g a c c c f f fi c a c c a g g a 从c 从c c g g a t t c c g g a 代c c g g c t g c g g c c 代a c c c 核酸序列摆的就是d n a 或者r n a 链中的碱基a 、c 、g 、t 或u 的排列顺序“3 ，核 酸的碱基有四种类型，在i ) n a 上它们是腺嘌呤a d e n i n e 、鸟嘌岭g u a n i n e 、胞嘧 啶c y t o s i n e 和胸腺嘧嚏t h y m i n e ，在r n a 上尿嘧啶u r a c i l 代替了胸腺嘧啶 t h y m i n e 。它们分别用它们的首字母缩写来代表即用a 、c 、g 、t u 字符代表。上 面的i 代表两条序列对应位置上的核酸碱基相同。序列中的一代表此序列中此位髓 插入一个空位。 序列比对的理论基础是进化学说。如果两个序列之间具有足够的楣似性， 就可推测二者可能具有共同的进化祖先，经过序列内残基的替换、残基或序列片 段的缺失、以及序列重组等遗传变异过程分别演化而来。序列相似和序列同源是 不同的概念，序列之间的相似稷度是可以量化的参数，而序列是否同源需要有进 化事实的验证。在残基一残基比对中，可以明显看到序列中某些荽【基酸残基比其 它位置上的残基更保守，这些信息揭示了这些保守位点上的残基对蛋白质的结构 和功能是至关重要的，例如它们可能是酶的活性位点残基，形成二硫键的半胱氨 酸残基，与配体结合部位的残纂，与金属离子结合的残基，形成特定结构m o t i f 的残基等等。但并不是所有保守的残基都一定是结构功能重要的，可能它们只是 由于历史的原因被保留下来，而不是由于进化压力而保留下来。因此，如果两个 序列有显著的保守性，要确定二者具有菇同的进化历史，进而认为二者有近似的 第一章绪论 结构和功能还需要更多实验和信息的支持。 序列比对解决的是序列之间的相似性问题，而不是序列之间的同源性问题。 但是根据序列之间的相似性，我们可以推测二者之间的同源性。序列比对虽然不 能赢接解决序列之间的同源性问题但是为我们解决序列之间的网源性问题提供 了很有意义的线索。 序列比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序 列进行比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有 关查询序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大 的帮助。近年来随着生物信息学数据大量积累和生物学知识的整理，通过比对方 法可以有效地分析和预测一些新发现基因的功能。 序列比对的问题是生物信息学研究的一个基本课题之一，经过多年的发展， 已经出现了许多序列比对的方法和相应的软件实现。这些方法和软件都有其适用 的范围，都在一定的问题域发挥着重要的作用。 序列比对是生物信息学研究的一个基本方法，其相应的软件是生物信息学 研究的一个基本工具。 序列比对可以在核酸和氨基酸两种水平上进行，因为我的谋题解决的是在 核酸水平上进行e d n a m r n a 序列与d n a 序列的比对闯题，因此，以下的序列比对 都是指的在核酸水平上进行序列比对。 序列比对有两种方式，一种是两条序列之间的比对，一种是多条序列( 大 于2 条) 之间的比对。我的课题是两条序列之间的比对，以下的序列比对没有特 别说明，都是指的两条序列之问的比对。 1 1 2 序列比对的数学模型 序列比对在生物信息学的研究中占有重要的地位，其方法和实现都是生物 信息学研究的一个重要的方向。序列比对的问题并不象比较两个字符串是否相同 那样简单，序列比对的问题在数学上转化为寻找最优路径的问题，是一个寻优的 问题。其基本算法是动态规划算法。还有一些其他的近似算法，如贪心算法等。 动态规划算法的时间复杂度和空间复杂度都是0 ( m n ) ，其中m 、1 3 是算法矩阵的 行数和列数。序列比对的数学模型如下图所示： 令参加序列比对的两条核酸序列为a 和b 。将a 和b 两条序列分别作为动态 2 第一章绪 论 规划算法矩阵的一维。如图1 1 2 所示 k 弋 、 图1 1 2 动态规划算法矩阵示意图 其中箭头线指示的即为条比对的最佳路径。其结果为： a ： a c c g t c a c t g il | b - a c c g - c a c t g 1 1 3 序列比对的算法 序列比对的问题在数学上为寻找最优路径的问题，因此任何解决寻优问题 的算法都可以用来解决序列比对的问题。现在解决序列比对问题的经典算法是 动态规划算法。 动态规划算法按照解决的问题的不同可以分为全局动态规划算法和局部动 态规划算法，全局动态规划算法解决的问题的是在算法矩阵的左上角和右下角单 元之间( 即全局范围内) 寻找一条最优路径，而局部动态规划算法并不是解决这 样的问题，局部动态规划算法解决的问题是在算法矩阵中寻找一条或者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 算法。 第一章绪 论 经典算法( 全局动态规划算法和局部动态规划算法) 虽然是解决序列比对 问题的最好的算法，但是它们的应用局限性很大。二者的时间复杂度和空间复杂 度都是0 ( m n ) ，m 和n 是参加比对的两条序列的长度。随着序列长度的增加，复 杂度指数上升。假定动态规划算法( 全局和局部) 矩阵的每个单元存贮3 个变量： 最大分值m 、插入分值i 、删除分值d ，每个变量用4 个字节存放，对于两条长 度分别为1 m 和1 k 的序列进行比对，需要的内存最小为1 2 g ，在现有的硬件资源 下，它们不能够应用于长序列之间的比对，对于一条序列与整个基因组进行比对 的任务更是鞭长莫及。 解决序列比对的问题，现在多采用启发式算法和经典算法相结合的方法。 这种方法的思想是首先寻找两条序列中可能相似的区域，然后对相似的区域运用 经典算法求取联配的结果。软件提供给用户一些参数，这些参数用来控制和调节 软件的运行行为，参数的选取对于程序的运行速度和结果精度有着很大的影响。 启发式算法的一般行为都是在运行速度和结果精度之间寻求平衡。而这些又都是 依赖于软件的参数。 在序列比对的算法中( 包括启发式算法和经典算法) ，有两个通用的量对比 对结果的影响很大，它们是替代矩阵和空位罚分。 在图1 1 2 的算法矩阵中，最佳路径的选取标准一般都是依赖于分值，对 于每一条路径赋给一个分值，分值最大的那条路径即为最佳路径。在图1 1 2 中，对于条路径上的任意一个单元m ，可以来自于三个方向，它们分别是从紧 邻的左上角单元，紧邻的上面一个单元，紧邻的左边一个单元。从左上角来对应 于碱基的替代操作，对应的就是一个替代矩阵，对于替代操作赋给的分值就是从 替代矩阵里边提取，其他的两个操作涉及到空位罚分。因为最佳路径的选取标准 是分值的大小，所以替代矩阵和空位罚分对于结果有着很大的影响。 1 1 3 1 替代矩阵 替代矩阵包含了在序列比对中各种碱基取代方式如何赋分的信息，反应了 核酸的碱基相互取代方式之间的相对难易性。残基的取代有不同的倾向性，如在 人和老鼠的替代矩阵中a 、g 倾向于相互取代，c 、t 倾向于相互取代，也就是转 换( t r a n s i t i o n ) 相对于颠换( t r a n s v e r s i o n ) 更容易发生，反应在替代矩阵中 就是对于转换的罚分比颠换的罚分要小。 4 第一章绪论 最简单的替代矩阵是相同不相同的形式，即相同给一个分值，不相同给一 个分值。如下所示： 这种矩阵没有考虑残基相互取代的倾向性，将所有的取代情况一视同仁。 这种矩阵应用于同物种的比对还是很合适的。因为在这种情况下，变异相对来说 是很少的，大部分都是相同的序列。在物种不相同的情况下，例如人的c d n a 序 列和老鼠的d n a 序列进行比对的时候，这种矩阵就不是很适合。因为有了变异 正是有了变异才有了两个物种，因此，我们在对这两个物种进行比对的时候必须 要考虑到变异的情况，也就是必须使用一种考虑变异即残基的取代倾向性的矩 阵，否则比对的结果的正确性要大打折扣。 第二种矩阵考虑了残基之间取代的倾向性。不同的残基取代赋予与之相适 应的一个分值。这种矩阵具有物种相关性。也就是说不同的两个物种之间残基的 取代倾向性也不同，因而其替代矩阵也不一样。下面的矩阵是人和老鼠两个物种 之间的替代矩阵： 厂 。 。 la9 1 一i 1 43 11 2 3 l l c- 1 1 4i 0 01 2 53 1 l l g- 3 1- 1 2 51 0 0一1 1 4 l l t一1 2 33 1一1 1 4 9 1 l 如上图所示：这个矩阵考虑了残基之间取代的倾向性。如a 更倾向于转化 为g 而不是c ，c 更倾向于转化为t 而不是g 等。 在应用序列比对软件进行序列比对的时候，如果软件需要替代矩阵的话， 替代矩阵的选取应该能够很好的反应参加序列比对的两个物种之间的遗传变异 的关系。当然获取这样的矩阵也不是很容易的，一般根据经验或者其他的线索来 选择一个替代矩阵。 因为不同的物种之间替代矩阵一般是不同的，因此在软件设计和编写的时 候最好能够将替代矩阵设置为一个参数，可以由用户输入，这样软件就可以适用 于很多种情况下的比对，固定替代矩阵的软件的灵活性不是很大。应用局限性比 较大，不适合采用。 第一章绪 论 1 1 3 2 空位罚分 两条相似的序列并不总是等长的。由于进化的原因，其中某条序列中的某 个或者某些核酸碱基丢失了，或者新增加了一些核酸碱基。但是它们是从同样的 一个源序列进化而来的，即它们是同源的。 因为它们是相似的，比对的结果应该是两条序列的一个全局比对结果。因 此就需要在某条序列的某个或某些位置插入空位，如图1 1 2 中的比对结果。 对于参加序列比对的两条序列，我们不一定也不可能保证输入的两条序列 是等长的，对于采用全局动态规划算法来说，序列比对的结果中肯定会出现空位。 对于具有空位的两条序列的比对结果，两条序列并不一定是相似的。我们 通过计算比对结果的分值来判断它们是否相似，分值的域值是一个输入的参数， 高于域值的两条序列认为是相似的，低于域值的两条序列认为是不相似的。在给 定域值参数和替代矩阵的情况下，空位的分值就决定了序列的比对结果。即决定 了两条序列是否相似。因此对于空位的分值给的应该适当。数学描述如下： 在上面的比对结果中，有两种情况，一种是对应的位置上都是核酸碱基， 即都是a 、c 、g 、t u 。第二种是对应的位置上一个是核酸碱基，另一个是一即空 位。 令第一种情况的总分为s h ，第二种情况的总分为s k ，比对结果的总分为s z 。 s h 可以根据替代矩阵来求取，s k 即为空位罚分。s h ，s k ，s z 满足： s z s k + s h 在替代矩阵和域值一定的情况下，s h 一定，因此s z 的大小直接和s k 相关。 还有一种空位罚分策略，即对连续一段空位情况。第一个空位相当于开一 个空位，给定一个分值g a p o p e n ，以后的空位相当于是第一个空位的扩展，给定 一个分值g a p e x t e n d ，二者的分值不同，一般开空位应比空位扩展罚更多的分值。 对于序列比对软件来说，默认的空位罚分和空位扩展罚分都是针对某些物 种得到的优化的分值，但是，在应用序列比对软件进行比对的时候，我们可能根 据参加比对的两条序列的特点适当的调整默认的罚分参数。 1 1 4 序列比对的边界问题 序列比对问题本身并不涉及到e x o n 与i n t r o n 的边界的问题，序列比对的 两条序列可以是两条d n a 序列，也可以是两条c d n a 序列或者m r n a 序列，因此， 6 第一章绪论 单纯序列比对的问题并没有边界的问题，但是在c d n a m r n a 序列与d n a 序列的比 对软件中，一般都解决了e x o n 与i n t r o n 之间的边界的问题。例如s i m 4 软件， 也有的并没有明确的给出边界信息，例如b l a t 软件，在这里，为了方便，我们 也将e x o n 与i n t r o n 之间的边界问题归于序列比对的解决问题之内。 c d n a 序列是e x o n 的连续序列，中间没有i n t r o n ，它是m r n a 序列反转录雨 来的，而d n a 序列，既有e x o n 也有i n t r o n 。其关系如图1 1 4 - 1 ”1 所示： 同g u r e 2 1 撕蛔咖p 吼删嘏嗣掣c 酬妇蕾弘懿惭r n a 1 n 毛r 嘲 矾删w h o u k 蕾汹蛳硼耐吣伽斌黻h i i 呻酝 鞠q i 】啊蝣鹤o f 妇咖- 图1 1 4 - lm l h n a 与d n a 关系图 一般情况，一条c d n a m r n a 序列与一条d n a 序列比对，不仅需要确定出d n a 序列上与其相似的序列片断还需要在d n a 序列上确定出e x o n 与i n t r o n 的边界- c d n a m r n a 序列是e x o n 的连续序列，在d n a 序列中，只有e x o n 编码蛋白质， 7 第一章绪论 i n t r o n 在e x o n 接合的过程中被去除掉，如图1 1 4 2 所示。因此m r n a c d n a 直 接反应了基因的功能。在c d n a m r n a 序列与d n a 序列的比对中，如果c d n a m r n a 序列能够完全在d n a 序列上找到相应的e x o r ，弗且准确的找到边界，则可以预 测两个基因具有相同的功能。因此，c d n a m r n a 序列与d n a 序列的比对对于预测 基因、发现基因、分析基因的功能提供了很好的支持。其比对算法和软件实现在 序列比对中具有很重要的位置。 i n t r o n 与e x o n 的边界类型有两种：g t a g 与c t a c ( g 丁一a g 是正链时的边界， 约占9 8 以上，反链时是c t a c ，其他的边界类型不予考虑) ，如图1 1 4 2 所 示： 一_ 下 f r = 一t = 图i i 4 2m t r o n 与e x o n 的边界类型 i n t r o n 与e x o n 边界的确定一般有两种方法，一种是利用规则寻找边界g t a g 或者c t a c 。一种是基于统计的方法。基于规则的方法简单，但是不灵活。基于 统计的方法就是事先找出许多的边界情况的模板样本，然后在确定边界时利用人 工智能的方法如 附l 方法去模板中匹配，找出最好的个模板来使用，从而给出 边界的位置。基于统计的方法比较灵活，模扳可以随时添加和修改。其找出的边 界位置比较合理，也比较准确。 1 1 5 课题的目的和意义 近些年来，生物信息学迅猛发展，其中一个最重要的标志就是生物数据库 中数据的增长，尤其是核酸碱基的增长，截至2 0 0 0 年2 月，核酸数据库中序列 数总数已近5 7 0 万，约含5 8 亿碱基，如图1 1 5 0 1 。对于这些数据的及时处理 和分析变得尤为重要。 c d n a m r n a 序列与d n a 序列的比对有其独特的优点，它可以在d n a 序列上预 测和发现未知的和已知基因具有相同功能的基因，可以分析未知功能的基因的功 8 第一章绪论 能，可以帮助我们进行基因注释，可以帮助我们分析可变剪切等，因此研究 c d n a m r n a 序列与d n a 序歹9 的比对算法和软件实现非常必要和迫切。 罔2 1 ( ；蛳b a n k 置器簟长。弓l 囟g 嘲“舢年2 月 蚺1 1 6 凝。 寰1 5 姐序爿蠢冀摩长情糖 午曾撇詹爿囊 草静 - 善救序列嚣 1 啦啪啪 6 0 6 il 释2幻毒s 26 5 l 舯 l l 鳃， 22 “啦9劓打，9 9 31 2 6 2 1 2 2 5 il b 6 6 1 4 l 1 9 5 4 j 2 帽b螂5 1 1 7 32 6 t 瑚t 6 2 9 聪 1螂42 1 1 i 4 9 5 4j 9 9 52 8t _ 9 2 “2 矗94 7 8 j ( j e 6 sq 嚣2 9e 6 2】锕6“，缁0 拍 5 6 昭 1 9 钾1 0 啦! 瑚 1 0 刺廿, l 9 9 7 7 8 1 5s 9 i1 3 8li 拿25 0 5 0 鼬1 9 1 弱d d ：l ，钟，1 9 孵1 甜23 棉蛾32 舢23 2 5 l ，即抽强竹l 2 24 wl 峰辨2 蜘，s 弹却r3 船5 i 窖 i 。4 0 ) 2 77 鼗 j 船硷s s 蚰口蛆5s 聃ll ，o j 9 9 l 拍i 曲2 7 ；5n 蛐 拄 号l 口d 年2 问擞审聍g 目县d t 蓐l m 篡诅啊鼍 图1 1 5 生物数据库中数据增长图 现有的可以用于c d n a m r n a 序列与d n a 序列进行比对的软件有e s t 2 9 e n o m e 、 s i m 4 、g e n e w i s e 等软件，它们都有着很好的应用和效果，但是，s i m 4 是一个同 物种的c d n a m r n a 序列与d n a 序列进行比对的软件，e s t 2 9 e n o m e 采用全局动态 规划算法，因此它不能对于整个基因缀进行比对，g e n e w i s e 也是采用动态规划 算法，边界的确定上它采用统计的方法，利用h m m 模型进行边界的寻找，精度比 较高，但是它的速度慢，也不能应用于整个基因组的比对。 随着生物信息学的发展，c d n a m r n a 序列以致很多条序列与整个基因组数量 级上的跨物种的比对问题日益变得重要。与整个的基因组进行比对可以更加准确 9 埔蕾 第一章绪论 的预测和发现功能相同的基因，由于基因复制的原因，还可以可能发现多个功能 相同的基因，多条c d n a m r n a 序列的提交可以更快的分析和处理数据，可以从更 高的一个高度来分析看待我们所要解决的问题。 因此，发展多条c d n a m r n a 序列与整个基因组数量级的跨物种比对算法和 软件很有意义，并且很必要。 本课题就是应这个需求而设立的，本课题的目的就是研究多条e d n a m r n a 序列与整个基因组的跨物种的比对算法，并且实现相应的软件x a t 。 1 2 国内外研究现状 序列比对可以帮助生物信息学家预测、发现新的基因，可以寻找同源序列 片断等。序列比对在生物信息学的研究中占有重要的地位，随着生物信息学的发 展，序列比对的算法和相应的软件实现也不断的发展和完善。序列比对在生物信 息学的研究中一直是一个研究重点和热点。如今，已经出现了许多的序列比对的 算法和软件，如f a s t a 、b l a s t 、s i m 4 、b l a t 、b l a s t z 、e s t 2 9 e n o m e 、g e n e w i s e 等。每个软件都有其优点和应用范围。在序列比对的软件中，软件采用的方法和 软件的实现融为了一体。 1 2 1f a s t a 软件算法 f a s t a “1 的算法描述来自于w i l l i a m r p e a r s o n 和d a v i dj l i p m a n 在1 9 8 8 年发表于b i o c h e m i s t r y 上的论文。f a s t a 软件进行局部比对，搜索相似的序列 片度，绘出局部比对的结果中分值最高的一个结果。它的输入要求是两个序列文 件名字，第一个是q u e r y 序列文件名字，第二个是s u b j e c t 序列文件名字，q u e r y 序列文件中包括一个序列，而s u b j e c t 序列文件中可以包含多个序列文件，f a s t a 软件对于s u b j e c t 序列文件中的序列腰序搜索，给出q u e r y 与s u b j e c t 序列文件 中每个序列比对的结果。它仅仅是一个局部序歹l j 比对软件，因此它的输入没有特 别的要求，不一定是c d n a m r n a 与d n a 序列，它将所有的序列看作d n a 序列，进 行相似片断序列的搜索。它的算法如下： a 找出进行比对的两条序列中所有长度为k - t u p 的连续的一致序列片断。 例如下面的两条序列： o 第一章绪论 l2 3 4 5 6 7 8 9 l a c g t c t t c a 2 a c c c g g c t g 令k - t u p = 2 ，那么在上面的两条序列中有两个满足条件的连续的一致序列片 断对。即序列( 1 ，1 ) 和( 5 ，7 ) ，括号中第一个坐标是序列1 中的位置起点，第二个 坐标是序列2 中的位置起点。这种序列片断的一致性可以表示为对角线圈，一对 致片断表示为一条对角线。如下图： ac g tcttca 这一步就是找出所有的对角线。对于图中的片断，如果片断间距小于用户 设定的界限，则将二者连起来作为一个片断。计算对角线的分值时不考虑核酸碱 基的替代，不考虑插入和删除。只考虑相同不相同。相同给一个分值，不同给 一个分值。选择1 0 条分值最高的片断进入下一步。这一步的结果见图1 2 i a 。 b 在这一步，对a 步骤中得到的1 0 条片断重新记分，此时允许保守点的 突变，利用替代矩阵来记分。在重新记分以后，在每条这样的片断中找出分值 最高的子片断，作为“初始区域”进入下一步。在初始区域中，最高的分值记为 i n i t l 。这一步的结果见图1 2 1 8 。 c 在这一步中，f a s t a 选出分值高于用户设定的界限的且相互之间不重叠 的初始区域，并尝试将这些初始区域链接起来。对于链接出现的空位进行相应的 罚分。最终找出分值最高的初始区域或者链接起来的数个初始区域。这一步计算 出来的最高分值记为i n i t n 。这一步的结果见图1 2 1 c 。 d 以i n i t l ( 或i n i t n 的片断) 为中心，向前后延伸一定的长度，在这样 的一个区域中( 见图1 2 1 d 中虚线间的区域) ，应用s m i t h w a t e r m a n 算法进行 第一章绪论 重新对齐，最终的得分为o p t ，这步的结果见图1 i d 。 f a s t a 算法简单快速有效，它能够很好的解决局部相似性搜索问题，但是它 没有采用跨物种的替代矩阵，不适宜用来进行跨物种的搜索。另外它不考虑b n a 序列上e x o n 与i n t r o n 的边界的问题，因此，不能用来进行c d n a m r n a 与d n a 序列的比对。 辅m b 靳1 除习柏 卜1 、_ ：； ”除沁卜 c 辅 ，二冈”l 土 图1 2 1 f a s t a 的4 步( a - - d ) 算法图示 1 2 2 b l a s t 软件算法 b l a s t 。1 ( b a s i cl o c a la l i g n m e n ts e a r c ht 0 0 1 ) 软件算法的描述来源于 s t e p h e nf a l t s c h u l 等的论文( b a s i cl o c a la l i g n m e n tt o o l 。b l a s t 软件是 如今应用最广泛的局部序列比对软件。它的速度快，并且提供了统计值来对得到 的比对结果进行统计上重要性的描述。下面介绍b l a s t 软件采用的一些方法和其 算法。 1 2 2 1m s p m s p ( m a x i m a ls e g m e n tp a i r ) 是在参加比对的两条序列中的分值最高的一 对具有相同长度的片断。m s p 的边界是这样的一些点，无论是增加长度或者是减 少长度，都不能使分值增加。使用的矩阵是相同分值为+ 5 ，不周分值为一4 。如 第一章绪论 下面两条序列中的画线部分： a ： a c g t a a c c g t b ：9 8t a y 趣塑c c 画线部分即为一个m s p ，分值为3 0 ，因为无论是增长或者缩短都不能使其 分值增大。 1 2 2 2 统计方法 给定参加比对的两条长度分别为m 和n 的随机序列，发现一个分值大于或者 等于s 的m s p 的概率p 的计算公式如下： p - 1 一e 一7 其中： y - a n n e 一， a ，k 为参数。 发现c 个分值都大于或者等于s 的分立的m s p 的概率p c 的计算公式如下： p c - 1 - e - y 萎鲁 1 2 2 3 序列压缩 核酸序列中只有4 种碱基，a 、c 、g 、t 。因j 墩在计算机中我们可以用1 个 字节来存贮4 个字符。每个字符占2 个比特位。这样在搜索的时候每次移动i 个字节即4 个字符。相比于不压缩的情况速度可以提高将近4 倍。因此大大加快 了搜索的速度。 1 2 2 4 重复序列 在实际的d n a 序列中，核酸碱基的出现概率( 即字符a c g t 出现的概率) 不 是真正随机的。比如可能具有a + t 富有的区域或者重复的序列片断。这对于实 际的编程来说是一个问题。当一个具有a + t 富有区域或者具有重复序列片度的 q u e r y 序列和d n a 序列比对时，可能会产生许多没有意义的重复结果序列。因此， 消除它们的影响很重要。 1 2 2 5 算法 a ) 对q u e r y 序列建立哈希表。 以d n a 序列比对来说，对于w o r d ：l1 的q u e r y 序列建立哈希表，表的长度 第一章绪论 为4 ”= 1 6 m 。搜索d n a 序列时，可以直接定位q u e r y 序列上的位置。 b ) 获取所有分值大于t 的m s p 。 c ) 扩展m s p ，保留分值大于s 的比对结果。 d ) 给出比对结果，同时给出比对结果的统计值。 b l a s t 软件算法引入了统计值，对于得到的结果给定在随机序列的情况下的 统计重要性的描述。为我们分析结果的统计重要性提供了定量的描述。b l a s t 软 件和f a s t a 软件一样，也是一个局部序列比对软件，它也没有考虑e x o n 与i n t r o n 的边界问题，不适宜c d n a m r n a 与d n a 序列的比对问题。 1 2 3 s i m 4 软件算法 s i m 4 软件算法来源于l i l i a n af l o r e a 等的论文ac o m p u t e rp r o g r a m f o r a 1 i g n i n gc d n as e q u e n c ew i t hag e n o m i ed n as e q u e n c e 。s i m 4 软件用来进行 e d n a 序列与d n a 序列之间的比对。它不仅仅给出d n a 序列中与c d n a 序列中的e x o r 相似的序列片断，还给出d n a 序列中i n t r o n 与e x o n 的边界信息。在同物种的序 列比对中，它是一个非常好的算法。其算法如下： a ) 确定h s p h s p ( h i g h - s c o r i n gs e g m e n tp a i r s ) 是给定两条比对序列中的高分 ( h i g h - s c o r i n g ) 比对序列片断，并且没有空位。类似于b l a s t 软件中m s p 。s i m 4 检测所有的w o r d 等于1 2 的匹配片断，然后将它们向两边扩展，扩展时的矩阵是 相同分值为l ，不同为一5 。当分值不能增加时即停止扩展。 b ) 选择能够代表一个基因的一组h s p 用动态规划算法选择一个最好的h s p 链。选择的h s p 应满足以下两个条件： 个是h s p 在c d n a 序列上的位置升序排列。二是连续的h s p 的对角线( 前面已 经说过，匹配的比对序列在图形显示为一条对角线) 应该相同或者差别满足给定 的域僮。h s p 的分值乘上1 0 0 ，并且减去由于对角线的不同即空位的引入所罚的 分值。 c ) 确定e x o n 边界 当e x o nc o r e ( e x o nc o r e 是一组h s p 的集合，它们几乎在一条对角线上) 之间有重叠时，需要在重叠区域寻找一个位置来去掉重叠，使两个e x o n c o r e 链接起来。这个位置一般根据g t a g 或者c t a c 原则在d n a 序列寻找e x o n 与i n t r o n 1 4 第一章绪论 的边界。当e x o nc o r e 相互不重叠时，它们相互向对方扩展，扩展时使用贪心算 法。边界依然遵循g t a g 、c t a c 原则，如果扩展不成功，例如分值太低，不重叠 的区域太长等，那么在二者之问的区域重新执行a ，b ，c 步。对于两头的e x o n c o r e ，分别向各自的序列末端扩展，依然使用贪心算法和g t a g 、c t a c 原则。如 果扩展不成功，在剩余的区域重新执行a ，b ，c 步。 d ) 给出比对结果。给出每个e x o n 的比对结果。 s i m 4 软件算法对于参加比对的两条序列不同的原因有两个假设：一个是序 列不同的原因是由于i n t r o n 的引入而不同；另一个是序列不同的原因是由于序 列的错误( 如测序错误) 而不同。由此可以看出，s i m 4 软件的最初设计目标是 面向于同物种的序列比对的，丽不是跨物种的序列比对。 s i m 4 在同物种的c d n a 序列与o n h 序列比对上效果很好。随着物种进化变异 的出现，其精确度随之下降。表1 2 3 “1 显示了当跨物种比对时的情况。选择的 是人的1 6 条m r n a 和同源的老鼠的基因组序列。第4 列显示了有多少m r n a 用s i m 4 比对上了，第5 列显示了在蛋白编码区有多少比对上了，第6 列显示了比到老鼠 的非m r n h 区域的核酸个数。 i r a b 4 p t l f lo f 蟑m 履帅 村a n h i 奠h 嘲蛳n h 幽 w l u l 协o r t h o l o a o mm o u s e 韵n 啊n hs q u - 埔 g e n e23 56 i s o r9 1 99 8 62 0 ( 2 0 )1 1 0 0 0 0 0 ( 0 3 1 1 5 ) 揪叠! 盼- 29 1 79 9 11 2 ( 1 3 ) 8 3 o1 0 0 1 2 3 ( 2 8 2 2 7 舢 h s a p9 1 31 0 0 1 0 ( 。) 1 0 01 0 0 0 8 9 ( 1 1 1 1 2 4 0 ) g n 8 38 9 8驰21 1a o )7 5 o1 0 1 0 z n 9 2 2 l - 2585c 7 )鲥09 8 5 1 7 8 ( z 7 1 1 5 1 5 】 h 铲7 p ，c 68 9 29 6 11 5 ( 1 4 ) 8 0 。19 6 8 1 8 7 ( 3 8 2 0 3 3 ) h t m d r 翻8 8 99 5 11 0n o )魄49 9 20 12 ( 5 4 3 4 1 c 7 08 8 79 7 6 3 ( 3 ) 7 8 21 0 0 0 0 0 ( 0 1 5 1 鳓 刑8 8 79 6 0 7 ( 7 ) 5 2 91 0 0 o 0 0 ( 0 1 1 8 4 3 l c 3 f8 8 69 3 21 2 ( 1 2 j1 1 0 0 0 3 2 ( 6 1 8 5 6 ) c 9盯49 2 o 2 2 ) 9 t l ，51 0 00 1 1a ，8 7 7 8拍49 0 91 404 )7 4 29 3 31 1 71 2 5 2 1 2 9 c 2 f8 5 09 2 26f 6 7 2 81 0 0 0 2 3 ( 2 8 8 国 8 78 1 68 6 ，6 7 ( 5 ) 6 4 2h 4 0 3 3 ( 4 1 2 ) c 88 1 57 5 961 6 )7 1 o4 0 4 8 6 ，1 2 4 7 l c d 47 0 26 2 91 0f 7 )2 1 o4 7 3 o 5 9 1 8 3 0 5 1 ) g 口r p k 函呻l l l o d h t l w l a l ：m o s t c o l t m n m - o t l k a f l 竹o m 珊恤i t o a t m a 岫 l 葛h j 髓1 1 9 9 7 1 驰m n 哇 蝈r 喇n 曲由r , u d a o t i d o l d m 哪t h 扭岫棚e o l l n m n 嘣d 巾l 如幻时叼相睫( 1 阳m 明t d 佳d 删h a l a t y “豳黼帅h 舢硎用悯m q u n m h t i m 翻埔舢幽埘憎蛳( 2 1 唧“岬 啊a m i n o 撕d 嘶f r j l a a t , t o a t a h b 嘣竹1 r o l l 2 嘴铀k 蚋幻m h 埘蕾1 9 9 8 ) c 3 l n u m b a fo r 惜 h 廿褂口m | i d h 阳憎咐鼬畦删孵- 皿醇o o t a t o 瞄o 1 d 钾嘲l 釉m 呻t 蚺d t h o q n t i r o m l i n a 酬州埘- 抽啊- 1 5 l 阳明协9 - d 舳p r 晌由咖佃簪啪州脚i i k i i t 4 ( 6 l 知f 铀f 衄驴a r m ，c i 怕h 曲 晡g r 州b y t 嘲协p 0 蜘惜n o t h t h o 嘶嗍删i 蹦嗍钾瑚咖讲，p 妇j l “抽嘲 表1 2 3s i