新一代则序技术中的短序列比对和组装算法

论文摘要

新一代测序技术产生的序列片段普遍在35bp~75bp且数据量巨大,原来的序列比对和组装软件不适合这么短的序列,这就给序列比对和序列组装提出了新的挑战。本文主要探讨了新一代测序技术中的短序列比对和短序列组装算法。主要工作如下:(1)深入分析了基于哈希表的短序列比对算法ELAND、MAQ、SOAP以及基于BWT的短序列比对算法BOWTIE、BWA、SOAP2,对它们的原理及具体实现步骤进行了详细的解释,最后从模拟数据和实验数据两个方面对它们的性能进行了比较,从实验结果看基于BWT的算法在时间上与空间上一般优于基于哈希表的算法,MAQ算法虽然运行时间比基于BWT的时间要长,但是其内存使用率较低,SOAP算法是所有算法中对内存要求最高的算法。(2)对短序列组装算法进行了分类归纳,对SSAKE、VCAKE、VELVET短序列组装算法的原理和实现也做了深入的分析,并使用乳酸菌基因组对它们的性能进行了比较。从实验结果看,VELVET算法的拼接性能最好,其次是VCAKE,而SSAKE运行的时间较长。(3)然后提出一种新的基于分块索引的比对算法,算法也是基于BWT,它采用对BWT分块索引压缩的方式,并在内存中建立缓冲区,按照最久不用的原则将最久不用的块调出,以减少内存的占用。从实验结果看,当算法的缓冲区越大的时候,执行速度越快,优与MAQ算法,当缓冲区越小的时候,执行时间较长,但内存使用明显低于BOWTIE等算法。(4)最后对SOAP比对算法提出了一些改进,将短序列分为A,B,C三段,使内存使用率降低,加快了比对速度。并通过实验与SOAP算法做了比较,其内存使用率和运行速度均优于SOAP算法。

论文目录

• 摘要
• ABSTRACT
• 1. 引言
• 1.1 研究的目的和意义
• 1.2 研究现状
• 1.3 论文的结构安排
• 2. 短序列比对算法
• 2.1 基于哈希表的短序列比对算法
• 2.1.1 Eland算法
• 2.1.2 MAQ算法
• 2.1.3 soap算法
• 2.2 基于BWT的比对算法
• 2.2.1 BWT转换压缩原理
• 2.2.2 Bowtie算法
• 2.2.3 bwa算法
• 2.2.4 SOAP2算法
• 2.3 比对算法性能分析与比较
• 3. 短序列组装
• 3.1 基于Overlap/Layout/Consensus的组装算法
• 3.2 基于图的贪婪组装算法
• 3.3 基于de Bruijn Graph算法
• 3.3.1 de bruijn图结构
• 3.3.2 Velvet算法
• 3.4 组装算法性能分析与比较
• 4. 算法改进
• 4.1 基于块索引的短序列比对算法
• 4.1.1 算法描述
• 4.1.2 算法性能分析
• 4.2 SOAP算法改进
• 5 结论与讨论
• 参考文献
• 附录 攻读学位期间发表的论文