A memetic gravitation search algorithm for solving DNA fragment assembly problems

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

Research output: Contribution to journalArticlepeer-review

4 Citations (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.

Original languageEnglish
Pages (from-to)2245-2255
Number of pages11
JournalJournal of Intelligent and Fuzzy Systems
Issue number4
Publication statusPublished - 2016 Mar 10

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'A memetic gravitation search algorithm for solving DNA fragment assembly problems'. Together they form a unique fingerprint.

Cite this