Finding the longest common subsequence for multiple biological sequences by ant colony optimization

Finding the longest common subsequence (LCS) for a set of nn (an arbitrary n>2)n>2) sequences is an NPNP-hard problem. It is an essential operation for a wide range of applications in the areas of computational biology, pattern recognition, string editing and data compression, to name a few. In this paper, we design a novel ant colony optimization (ACO) algorithm to find the approximate solution to the LCS problem for multiple biological sequences. The performances of our ACO algorithm, the known expansion algorithm [Bonizzoni P, Vedova GD, Mauri G. Experimenting an approximation algorithm for the LCS. Discrete Applied Mathematics 2001;110:13–24] and best next for maximal available symbol algorithm [Huang KS, Yang CB, Tseng KT. Fast algorithms for finding the common subsequence of multiple sequences. In: Proceedings of international computer symposium; 2004. p. 90–95] were tested and compared by using various sets of DNA and protein sequences. The experimental results demonstrate the effectiveness and efficiency of the proposed ACO algorithm in dealing with the LCS problem for multiple biological sequences.