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
ALTSCHUL, SF
GISH, W
MILLER, W
MYERS, EW
LIPMAN, DJ
[J]. JOURNAL OF MOLECULAR BIOLOGY, 1990, 215 (03) : 403 - 410
[2] BOGUSKI MS, 1992, NEW BIOL, V4, P247
[3] CHAO KM, 1992, IN PRESS CABIOS
[4] CHAO KM, 1992, UNPUB SPARSE DYNAMIC
[5] EPPSTEIN DZ, 1992, IN PRESS J ASS COMPU
[6] SPEEDING UP DYNAMIC-PROGRAMMING WITH APPLICATIONS TO MOLECULAR-BIOLOGY
GALIL, Z
GIANCARLO, R
[J]. THEORETICAL COMPUTER SCIENCE, 1989, 64 (01) : 107 - 118
[7] A TIME-EFFICIENT, LINEAR-SPACE LOCAL SIMILARITY ALGORITHM
HUANG, XQ
MILLER, W
[J]. ADVANCES IN APPLIED MATHEMATICS, 1991, 12 (03) : 337 - 357
[8] HUANG XQ, 1990, COMPUT APPL BIOSCI, V6, P373
[9] SEQUENCE COMPARISON WITH CONCAVE WEIGHTING FUNCTIONS
MILLER, W
MYERS, EW
[J]. BULLETIN OF MATHEMATICAL BIOLOGY, 1988, 50 (02) : 97 - 120
[10] MYERS EW, 1989, B MATH BIOL, V51, P5, DOI 10.1007/BF02458834

← 1 2 3 →