Article Preview
Top1. Introduction
Deoxyribonucleic acid (DNA) is a nucleic acid that contains the genetic information in all organisms including humans. The DNA is represented as a long file made up of four chemical bases: adenine (A), guanine (G), cytosine (C), and thymine (T). These bases are 99 percent similar for all humans and usually organisms of the same classes have high similarity in their DNA (Berk et al., 2000). A genome is a stretch of DNA that encodes a polypeptide (protein), which is a set of amino acids bound together in a specific order. The chemical bases are up with each other in the way that base A is always paired with base T, and base C is always with base G. This sequence consists of nucleotides bound together, which are interpreted by the cellular machinery in groups of three, called triplets (Cai et al., 2012).
DNA fragment assembly is a NP-hard problem in computational biology (Pevzner et al., 2001). The human DNA contains about 3 billion bases and cannot be read at once. Experimental techniques have been used to solve this problem by cutting the whole sequence at random positions to a set of fragments. The main objective of DNA fragment assembly is to construct the original DNA sequence from the small fragments by finding the best order of these fragments to maximise overlapping scores between each two consecutive fragments (Bankevich et al., 2012).
Several optimisation-based methods have been proposed to deal with the DFA problem (Pevzner et al, 2001; Caserta et al,. 2014; Chang et al,. 2011; Bocicor et al,. 2011). The main objective of these methods is to construct the original DNA sequence based on the small DNA fragments by maximising the overlapping scores between consecutive sequences. Greedy methods were firstly applied to deal with the DNA fragments assembly problem by Staden (1980), afterwards, metaheuristics were widely used to solve the same problem. Gheraibia et al (2013) proposed Penguins Search Optimisation Algorithm (PeSOA) based on the collaborative hunting strategy of penguins. This metaheuristic algorithm is different from the traditional algorithms in a sense that it controls the expenditure of time on non-useful search area. Penguins hunt fishes in groups to gain energy and synchronise their dives to optimise the overall expenditure of energy in the search process. The PeSOA algorithm starts its operation by generating an initial population. The population is then divided into groups and each group starts searching in a specific location by fixing other parts of the solution. In order to save energy, penguins use the energy reserve to decide whether to hunt or not in a given area. The energy level of a penguin is determined by its oxygen reserve and it is used also as an acceleration coefficient to ensure a good intensification strategy for the global optimum. The number of penguins in a group can vary depending on the quantity of fishes eaten by the penguins of this group which represents the improvement of the objective function of the penguins.
In this paper, a penguins search optimisation algorithm based approach is proposed to deal with the DNA fragment assembly problem. The purpose of the proposed approach is to find the best combination (order) of DNA fragments which maximise the overlap between each two consecutive fragments. To do so penguins are employed to find local solutions where each group of penguins concentrate on a set of fragment and search for solution. The final solution is constructed based on the best local solutions given by each group of penguins. Consequently, solving the DNA fragment assembly problem needs the improvement of total overlapping between fragments and reducing the computation time. To evaluate the efficiency of the proposed method, several experiments have been performed with different benchmarks generated by GenFrag (Engle et al., 1993) and DNAgen (Guillermo et al., 2013) tools. The experiments show that the proposed approach improves the total overlapping score by exploring the search spaces in an efficient way.