A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
This addresses a computational bottleneck in bioinformatics, computational linguistics, and information retrieval for handling many strings, though it is incremental as it builds on known MCS concepts.
The paper tackles the NP-hard problem of finding a Longest Common Subsequence (LCS) for multiple strings by developing a randomized algorithm called Random-MCS that finds a Maximal Common Subsequence (MCS) with linear complexity in the number of strings, and shows that running it multiple times often yields an LCS solution.
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 {\em Random-MCS}, for finding a random instance of Maximal Common Subsequence ($MCS$) of multiple strings. A common subsequence is {\em 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 {\em Random-MCS} often yields a solution to $LCS$.