基于并行ACO算法的DNA杂交测序

摘要

Aiming at the problems of lower precision of solution and the lower speed of convergence in relevant algorithms for DNA Sequencing By Hybridization(SBH) problem, this paper makes a model for SBH problem and extracts the heuristic information. An Improved Parallel Ant Colony Optimization(IPACO) algorithm is proposed for DNA SBH. Simulation experimental results show this algorithm has better performance compared with serial ACO, tabu search and evolutionary algorithm in precision and convergence.%针对求解DNA杂交测序(SBH)问题的相关算法存在解的精度不高及收敛速度慢等问题,建立SBH问题的数学模型,从中抽取启发式信息,提出一种改进的并行蚁群优化算法(IPACO),并将其应用到DNA杂交测序问题中.仿真实验结果表明,该算法解的精度和收敛速度均优于普通串行蚁群算法、禁忌搜索算法和进化算法.