面向基因组的高效FM-index构造算法

作     者：王哲 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：霍红卫;张小宁

授予年度：2015年

学科分类：0831[工学-生物医学工程（可授工学、理学、医学学位）] 0711[理学-系统科学] 07[理学] 08[工学] 

主      题：FM索引 BWT变换 后向搜索 小波树 rank 

摘      要：随着第一条人类DNA被解码成2.8GB的字符串,许多生物学的研究都集中在对DNA序列的分析上。本文选取DNA序列的索引进行研究,旨在解决目前DNA序列的FM-index不能够在普通电脑(4-8G内存)上高效构造的问题。本文提出的增量式构造FM-index的算法框架为继续研究高效构造FM-index提供了理论基础。现实意义上,该算法扩展了FM-index的应用范围,节约了购买超级计算机的成本。FM-index是压缩全文本自索引的一种。通常FM-index的算法框架分为以下步骤:首先,将文本T经过BWT变换(Burrow-Wheeler Transform)得到的文本L;然后,采用小波树(Wavelet-tree)对文本L进行编码存储;接着为小波树的内部节点提供高效的rank查询结构;最后采样后缀数组(SA)和名次数组(SA-1)。FM-index在这些基础数据结构的支持下实现高效的count,locate和extract操作。它最初最多使用5nHk(T)+o(n)位的空间存储,其中Hk(T)表示T的k阶经验熵,n表示文本的长度。FM-index可在普通电脑内存中存储,然而构造过程中过高的峰值内存或者过长的构造的时间均限制了FM-index的应用。通过大量阅读和分析之前的研究成果,深入理解BWT变换的过程,理解SA、SA-1和LF映射的关系以及rank查询结构的特点,经过大量实验测试与分析,最终得到了本文的算法。本文主要分3个部分进行了研究:首先,为了解决DNA数据的BWT变换无法在普通电脑上完成的问题,本文提出了LF-BWT算法。该算法理论上在线性时间内利用线性空间完成了DNA数据的BWT变换,实验表明,LF-BWT算法仅需不到原文本1倍的空间就可以快速完成DNA数据的BWT变换,并且可以调整参数来获得时间和空间的权衡,进一步扩展了LF-BWT算法的使用范围。该算法在与最新的主流算法的比较中也表现出了优势。第二,为了解决LF-BWT算法在构造过程没有获得SA和SA-1采样的问题,本文提出了由BWT变换生成的文本通过LF映射在线性时间内获得SA和SA-1采样的算法。该算法并不完整存储SA,而是每次LF映射过程中遇到采样点就进行采样,这极大的减小了内存空间的占用。第三,为了更进一步提高FM-index的压缩率和查询效率,本文提出了RRR算法的一个改进版本CF算法,它充分结合了CPU字长以及数据的局部性原理,提高了cache命中率。该算法在保持了与RRR算法的空间和查询时间理论复杂性一致的情况下,提供了更加高效的实际性能。实验表明,不管是随机数据还是真实DNA数据,CF算法均表现出了很大的优势。