An algorithm for Constrained LCS

The problem of finding the Constrained Longest Common Subsequence (CLCS) for three sequences is a problem with many applications. In this paper a novel algorithm to compute the CLCS is proposed. The most important features of the proposed algorithm are: i) This algorithm is able to find a set of possible CLCS solutions instead of simply returning the length of the CLCS. ii) The algorithm is based on the concept regarding dominances between subsequences. iii) It is expected that the time complexity of our proposed algorithm will be O(ℓ|Δ∥D|), where |Δ| is the number of matches between the two longer input sequences, |D| is the size of the resulting sets after applying a dominance concept, and ℓ is the length of the computed LCS. iv) The expected space complexity of our proposed algorithm is O(|Δ| + |D|). v) This algorithm is capable of determining the problem´s reliability at a very early stage of its running.