论文部分内容阅读
随着后基因组时代的到来以及一些新的高通量信息提取技术的开发,DNA和蛋白质序列数据库中的信息量以爆炸式增长。生命科学研究已经进入了深深依赖计算机和网络的时代。在所有的计算机工具中,多序列对齐占据核心地位。因为其它的许多生信息学工具都是以多序列对齐为基础的。由于序列对齐是一个NP完全问题,所有企图快速产生最优化对齐的想法是不可能实现的。所以,那些取得对齐质量与对齐时间最佳平衡的程序就是好的多序列对齐程序。分治对齐方法(DCA)就是这样一个比较好的程序。 由于序列对齐的计算复杂性相对于序列长度成指数形式增长,所以将长序列集分割成短序列子集的DCA思路可能产生快速的多序列对齐。首先,DCA将原序列集在中点附近切断,得到两个含较短序列的序列子集。重复这个处理过程直至得到充分短的序列集而能轻易的被对齐;接着,最优化对齐这些短序列子集;最后,通过连接对齐矩阵,得到全序列的对齐。DCA的关键问题就是如何计算这些分割点。实际上,DCA程序以一种贪婪方法计算分割点,而不能使DCA程序没有预期的快。 在本文中,我们提出了一种新的多序列对齐算法LSS-DCA。LSS-DCA结合了DCA方法和渐近方法的优点,达到了计算速度和对齐质量的较好平衡。LSS-DCA采用了一种简化的但十分严格的渐近方法来计算序列中显而易见的最长相似片段(LSS)。并在LSS两端切断序列集,LSS两边的短序列集重复进行相同的处理过程,直到所有的LSS被找出并被对齐。最后,以原序列集中相对应的序列片段或空格填充LSS之间的空隙,得到全序列集的对齐。 这种严格的渐近算法十分可能导致不能发现序列集中的相似片段,这将导致DCA过程不能进行下去。为尽量避免这种失败,一种纵向的分治(相对前面的沿序列的横向分治)被用来对原序列集进行聚类,将序列集分成多个关系更紧密的子集。这种聚类过程也是重复进行的,直至所有的序列被归入相应的类而适合横向DCA处理。两种DCA是交叉进行,但横向DCA具有更高的优先级。只有在横向DCA无进行下去时(找不到LSS),才进行纵向DCA并对得到的所有类进行横向DCA。一种极端情况就是所有的序列都是低相关性而每一条序列被归到不同的类中。在这种情况下,LSS-DCA的策略就不起作用,只采用ClustalW对齐序列。 我们用Visua1C+十开发了基于LSS一DCA思想的计算机程序,并测试了LSS一DCA程序的计算时间和内存要求。用几个序列数据对LSS一DCA程序进行验证,对齐结果与其它的6个对齐程序进行比较。结果表明,LSS一DCA快速产生质量较好的对齐,但对含有两个以_E相似的相似片段的序列集的对齐不理想。此外,LSS一DCA对内存的要求也较高。