A simple algorithm for the constrained sequence problems

Abstract

In this paper we address the constrained longest common subsequence problem. Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is the longest subsequence of X and Y such that P is a subsequence of Z. Recently, Tsai [Inform. Process. Lett. 88 (2003) 173-176] proposed an O(n 2·m2·r) time algorithm to solve this problem using dynamic programming technique, where n, m and r are the lengths of X, Y and P, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in O(n·m·r) time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved with the same time complexity. © 2004 Published by Elsevier B.V.