A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
share
Finding the common subsequences of L multiple strings has many applications in the area of bioinformatics, computational linguistics, and information retrieval. A well-known result states that finding a Longest Common Subsequence (LCS) for L strings is NP-hard, e.g., the computational complexity is exponential in L. In this paper, we develop a randomized algorithm, referred to as Random-MCS, for finding a random instance of Maximal Common Subsequence (MCS) of multiple strings. A common subsequence is maximal if inserting any character into the subsequence no longer yields a common subsequence. A special case of MCS is LCS where the length is the longest. We show the complexity of our algorithm is linear in L, and therefore is suitable for large L. Furthermore, we study the occurrence probability for a single instance of MCS and demonstrate via both theoretical and experimental studies that the longest subsequence from multiple runs of Random-MCS often yields a solution to LCS.
READ FULL TEXT