Affiliations: [a]
Institute of Computer and Communication Engineering, Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C. | [b]
Department of Computer Science and Entertainment Technology, Tajen university, Pingtung, Taiwan, R.O.C. | [c]
Department of Computer Science and Information Engineering, National Ilan University, Yilan, Taiwan, R.O.C. | [d]
Department of Psychology, National Cheng Kung University, Tainan, Taiwan, R.O.C.
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.
Keywords: Gravitation search algorithm, DNA sequence fragment assembly, meta-heuristic algorithm, memetic algorithm
