Abstract:
The longest common subsequence problem is a classical string problem that concerns of finding
the common subsequence which is the longest of every member of a given set of strings,
where input strings are assumed to be independent. This problem is one of the most studied
computational problem in bioinfo:rmatics and computational biology. The problem is
NP-hard for more than two input strings and the existing exact solutions are impractical for
large input sizes. It has several important applications such as computational biology, data
compression, pattern recognition, FPGA circuit minimization and bioinformatics. Most
research efforts up to now have focused on solving this problem optimally. Several approximation,
heuristic and meta heuristic algorithms have been propo~ed which aim at finding
good solution to the problem but not necessarily optimal. In this thesis, we propose both
deterministic and nondeterministic algorithms. Initially, we work on expansion algorithm of
Bonizzoni et al., then we propose an algorithm based on dynamic programming. Both are
deterministic algorithms. Finally, we integrate the stochastic and heuristic approaches with
dynamic programming method and we propose new nondeterministic algorithms based on
stochastic, heuristic an~ dynamic programming method. We have used heuristic functions,
inspired by the pheromone update st~ategy of ant colo~y optimization system. We integrate
local search technique in our algorithms to improve the results. The proposed algorithms
are compared with the state-of-the-art algorithms over several standard benchmarks, including
simulated and real biological sequences. Extensive experimental results show that
the proposed algorithm outperforms the state-of-the-art by giving higher quality solutions
with reasonable time for most of the experimental cases.
