基于快速沃尔什变换的生物序列相似性比对

摘要

生物信息学是一门交叉学科,它包含了生物信息的处理、存储、分发、分析和解释在内的所有方面,它综合运用数学、计算机科学和生物学的各种工具,来阐明和理解大量数据所包含的生物意义.本论文大致可以分为两大部分:生物序列相似性比对和序列拼接.生物序列的相似性比对是生物信息处理中最重要的数据处理任务之一,而序列拼接是全基因组测序中的一个极其重要的环节.论文首先简单介绍了生物序列相似性比对及其算法,特别的讨论了最早提出的,也是最基本的生物序列相似性比对算法——动态规划算法,它是1970年由Needleman和Wunsch提出的.在这些算法的启发下,本文提出了基于快速沃尔什变换的分子子序列识别方法.这种方法不仅极大地降低了CPU时间而且其准确度可以达到100％.由于分子子序列识别应用的局限性,在此基础上论文进而提出了基于快速沃尔什变换的两两相似性比对方法.这种方法可以对任意两条序列进行相似性比对.由计算模拟可知,此方法耗费的时间与序列长度成近似线性关系,并且其空间复杂度也明显降低.接着,论文简单综述了序列拼接及其算法,并对Phrap和Euler两种典型算法进行了分析和比较.通过分析序列拼接中存在的问题可知重复序列对序列拼接的准确度有极大的影响.针对这种情况,论文利用前述的分子子序列识别方法提出了一种新的重复序列屏蔽方法.它能快速给出重复序列的位置信息,并加以识别.所以,根据计算模拟分析和实现表明此方法的时间复杂度得到了极大的降低,其精确度可达100％.

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

1绪论

1.1生物信息学简介

1.2生物信息学的研究现状及任务

1.3论文研究的主要内容

1.4论文研究的主要创新点

1.5论文的结构

2生物序列相似性比对

2.1 DNA序列相似性比对简介

2.2两两序列比对

2.3多序列比对

2.4序列比对算法简介

3基于快速沃尔什变换的分子子序列识别

3.1快速沃尔什变换的简介

3.2基于快速沃尔什变换的DNA分子子序列识别

4基于快速沃尔什变换的两两序列相似性比对

4.1基于快速沃尔什变换的两两序列相似性比对

4.2算法模拟与实现

4.3小结

5基因组DNA序列拼接

5.1大规模全基因组测序技术简介

5.2片断拼接问题及现有技术

5.3两种片断拼接算法

6DNA序列拼接中重复序列屏蔽的一种新方法

6.1含相同重复子序列片段间的关系分析

6.2DNA序列拼接中重复子序列屏蔽方法

6.3结语

结束语

致 谢

参考文献

附录：攻读硕士学位期间发表论文目录