Abstract:

This paper proposes two approximation algorithms for LCS problem of three input strings. Even if the approximation factors of the two algorithms are still 1/|?|, they can both get much better results in comparison of Gotthilf’s approximating LCS algorithm in most cases. Linear approximating LCS algorithm, takes O(n) time and O(n) space, where n is the length of the longest input sequence. It can work well in the case of large scale input strings. Recursive approximating LCS algorithm, whose time and space complexities both are O(nlogn), can receive the best precision among these algorithms at the most time. It is applicable to meet the desire of good precision for corresponding LCS problem. The two algorithms can be used to solve the LCS problem of multiple sequences and CLCS problem of multiple sequences. Experimental results prove the validity of the two algorithms.

Key words: bioinformatics, Longest Common Subsequence(LCS), approximation factor, constraint

摘要：

提出2种针对3条源序列的近似LCS算法，近似因子均为1/|?|。其中，线性近似LCS算法的时空复杂度均为 ， 为最长源序列的长度，适于解决大规模问题。递归近似LCS算法时空复杂度均为O(nlogn)，适于要求高精度问题。同时，这2种算法都能用于解决多序列的LCS和CLCS问题。实验验证了这2种算法的有效性。

关键词: 生物信息学, 最长公共子序列, 近似因子, 约束

CLC Number: 

• TP311.52