论文部分内容阅读
随着新一代测序技术的快速发展,DNA测序数据爆炸式积累的速度远远大于其被处理的速度。DNA序列比对是生物信息学的一项重要的、关键的、基础的研究内容,是基因拼接组装的第一步,它是一个把测序仪测出的reads比对到参考基因组上的过程。目前的序列比对软件,根据建立索引方法的不同主要分为两类:基于hash的和基于BWT的,基于hash的序列比对软件有SOAP、MAQ等,基于BWT的序列比对软件主要有BWA、Bowtie、SOAP2等。在比对速度和比对精度上,测序数据的快速积累为当今的序列比对工具提出了巨大挑战。本文研究的是基于BWT的短序列比对,目前基于BWT的序列比对软件存在的一个问题就是高速缓存命中率过低,针对此问题,本文提出了一个对reads先排序后比对的算法。本文算法对待比对的reads进行从右到左按字典顺序排序,这样有相同后缀的reads经过排序会集中在一起,根据BWT查找子序列方法的特点,上一条read比对的中间结果可以为下一条read的比对所用,这样可以减少高速缓存命中率低的访问次数,据我们统计,对于大量的36bp长的reads,相同后缀的长度可达到18bp,这样就相当于平均每条read可减少18次的计算,从而提高比对速度。除了精确比对,我们还做了能够允许2错误的模糊比对,我们采用的是一个新颖的方法,对不能被精确比对的reads进行错误处理,产生新的reads,然后排序进行比对。在这个过程中我们构建了一个索引结构用来对错误处理过的reads进行筛选,大大减少了待比对的reads数量,节省了比对时间。为了验证基于排序的短reads比对算法是否能提高比对效率,本文用模拟数据和真实数据对系统进行了实验,实验结果表明,本文介绍的基于reads排序的算法是可行的,利用排序的reads的确比未排序的reads比对速度快。另外本系统还和目前其他比较流行的序列比对软件进行了比较,发现本软件在大规模序列比对时具有明显的优势,在比对过程中能够获得较高的比对速度和精度,特别是在精确匹配中表现出了良好性能。