一种基于蚁群算法的生物序列并行比对方法

A parallel alignment method for biological sequences based on ant colony algorithm

生物序列比对是生物信息领域的重要课题,比对结果的合理性和正确性关系到基于比对结果研究的正确性。在保证正确性的前提下利用并行计算充分挖掘计算潜力对提高比对效率有重要意义。针对双序列的全局比对问题,提出了基于蚁群算法的双序列比对并行化方案。对耗时最多的搜索比对路径和信息素更新两个步骤给出了基于共享内存模型的并行化方法。"天河二号"上OpenMP实验结果表明,8线程并行情况下,加速比可达5.03,且序列越长性能越高。

Biological sequence alignment is an important issue in the field of bioinformatics, and the rationality and correctness of alignment results are crucial to the researches based on sequence alignment. It is of great significance to exploit the computational potential with the help of parallel computing to improve alignment efficiency under the premise of ensuring alignment correctness. We propose a parallel alignment scheme based on the ant colony algorithm for the global sequences alignment problem. Aiming at the two most time-consuming steps in the ant colony algorithm, the search of comparison path and the pheromone update, we present a parallel method based on the shared memory model. Experiments on Tianhe II by the OpenMP show that with eight threads in parallel, the speedup can achieve 503, and the longer the sequence is, the better the performance is.