A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem

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

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

Abstract

Determining the sequence of a long DNA chain first requires dividing it into subset fragments. The DNA fragment assembly (DFA) approach is then used for reassembling the fragments as an NP-hard problem that is the focus of increasing attention from combinatorial optimization researchers within the computational biology community. Particle swarm optimization (PSO) is one of the most important swarm intelligence meta-heuristic optimization techniques to solve NP-hard combinatorial optimization problems. This paper proposes a memetic PSO algorithm based on two initialization operators and the local search operator for solving the DFA problem by following the overlap–layout–consensus model to maximize the overlapping score measurement. The results, based on 19 coverage DNA fragment datasets, indicate that the PSO algorithm combining tabu search and simulated annealing-based variable neighborhood search local search can achieve the best overlap scores.

Original languageEnglish
Pages (from-to)495-506
Number of pages12
JournalNeural Computing and Applications
Volume26
Issue number3
DOIs
Publication statusPublished - 2015 Apr

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem'. Together they form a unique fingerprint.

Cite this