Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints

摘要

Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I is contained in X and J is contained in 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 |I| ≤ 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.