基于后缀树与后缀数组混合结构的基因序列比对算法研究

作     者：焦雅 

作者单位：内蒙古农业大学 

学位级别：硕士

导师姓名：高静

授予年度：2015年

学科分类：0831[工学-生物医学工程（可授工学、理学、医学学位）] 0711[理学-系统科学] 07[理学] 08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：序列比对 后缀树 后缀数组 BWT 空位种子 FM-index算法 

摘      要：随着基因测序技术的迅猛发展,基因数据库中序列公共数据量呈指数形式增长。对于基因数据最基础但最重要的分析方法为序列比对。本文通过对现今常用的分析算法和分析软件在序列的类型、特点和功能等方面研究和比较,发现序列比对算法的重点是对基因数据结构进行有效组织。目前这些数据结构有哈希表和后缀树、后缀数组,本文在此研究基础上提出了新的算法BWL。BWL算法的特点：(1)采用了新的数据结构,即后缀树与后缀数组混合的新的数据结构,这种数据结构不仅占用内存空间比较小,解决了基因数据文件因内存受限的问题,而且能减少与外存频繁交互,提高比对运算速度。(2)BWL算法在序列比对过程中引进空位种子模型,提高算法敏感度。对于没有完全匹配的序列,采用加入空位的方法,相对于精确的动态规划法或对模型逐位循环进行增、删、改再比对的试探方法在运算速度方面有了进一步提升,算法有效性明显提高。最后本文做了序列比对仿真实验,并对实验结果进行了详细的分析分析结果表明,本文提出的后缀树与后缀数组混合的数据结构占用内存不会随着基因数据的大小而改变,索引构建速度也较其他算法更快。另外,序列比对上提出的引入空位种子模型的方法在实验比较中得出本文提出的改进具有有效性并且实际性能的提升很显著。