A hybrid crow search algorithm for solving the DNA fragment assembly problem. (15th July 2018)

• Record Type: Journal Article
• Authors: Allaoui, Mohcin; Ahiod, Belaïd; El Yafrani, Mohamed
• Is Part Of: Expert systems with applications. Volume 102(2018)
• Page Start: 44
• Page End: 56
• Publication Date: 2018-07-15
• Subjects: Crow search algorithm -- DNA fragment assembly -- Discrete optimization -- PALS2-many*; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.02.018
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: An adaptation of the crow search algorithm to solve the DNA fragment assembly problem is proposed. A combination of CSA and a PALS based local search allowed superior performances. Generating new solutions is based on a modified ordered crossover operator (OX). Abstract: 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.