论文部分内容阅读
生物信息学(Bioinformatics),指的是利用信息技术和计算机科学等方法,以研究大量而复杂的生物数据的一门交叉学科。目前,基因组学中的DNA排序问题的研究是生物信息学的重要研究领域之一。研究DNA序列的基本途径是序列比对,它通过序列的排列规律寻找序列间的相似性和同源性,从而分析研究生物的遗传进化信息。近年来,随着生物学的发展,基因序列数据量成倍增加,传统的串行序列比对算法无法满足日益扩大的数据规模的需要。本文基于序列比对算法的特征研究其并行算法,提出一种序列编码算法和数据“首条序列划分”法,以有效提高算法的并行效率,为解决大规模生物序列比对问题奠定基础。本文主要的创新性工作包括:(一)提出一种新的DNA序列编码算法,实现基于MPI的并行FED算法。本文分析比较了DNA序列中精确比对(Exact Sequence Alignment)类型的算法,发现随着数据量的增长,算法计算时间会显著增加。为了解决这一问题,首先,我们提出了一种基于位运算的序列编码方式,以此降低数据存储空间,加快序列编码速度,从而提高算法效率;然后,采用并行算法对FED算法进行改进,并通过消息传递模型(MPI)在集群环境下实现算法的并行化,实验表明,该并行算法在20核环境下运行时,加速比达到16.1。(二)提出最适合CVoting算法的“首条序列划分”法,并基于MPI实现算法的并行。本文研究了模体发现问题(Motif Finding Problem)中计算挑战实例的算法,CVoting是目前具有代表性的能解决大型挑战实例的算法,但是它计算(21,8)挑战实例的时间依然需要超过20小时。因此,本文基于MPI的特点,设计三种数据划分方法,分析和比较三种方法对算法的适应性,提出“首条序列划分”方法是适合CVoting算法并行的最佳方式。该方式不仅实现算法的并行,将(21,8)挑战实例的运算时间降低到20分钟以内,而且算法从1个计算核开始一直到128个计算核始终保持加速比的线性增长,其中,在128核时加速比达到96.2。