LSS-DCA：一个快速的分治多序列对齐算法

摘要

在该文中,提出了一种新的多序列对齐算法LSS-DCA.LSS-DCA结合了DCA方法和渐近方法的优点,达到了计算速度和对齐质量的较好平衡.LSS-DCA采用了一种简化的但十分严格的渐近方法来计算序列中显而易见的最长相似片段(LSS).并在LSS两端切断序列集,LSS两边的短序列集重复进行相同的处理过程,直到所有的LSS被找出并被对齐.最后,以原序列集中相对应的序列片段或空格填充LSS之间的空隙,得到全序列集的对齐.该文用Visual C++开发了基于LSS-DCA思想的计算机程序,并测试了LSS-DCA程序的计算时间和内存要求.用几个序列数据对LSS-DCA程序进行验证,对齐结果与其它的6个对齐程序进行比较.结果表明,LSS-DCA快速产生质量较好的对齐,但对含有两个以上相似的相似片段的序列集的对齐不理想.此外,LSS-DCA对内存的要求也较高.

目录

致谢

缩略词

第一章多序列对齐在生物学研究中的意义

1.1什么是多序列对齐

1.2多序列对齐是生物学研究必需的一种计算机工具

1.3多序列对齐在后基因组时代中的核心作用

1.3.1功能确认(Functional assignments)

1.3.3保守模式分化(Differential conservation patterns)

1.3.4进化研究(Evolutionary studies)

1.3.5结构域布局(Domain organization)

1.3.6同源结构建模(Homology structure modeling)

1.3.7信息繁殖(Information propagation)

第二章多序列对齐的一些基本概念

2.1两序列对齐(Pairwire(Sequence)Alignment)

2.2多序列对齐(Multiple(Sequence)Alignment)

2.3对齐积分(Alignment Scores)

2.3.1替代点阵(Substitution matrix)

2.3.2两序列对齐积分(Pairwise Alignment Score)

2.3.3多序列对齐积分(Multiple Alignment Score)

2.4最优对齐(Alignment Optimalizing)

2.5序列权重(Sequence Weithting)

2.6动态规划(Dynamic programming)

2.6.1两序列的最优对齐

2.7 Needleman-Wunsch(N-W)算法和Smith-Waterma(S-W)算法

2.7.1 N-W算法

2.7.2 S-W算法

第三章多序列对齐的研究进展

3.1渐进算法(progressive algorithms)

3.2精确算法(Exact algorithms)

3.3迭代算法(Iterative algorithms)

3.3.1随机迭代算法(Stochastic iterative algorithm)

3.3.1非随机迭代算法(Non-stochastic iterative algorithm)

3.4基于一致性的算法(Consistency-based algorithm)

第四章LSS-DCA算法及其计算机实现

4.1 DCA算法

4.2 LSS-DCA总体算法

4.2.1 LSS计算

4.2.2序列归类

4.3 LSS-DCA的计算机实现

第五章结果与讨论

5.1 LSS-DCA的计算时间和内存占用

5.2 LSS-DCA与其它对齐程序的结果比较

5.3结论

参考文献

附录攻读硕士学位期间发表的学述论文