Applying the firefly approach to the DNA fragments assembly problem

Abstract. In Informatics we sometimes come across problems, which cannot be solved by common algorithms. Other times, the devised algorithms are too complex for real use. An alternative solution can often be found in the use of metaheuristics. One of the metaheuristics subgroups are algorithms inspired by nature. Their main inspiration is nature itself. They imitate processes from life. Social insects like ants or bees are good examples. At the first sight they are very simple organisms. When we look closer, however, their overall behavior is amazing, as is their organization in a swarm when working towards their common goal. Application of these algorithms can lead to interesting solutions in many different fields, especially when no other viable solution is available.
DNA assembly is one of such problems. The problem is to assemble DNA from fragments read by some DNA sequencing technology, since current technologies are not able to read the whole DNA sequence, only much shorter fragments. We propose a possible solution to the DNA assembly problem by use of a biologically inspired algorithm that imitates fireflies. We adapted algorithm for this problem and designed new algorithm operators. We implemented the proposed solution in a prototype. Finally, we successfully verified the algorithm on GenFrag and DNAgen benchmark instances of DNA problem.