| 一种基于蚁群算法的生物序列并行比对方法 |
| |
| 引用本文： | 李娟,汤德佑,傅娟.一种基于蚁群算法的生物序列并行比对方法[J].计算机工程与科学,2017,39(9):1610-1616. |
| |
| 作者姓名： | 李娟 汤德佑 傅娟 |
| |
| 作者单位： | （1.华南理工大学软件学院，广东 广州 510006；
2.湖南工业大学绿色包装与生物纳米技术应用湖南省重点实验室，湖南 株洲 412008；
3.华南理工大学医学院，广东 广州 510006） |
| |
| 基金项目： | 国家自然科学基金(61201100)；广州市科技计划(201508010029) |
| |
| 摘 要： | 生物序列比对是生物信息领域的重要课题,比对结果的合理性和正确性关系到基于比对结果研究的正确性。在保证正确性的前提下利用并行计算充分挖掘计算潜力对提高比对效率有重要意义。针对双序列的全局比对问题,提出了基于蚁群算法的双序列比对并行化方案。对耗时最多的搜索比对路径和信息素更新两个步骤给出了基于共享内存模型的并行化方法。"天河二号"上OpenMP实验结果表明,8线程并行情况下,加速比可达5.03,且序列越长性能越高。
|
| 关 键 词： | 生物序列比对 并行算法 蚁群算法 OpenMP |
| 收稿时间： | 2016-01-11 |
| 修稿时间： | 2017-09-25 |
A parallel alignment method for biological
sequences based on ant colony algorithm |
| |
| LI Juan,TANG De-you,FU Juan.A parallel alignment method for biological
sequences based on ant colony algorithm[J].Computer Engineering & Science,2017,39(9):1610-1616. |
| |
| Authors: | LI Juan TANG De-you FU Juan |
| |
| Affiliation: | (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) |
| |
| 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 503, and the longer the sequence is, the better the performance is. |
| |
| Keywords: | biological sequence alignment parallel algorithm ant colony algorithm OpenMP |
|
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
