TY - JOUR
T1 - A hybrid crow search algorithm for solving the DNA fragment assembly problem
AU - Allaoui, Mohcin
AU - Ahiod, Belaïd
AU - El Yafrani, Mohamed
PY - 2018/7/15
Y1 - 2018/7/15
N2 - The sequencing of DNA goes through a step of fragment assembly, this step is known as DNA fragment assembly problem (FAP). Fragment assembly is considered as an NP-hard problem, which means there is no known polynomial-time exact approach, hence the need for meta-heuristics. Three major strategies are widely used to tackle this problem: greedy graph-based algorithms, de Bruijn graphs, and the overlay-layout-consensus (OLC) approach. In this paper, we propose an adaptation of the novel crow search algorithm (CSA) to solve the DNA fragment assembly problem following the OLC model. In order to accelerate the search process and improve the quality of the solutions, we combined CSA with a local search method. Using this combination we were able to obtain very accurate solutions for all the instances of the DNA fragment assembly problem we tested. In fact, our algorithm outperformed all other algorithms designed for the same purpose. Our contribution consists in the implementation of a new assembler for the DNA fragment assembly problem capable of finding for the first time the optimal solutions for 20 out of 30 instances. The approach we proposed to adapt CSA for a discrete optimization problem is a novelty. We preserved the semantics of the original algorithm by applying standard operators from evolutionary algorithms. Following the same approach can make adapting new algorithms for discrete problems more accessible and more efficient compared to mapping algorithms designed for continuous optimization to combinatorial problems.
AB - The sequencing of DNA goes through a step of fragment assembly, this step is known as DNA fragment assembly problem (FAP). Fragment assembly is considered as an NP-hard problem, which means there is no known polynomial-time exact approach, hence the need for meta-heuristics. Three major strategies are widely used to tackle this problem: greedy graph-based algorithms, de Bruijn graphs, and the overlay-layout-consensus (OLC) approach. In this paper, we propose an adaptation of the novel crow search algorithm (CSA) to solve the DNA fragment assembly problem following the OLC model. In order to accelerate the search process and improve the quality of the solutions, we combined CSA with a local search method. Using this combination we were able to obtain very accurate solutions for all the instances of the DNA fragment assembly problem we tested. In fact, our algorithm outperformed all other algorithms designed for the same purpose. Our contribution consists in the implementation of a new assembler for the DNA fragment assembly problem capable of finding for the first time the optimal solutions for 20 out of 30 instances. The approach we proposed to adapt CSA for a discrete optimization problem is a novelty. We preserved the semantics of the original algorithm by applying standard operators from evolutionary algorithms. Following the same approach can make adapting new algorithms for discrete problems more accessible and more efficient compared to mapping algorithms designed for continuous optimization to combinatorial problems.
KW - Crow search algorithm
KW - Discrete optimization
KW - DNA fragment assembly
KW - PALS2-many
UR - http://www.scopus.com/inward/record.url?scp=85042460702&partnerID=8YFLogxK
U2 - 10.1016/j.eswa.2018.02.018
DO - 10.1016/j.eswa.2018.02.018
M3 - Journal article
AN - SCOPUS:85042460702
SN - 0957-4174
VL - 102
SP - 44
EP - 56
JO - Expert Systems with Applications
JF - Expert Systems with Applications
ER -