1. A memetic gravitation search algorithm for solving DNA fragment assembly problems
- Author
-
Ko-Wei Huang, Chun-Wei Tsai, Jui-Le Chen, and Chu-Sing Yang
- Subjects
0301 basic medicine ,Statistics and Probability ,Mathematical optimization ,education.field_of_study ,Population ,General Engineering ,Initialization ,Swarm behaviour ,02 engineering and technology ,Tabu search ,03 medical and health sciences ,030104 developmental biology ,Fragment (logic) ,Artificial Intelligence ,Search algorithm ,Simulated annealing ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,education ,Algorithm ,Variable neighborhood search ,Mathematics - Abstract
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.
- Published
- 2016