New algorithms for the multiple longest common subsequence problems combining dynamic programming and heuristic methods

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.