CONSTRAINED SEQUENCE ALIGNMENT

被引：14

作者：

CHAO, KM

HARDISON, RC

MILLER, W

机构：

[1] PENN STATE UNIV,DEPT MOLEC & CELL BIOL,UNIV PK,PA 16802

[2] PENN STATE UNIV,INST MOLEC EVOLUTIONARY GENET,UNIV PK,PA 16802

来源：

BULLETIN OF MATHEMATICAL BIOLOGY | 1993年 / 55卷 / 03期

关键词：

D O I：

10.1007/BF02460648

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

This paper presents a dynamic programming algorithm for aligning two sequences when the alignment is constrained to lie between two arbitrary boundary lines in the dynamic programming matrix. For affine gap penalties, the algorithm requires only O(F) computation time and O(M + N) space, where F is the area of the feasible region and M and N are the sequence lengths. The result extends to concave gap penalties, with somewhat increased time and space bounds.

引用

页码：503 / 524

页数：22

共 21 条

[1] BASIC LOCAL ALIGNMENT SEARCH TOOL [J].