Algorithms for computing variants of the longest common subsequence problem

Abstract. The longest common subsequence(LCS) problem is one of the classical and wellstudied 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 define new variants, introducing the notion of gap-constraints in LCS problem and present efficient algorithms to solve them. The new variants are motivated by practical applications in molecular biology.