增强型稀疏后缀数组索引的高错误率reads比对

韦 好，钟 诚

(广西大学计算机与电子信息学院广西高校并行分布式计算技术重点实验室，南宁530004)

E-mail:394178293@qq.com

1 引言

将高通量DNA测序仪产生的read序列映射(比对)到参考基因组是生物信息学中十分重要的研究问题之一.映射(Mapping)过程是高通量测序技术(HTS)数据处理中的第一步也是最耗时的步骤，它采用索引串匹配的方法将read序列与参考基因组进行比对，确定每一条read在参考基因组上的位置，这一过程在基因组分析流程中起着关键作用.序列比对算法大致分为两大类:基于哈希表索引的算法和基于前缀/后缀树(数组)索引的算法［1］.第一类算法通常为参考基因组建立一个哈希索引表，根据“种子(seed)-扩展”策略，将比read短得多的子序列(称为种子)直接定位到参考基因组，然后根据每个映射位置上的种子扩展的结果来确定read的位置.这类算法虽能有效检测识别出单核苷酸多态性(single nucleotide polymorphism，SNP)或结构变异，但其最大的缺陷是内存空间占用很大.基于哈希表索引的代表性的比对算法有BFAST［2］、SOAP［3］、MAQ［4］、YAHA［5］和 FSVA［6］.第二类算法通常搜索参考基因组的前缀/后缀树(数组)，然后利用BWT(Burrows-Wheeler Transform)［7］方法计算每条 read 在参考基因组中的位置.这类比对算法可以节省大量存储空间和有效地减少参考序列与read序列之间的非精确匹配，但其比对速度较慢.基于前缀/后缀树(数组)的代表性比对算法有BWA［8］、Bowtie2［9］、SOAP2［10］和 HPG［11］.

在单分子测序仪的最新进展中，研究人员获得了比Sanger测序仪提供的长度更长的reads.自2010年，Pacific Biosciences发布的第一个实时单分子测序仪PacBio RS以来，单分……