Algorithms for computing variants of the longest common subsequence problem

作     者：Iliopoulos, Costas S. Rahman, A. Sohel 

作者机构：Kings Coll London Dept Comp Sci Algorithm Design Grp London WC2R 2LS England 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2008年第395卷第2-3期

页      面：255-267页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：CSFP Engineering and Physical Sciences Research Council, EPSRC Royal Society Commonwealth Scholarship Commission, CSC 

主　　题：algorithm longest common subsequence strings 

摘      要：The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in O(n(2) + R(K + 1)(2)) time, where R is the total number of ordered pairs of positions at which the two strings match and K is the fixed gap constraint. We then improve the running time to O(n(2) + RK + R log log n) using some novel techniques. Furthermore, we present an algorithm that is independent of K and runs in O(n(2) + R log log n) time. Using these techniques, we also present a new O(n(2)) algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a O(n(2)) algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to O(n(2)). Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. n. But our results can be easily extended to handle two strings of different length. (c) 2008 Elsevier B.V. All rights reserved.