Dynamic programming alignment of sequences representing cyclic patterns
J Gregor, MG Thomason - IEEE transactions on pattern …, 1993 - ieeexplore.ieee.org
IEEE transactions on pattern analysis and machine intelligence, 1993•ieeexplore.ieee.org
String alignment by dynamic programming is generalized to include cyclic shift and
corresponding optimal alignment cost for strings representing cyclic patterns. A guided
search algorithm uses bounds on alignment costs to find all optimal cyclic shifts. The bounds
are derived from submatrices of an initial dynamic programming matrix. Algorithmic
complexity is analyzed for major stages in the search. The applicability of the method is
illustrated with satellite DNA sequences and circularly permuted protein sequences.<>
corresponding optimal alignment cost for strings representing cyclic patterns. A guided
search algorithm uses bounds on alignment costs to find all optimal cyclic shifts. The bounds
are derived from submatrices of an initial dynamic programming matrix. Algorithmic
complexity is analyzed for major stages in the search. The applicability of the method is
illustrated with satellite DNA sequences and circularly permuted protein sequences.<>
String alignment by dynamic programming is generalized to include cyclic shift and corresponding optimal alignment cost for strings representing cyclic patterns. A guided search algorithm uses bounds on alignment costs to find all optimal cyclic shifts. The bounds are derived from submatrices of an initial dynamic programming matrix. Algorithmic complexity is analyzed for major stages in the search. The applicability of the method is illustrated with satellite DNA sequences and circularly permuted protein sequences.< >
ieeexplore.ieee.org