Computing a Longest Common Subsequence for Multiple Sequences

The longest common subsequence problem is a classical string problem that aims at computing a common subsequence having the highest possible length from a given set of strings. This problem is one of the most studied computational problems in bioinformatics and computational biology. The problem is NP-hard for more than two input strings and the existing exact solutions are impractical for large input size. In this paper, we propose a new nondeterministic algorithm based on stochastic and dynamic programming method. In our algorithm, we have employed a heuristic that is inspired by the pheromone update strategy of the ant colony system. We have also integrated a local search technique in our algorithm to improve our results. The proposed algorithm is compared with the state-of-the-art algorithms over several standard benchmarks including simulated and real biological sequences. Experimental results show that the proposed algorithm can provide high quality solutions within a reasonable amount of time.