基于距离的进化树系统的并行算法研究

• 作 者: 万康
• 出 处: 黑龙江大学
• 发表日期: 2004年期
• 关键词: 进化树 序列比对 距离矩阵 并行算法 甲型流感

随着生物测序技术的飞速进步,越来越多的生物数据需要处理。而传统的串行算法在处理生物数据时,运行效率低,耗费时间长。为了让处理生物数据的速度得到有效提升,本文针对构建进化树各个部分的串行算法进行分析。在此基础上,以生物序列数据作为研究对象,挖掘串行算法在并行化改进方面的潜力,提出了相应的并行算法。使得处理生物数据的算法性能得到大幅度提升,为后续的生物研究奠定坚实的基础。首先,多序列比对阶段包含多序列两两比对、构建向导树和多序列依次累进比对三个部分。本文利用两两比对每次比对结果互不依赖的特性,分析不同的并行策略,将每一次的两序列比对视为并行粒子,对串行算法作出了利于并行化的改进,提出并实现了基于矩阵降维的并行算法。随后通过实验比较了串、并行算法的性能。其次,在计算距离矩阵这部分,针对矩阵上三角元素的计算无关性,本文实现了基于OpenMP的并行算法,为了充分利用计算机的处理器资源,本文还提出了基于OpenMP+GPU的混合并行的算法,将串行算法拆分,不同部分分配给合适的处理器计算,让设备端和主机段同时并行处理不同的部分,使程序性能得到进一步的提高。最后,本文采用甲型流感病毒的生物序列作为实验数据。实验数据包括甲型流感病毒116个亚型的基因组序列,分别使用串行算法和本文的并行算法构建出它们的进化树,实验结果表明,并行构建耗时远低于串行构建。得到它们的进化树之后,本文最后对这些序列的进化关系进行了分析。