DYNAMIC-PROGRAMMING ALIGNMENT OF SEQUENCES REPRESENTING CYCLIC PATTERNS

被引：32

作者：

GREGOR, J

THOMASON, MG

机构：

[1] The Department of Computer Science, University of Tennessee, Knoxville, TN

来源：

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 1993年 / 15卷 / 02期

关键词：

CYCLIC PATTERNS; DNA AND PROTEIN SEQUENCES; DYNAMIC PROGRAMMING; GUIDED SEARCH; STRING MATCHING; STRUCTURAL PATTERN ANALYSIS;

D O I：

10.1109/34.192484

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 actual 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. Applicability of the method is illustrated with satellite DNA sequences and circularly permuted protein sequences.

引用

页码：129 / 135

页数：7