论文部分内容阅读
随着新一代高通量测序技术的出现,DNA测序技术已成为研究生命科学领域的重要手段,而新一代测序技术产生的读取数据长度较短,并且数据通量非常巨大,这给生物信息学带来了新的机遇和挑战。其中对于这些数据的分析算法的研究面临着巨大的挑战,特别是序列比对算法和数据存储算法。目前,随着新一代测序技术的不断普及,基因组重测序的序列比对程序(如MAQ、mrFast、SOAP等)越来越多,而且它们采用的结构也不断完善,性能上越来越好。这其中包括哈希表,后缀数组,后缀树等结构,而最近几年出现了使用压缩模型Burrows-Wheeler变换。由于其空间占有量非常小,而且在查找匹配方面能够实现块搜索,从而大大提高了拼接算法的时间和空间利用率。这使得全基因组序列比对软件在个人计算机上运行成为了可能,并给非专业研究人员带来了研究生物学众多问题的机遇。本文面向新一代测序数据,在人类全基因组上利用BWT变换,在保证整个reads映射过程的拼接速度不变的情况下,提出了BWT索引压缩方法,构建了一个新的BWT索引结构。利用该结构构建一个reads映射系统,该系统实现了reads数据快速映射到人类参考基因组序列上。其中通过构建检查点结构信息来快速查找映射对应关系,通过构建位置信息来快速返回读取数据的拼接位点。由于BWT后缀序列在BWT索引中占据大量空间,而对于BWT后缀序列的压缩存储直接影响了整个reads映射过程的拼接速度。考虑到BWT后缀序列结构中碱基分布不均匀,碱基序列重复度比较高,为了提高整个reads映射过程的内存利用率,设计并实现了几种后缀序列压缩算法。利用这些压缩算法,特别是BWT再变换,使得碱基序列集中在一起,从而提高了整个索引结构的压缩比率。最后,通过采用reads的模拟数据和真实数据,对于这些索引压缩算法进行测试分析。结果发现整个映射过程的拼接速度基本没有改变,而索引结构空间大大减小到850MB左右。虽然压缩算法的压缩比率不是很高,但是对于索引结构的压缩还是非常有必要的。