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.
