• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 论文 • 上一篇    下一篇

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

李娟1,汤德佑1,傅娟2,3   

  1. (1.华南理工大学软件学院,广东 广州 510006;
    2.湖南工业大学绿色包装与生物纳米技术应用湖南省重点实验室,湖南 株洲 412008;
    3.华南理工大学医学院,广东 广州 510006)
     
  • 收稿日期:2016-01-11 修回日期:2016-05-16 出版日期:2017-09-25 发布日期:2017-09-25
  • 基金资助:

    国家自然科学基金(61201100);广州市科技计划(201508010029)

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

LI Juan1,TANG De-you1,FU Juan2,3
  

  1. (1.School of Software Engineering,South China University of Technology,Guangzhou 510006;
    2.Hunan Key Laboratory of Green Packaging and Application of Biological Nanotechnology,
    Hunan University of Technology,Zhuzhou 412008;
    3.School of Medicine,South China University of Technology,Guangzhou 510006,China)
  • Received:2016-01-11 Revised:2016-05-16 Online:2017-09-25 Published:2017-09-25

摘要:

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

关键词: 生物序列比对, 并行算法, 蚁群算法, OpenMP

Abstract:

 
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.
 
 

Key words: biological sequence alignment, parallel algorithm, ant colony algorithm, OpenMP