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

摘要

新一代测序技术产生的序列片段普遍在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算法。

目录

文摘

英文文摘

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 结论与讨论

参考文献

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