Time and space efficient algorithms for constrained sequence alignment

Abstract

In this paper, we study the constrained sequence alignment problem, which is a generalization of the classical sequence alignment problem with the additional constraint that some characters in the alignment must be positioned at the same columns. The problem finds important applications in Bioinformatics. Our major result is an O(ℓn2)-time and O(ℓn)-space algorithm for constructing an optimal constrained alignment of two sequences where n is the length of the longer sequence and ℓ is the length of the constraint. Our algorithm matches the best known time complexity and reduces the best known space complexity by a factor of n for solving the problem. We also apply our technique to design time and space efficient heuristic and approximation algorithm for aligning multiple sequences. © Springer-Verlag Berlin Heidelberg 2005.