A memetic gravitation search algorithm for solving DNA fragment assembly problems

Ko Wei Huang, Jui Le Chen, Chu Sing Yang, Chun Wei Tsai

研究成果: Article同行評審

5 引文 斯高帕斯(Scopus)


The DNA fragment assembly (DFA) problem is among the most critical problems in computational biology. Being NP-hard, it can be efficiently solved via meta-heuristic algorithms, such as the gravitation search algorithm (GSA). GSA is a state-of-the-art swarm-based algorithm particularly suitable for solving NP-hard combinatorial optimization problems. This paper proposes a new memetic GSA algorithm called MGSA. MGSA is a type of overlap-layout-consensus model that is based on tabu search for population initialization. In order to increase the diversity of MGSA, we adapted two operator time-varying maximum velocities in the GSA procedure. Finally we also adapted the simulated annealing-based variable neighborhood search (SA-VNS) to find superior precise solutions. The proposed MGSA algorithm was verified with 19 DNA fragments based on seeking to maximize the overlap score measurements. In comparing the performances of the proposed MGSA and state-of-the-art algorithms, the simulation results demonstrate that the MGSA can achieve the best overlap scores.

頁(從 - 到)2245-2255
期刊Journal of Intelligent and Fuzzy Systems
出版狀態Published - 2016 三月 10

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Engineering(all)
  • Artificial Intelligence

指紋 深入研究「A memetic gravitation search algorithm for solving DNA fragment assembly problems」主題。共同形成了獨特的指紋。