DNA序列拼接算法分析及并行化探讨

摘要：

基于欧拉路径的拼接算法开辟了一条解决DNA序列拼接问题的新的途径,打破了遵循”重叠-排列-生成共有序列”方法的传统。本文举例说明了基于EULER路径的拼接算法和基于Hamilton路径的拼接算法是怎样解决repeat问题的。在CJ、NM、LL基因组序列拼工程中,比较了EULER算法与Phrap、CAPS、TIGR算法的拼接结果,分析了它们各自的优缺点。由于EULER路径算法要求构造一个复杂的deBruijin图,因此用该算法拼接大规模全基因组存在存储瓶颈问题,该文对基于EULER路径的拼接算法进行了并行化探讨。

关键词： 生物信息学 序列拼接 并行拼接 拼接算法

作者: 蔡毅 骆志刚

作者单位: 国防科技大学计算机学院 长沙 410073

会议类型: 国内会议

会议名称: 2007年北京地区高校研究生学术交流会

会议地点: 北京

会议语种:中文

页码: 81-86

在线出版日期: 2008-01-01（万方平台首次上网日期，不代表论文的发表时间）