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

计算机工程与科学

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

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

（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.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

摘要/Abstract

摘要：

生物序列比对是生物信息领域的重要课题，比对结果的合理性和正确性关系到基于比对结果研究的正确性。在保证正确性的前提下利用并行计算充分挖掘计算潜力对提高比对效率有重要意义。针对双序列的全局比对问题，提出了基于蚁群算法的双序列比对并行化方案。对耗时最多的搜索比对路径和信息素更新两个步骤给出了基于共享内存模型的并行化方法。“天河二号”上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

李娟1，汤德佑1，傅娟2，3. 一种基于蚁群算法的生物序列并行比对方法[J]. 计算机工程与科学.

LI Juan1，TANG De-you1，FU Juan2，3.

A parallel alignment method for biological

sequences based on ant colony algorithm

[J]. Computer Engineering & Science.

[1]	傅游, 韩昊, 孙月娇, 梁建国, 叶雨曦, 花嵘. 基于OpenMP的硅晶体分子动力学模拟的空间分解着色及向量化研究#br#[J]. 计算机工程与科学, 2024, 46(9): 1566-1575.
[2]	代长威, 孔瑞林, 季哲, . 面向离散粒子多尺度分析CPU/GPU架构的并行近邻搜索算法[J]. 计算机工程与科学, 2024, 46(8): 1349-1360.
[3]	乔珍, 尹传忠, 仇鑫. 基于改进蚁群算法的长航程无人船路径规划[J]. 计算机工程与科学, 2024, 46(10): 1835-1842.
[4]	肖调杰, 周峰, 郑翾宇, 刘剑, 陈琳, 刘杰, 易明宽, 陈旭光, 龚春叶, 杨博, 甘新标, 李胜国, 左克, . 大规模三维频率域电磁积分方程法数值模拟[J]. 计算机工程与科学, 2023, 45(11): 1901-1910.
[5]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(1): 85-94.
[6]	许晓阳, 王斯棋. 基于粒子分解的SPH并行算法研究与应用[J]. 计算机工程与科学, 2022, 44(6): 964-970.
[7]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(5): 910-915.
[8]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(3): 536-544.
[9]	明平洲, 李治刚, 刘婷, 芦韡, 刘东, 曾辉, 余红星. ARM计算环境下堆芯程序的移植[J]. 计算机工程与科学, 2021, 43(4): 681-688.
[10]	胡平志, 李泽滔. 基于改进蚁群算法的四足机器人步态规划[J]. 计算机工程与科学, 2021, 43(12): 2253-2262.
[11]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[12]	刘杰, 龚春叶, 杨博, 郭晓威, 甘新标, 李胜国, 李超, 陈旭光, 肖调杰, 穆利安, 宋敏, 赵冬勇, 鞠羽中. YH-ACT：热工流体力学并行应用程序[J]. 计算机工程与科学, 2021, 43(1): 58-69.
[13]	马贵平, 潘峰. 基于改进蚁群算法的物流运输路径研究[J]. 计算机工程与科学, 2020, 42(3): 523-528.
[14]	曹新亮, 王智文, 冯晶, 查敏, 王宇航. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学, 2020, 42(3): 564-570.
[15]	张卫祥，齐玉华，魏波，张敏，窦朝晖. 基于蚁群算法的测试用例优先排序[J]. 计算机工程与科学, 2020, 42(2): 241-249.