Efficient Algorithms for the Flexible Longest Common Subsequence Problem ∗

Given two sequences, the traditional longest common subsequence (LCS) problem is to obtain the common subsequence with the maximum num-ber of matches, without considering the continuity of the matched characters. However, in many ap-plications, the matching results with higher conti-nuity are more meaningful than the sparse ones, even if the number of matched characters is a lit-tle lower. Accordingly, we define a new variant of the LCS problem, called the flexible longest com-mon subsequence (FLCS) problem. In this paper, we design a scoring function to estimate the con-tinuity of a matching result between two strings. We show that the optimal solution of FLCS can be determined in O(n2) time, where n denotes the longer length of the two input sequences. There-fore, the results in this paper offer a new efficient tool for sequence analysis.