Practical models and algorithms for the DNA fragment assembly problem

Abstract

DNA fragment assembly problem is one of the crucial challenges faced by com- putational biologists where, given a set of DNA fragments, we have to construct a complete DNA sequence from them. As it is an NP-hard problem, accurate DNA sequence is hard to ¯nd. Moreover, due to experimental limitations, the frag- ments considered for assembly are exposed to additional errors while reading the fragments. In such scenarios, meta-heuristic based algorithms can come in handy. In this thesis, we have taken the ¯rst ever approach to generate noisy datasets using three realistic error models namely Sanger Sequencing error model, 454 Se- quencing error model and Exact error model. Next, we analyze the performance of two swarm intelligence based algorithms namely Arti¯cial Bee Colony (ABC) algorithm and Queen Bee Evolution Based on Genetic Algorithm (QEGA) to solve the fragment assembly problem and report quite promising results. We also pro- pose two hybrid algorithms namely Genetic Algorithm with Simulated Annealing (GA+SA) and Genetic Algorithm with Hill Climbing (GA+HC) for noiseless and noisy datasets. Additionally, we evaluate the performance of Genetic algorithm with noisy datasets. Our main focus is to design meta-heuristic based techniques to e±ciently handle DNA fragment assembly problem for noisy and noiseless data.