高度相似基因组序列数据集的压缩算法研究

摘要

随着高通量测序技术的发展,测序需要的成本急速下降,得到的基因组数据呈爆炸式增长,因此有效地存储和搜索这些基因组数据成为了急需解决的问题.压缩技术可以减少数据的存储空间,所以优秀的压缩索引算法成为了解决这一问题的关键技术.研究发现基因序列与普通文本数据的结构不同,序列中包含较多的冗余信息,而且同一物种或者按照生物分类法则划分的较相近的物种间的序列相似度很高,通用的文本压缩算法无法有效地压缩及搜索基因组序列集.所以,需要研究针对高度相似基因组序列数据集的压缩索引算法. 本文提出一种新的基于参考序列的压缩索引算法FMQ,能够高效地存储和搜索基因组序列集.主要思路是将序列集划分为参考序列和非参考序列,然后计算非参考序列与参考序列之间的差异信息,再设计压缩索引结构存储这些差异信息,并提出了在压缩索引结构上的搜索算法(包括子串提取和模式定位算法).具体工作如下: 压缩索引构建.首先,随机选取一条序列作为参考序列,顺序比较参考序列与非参考序列,得到不匹配的子序列,利用最长公共子序列算法获得参考序列与每个子序列之间的公共部分,根据公共部分逆推得到序列间的差异信息.然后,根据差异信息不同部分的特点,分别对差异位置,差异类型和差异碱基信息设计各自的压缩索引结构.这些差异信息的压缩索引结构所占空间为o(n)比特,其中n为参考序列的长度. 在压缩索引结构上的查询.本文在所建立的压缩索引结构上,提出了子串提取算法和模式定位算法.子串提取算法能够在O(n/log n+len+log2n/loglog n)时间内提取长为len的子串.模式定位算法将模式划分为等长的子模式集,利用建立的压缩索引结构搜索这些子模式在基因组序列集中出现的所有位置,并通过哈希表筛选出原始模式出现的所有位置.模式定位算法的时间复杂度为O(m*occ*n/log n),其中m为序列个数,occ是所有子模式在参考序列上出现的次数之和. 实验结果.在Pizza＆Chili Corpus标准数据集上测试了所提方法FMQ的索引构建时间,压缩率及查询性能.实验结果表明,相比于主流的几种相关压缩索引方法,FMQ在索引构建时间和压缩率上具有显著优势,索引构建时间最短,并且索引大小仅占其余方法的10%-60%.在查询性能方面,FMQ的模式定位算法性能较好,同时子串提取算法与所测试的几种方法相比性能接近.

目录

第一个书签之前