The problem of finding the longest common subsequence (lcs) of a given set of sequences over an alphabet ∑ occurs in many interesting contexts, such as data compression and molecular biology, in order to measure the "similarity degree" among biological sequences. Since the problem is NP-complete in its decision version (i.e. does there exist a lcs of length at least k for a given k?) even over fixed alphabet, polynomial algorithms which give approximate solutions have been proposed. Among them, Long Run [LR] is the only one with guaranteed constant performance ratio. In this paper, we give a new approximation algorithm for the longest common subsequence problem: the Expansion Algorithm (EA). First of all, we prove that the solution found by the Expansion Algorithm is always at least as good as the one found by LR. Then we report the results of an experimentation with two different groups of instances, which show that EA clearly outperforms Long Run in practice.
展开▼
机译：在字母∑上找到给定序列集的最长公共子序列（lcs）的问题发生在许多有趣的情况下，例如数据压缩和分子生物学，目的是测量生物学序列之间的“相似度”。由于该问题在其决策版本中是NP完全的（即，对于给定的k′，是否存在长度至少为k的lcs），甚至在固定字母表上也是如此，因此提出了给出近似解的多项式算法。其中，Long Run [LR]是唯一可以保证恒定性能比的产品。在本文中，我们针对最长的公共子序列问题给出了一种新的近似算法：扩展算法（EA）。首先，我们证明了扩展算法找到的解决方案始终至少与LR找到的解决方案一样好。然后，我们报告了两组不同实例的实验结果，这些结果表明EA在实践中明显胜过Long Run。
展开▼
