A Parallel Algorithm for Solving LCS of Multiple Bioseqences

A fast algorithm named FAST_LCS is presented for the longest common substring (LCS) problem. The algorithm firstly seeks the successors of the initial identical character tuples according to successor tables to obtain all the identical tuples and their levels. Then the result of LCS can be obtained by tracing back from the identical character tuple with the largest level. For n biosequences X ₁, X₂, ..., X_n, the time complexity of sequentially execution of our algorithm is O(L). Here L is the number of identical character tuples. The time complexity of our parallel algorithm is O(|LCS|), where LCS is the length of the longest common substring of X₁, X₂, ... , X_n. This time complexity is independent of the number of sequences n. Some experiments have been conducted on the gene sequences of tigr database using MPP parallel computer Shenteng 1800. The results show that our algorithm is accurate and more efficient than other LCS algorithms