This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Arslan, A. N. Articles by Egecioglu, O. Search for Related Content

Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints

Abdullah N. Arslan, Ömer Eeciolu

Department of Computer Science, University of Vermont, Burlington, Vermont 05405, USA
Department of Computer Science, University of California, Santa Barbara, Santa Barbara, California 93106, USA
aarslan{at}cs.uvm.edu
omer{at}cs.ucsb.edu

Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I X and J Y with maximum similarity score under a given scoring scheme. In several applications, variants of this problem arise with different objectives and with length constraints on the subsequences I and J. This constraint can be explicit, such as requiring | I | + | J | t, or | J | T, or may be implicit such as in cyclic sequence comparison, or as in the maximization of length-normalized scores, and driven by practical considerations. We present a survey of approximation algorithms for various alignment problems with constraints, and several new approximation algorithms. These approximations are in two distinct senses: In one the constraints are satisfied but the score computed is within a prescribed tolerance of the optimum instead of the exact optimum. In another, the alignment returned is assured to have at least the optimum score with respect to the given constraints, but the length constraints are satisfied to within a prescribed tolerance from the required values. The algorithms proposed involve applications of techniques from fractional programming and dynamic programming.

Key words: local alignment; cyclic sequence comparison; normalized local alignment; length-restricted local alignment; approximation algorithm; dynamic programming; ratio maximization; fractional programming
History: received August 2003; revised February 2004; accepted February 2004.