论文部分内容阅读
基因是承载着生命体特定遗传信息的核苷酸序列,当其产生突变或变异后就会导致各种癌症或遗传病的发生,因此治疗各种遗传病和癌症的实质就是破解基因的秘密。基因研究中最基础也是最重要的一步是将测定的DNA序列比对到参考基因组上,只有获得了测定序列在参考基因组上的真实位置,才能研究其变异所带来的遗传性状的改变,进而对该变异所带来的不利影响进行有针对性的治疗。但是,随着各种高通量测序技术的不断涌现,与日俱增的海量数据对当前主流比对算法无论是硬件上都是软件上都提出了极大的挑战。因此,研究并实现处理速度更快、准确率更高的基因序列比对算法显得尤为重要。本文首先研究了两种基于BWT索引的序列比对算法原理及实现,并分析了其各自的优劣势,然后研究并实现了一种新的基于Hash索引的Subread算法。本文的创新主要有两点:其一是针对Subread算法在重复序列情况下返回比对位置不完整的问题做了进一步改进及实现,提高了比对准确率;其二是利用并行化框架Hadoop实现了改进型Subread算法的并行化处理,有效提高了比对速度。本文的研究工作和主要内容如下:(1)研究并实现了参考基因组二进制压缩方案,成功将参考基因组的占用空间降低为原来的四分之一大小,而且压缩后的参考基因组保留了原参考基因组的全部信息,能够进行无损还原。(2)研究了目前两种基于BWT索引的序列比对算法原理,并分别对其进行了实现,最后从灵敏度、准确性、内存占用和时间消耗四个方面对两种算法的性能进行了测试,并分析了其各自的优劣势。(3)重点研究并实现了基于种子投票策略的Subread序列比对算法,并将其与两种基于BWT索引的序列比对算法进行了性能测试及对比分析;最后针对Subread算法在重复序列情况下返回比对位置不完整的问题做了进一步的改进及实现,并对改进前与改进后的Subread算法进行了性能测试及对比分析,重点分析了改进前与改进后算法的准确性。(4)研究了改进型Subread序列比对算法的集群并行化方案,并在Hadoop平台下对其进行了实现,最后对并行前和并行后的改进型Subread算法进行了性能测试及分析,重点分析了并行化前与并行化后的时间消耗等。