View article

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 …