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 条

[11] OPTIMAL ALIGNMENTS IN LINEAR-SPACE
MYERS, EW
MILLER, W
[J]. COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1988, 4 (01): : 11 - 17
[12] CHLOROPLAST GENE ORGANIZATION DEDUCED FROM COMPLETE SEQUENCE OF LIVERWORT MARCHANTIA-POLYMORPHA CHLOROPLAST DNA
OHYAMA, K
FUKUZAWA, H
KOHCHI, T
SHIRAI, H
SANO, T
SANO, S
UMESONO, K
SHIKI, Y
TAKEUCHI, M
CHANG, Z
AOTA, S
INOKUCHI, H
OZEKI, H
[J]. NATURE, 1986, 322 (6079) : 572 - 574
[13] Palmer JD, 1991, MOL BIOL PLASTIDS, V7A
[14] ON THE SPACE COMPLEXITY OF SOME ALGORITHMS FOR SEQUENCE COMPARISON
RABANI, Y
GALIL, Z
[J]. THEORETICAL COMPUTER SCIENCE, 1992, 95 (02) : 231 - 244
[15] SOFTWARE TOOLS FOR ANALYZING PAIRWISE ALIGNMENTS OF LONG SEQUENCES
SCHWARTZ, S
MILLER, W
YANG, CM
HARDISON, RC
[J]. NUCLEIC ACIDS RESEARCH, 1991, 19 (17) : 4663 - 4667
[16] FINE-STRUCTURAL FEATURES OF THE CHLOROPLAST GENOME - COMPARISON OF THE SEQUENCED CHLOROPLAST GENOMES
SHIMADA, H
SUGIURA, M
[J]. NUCLEIC ACIDS RESEARCH, 1991, 19 (05) : 983 - 995
[17] THE COMPLETE NUCLEOTIDE-SEQUENCE OF THE TOBACCO CHLOROPLAST GENOME - ITS GENE ORGANIZATION AND EXPRESSION
SHINOZAKI, K
OHME, M
TANAKA, M
WAKASUGI, T
HAYASHIDA, N
MATSUBAYASHI, T
ZAITA, N
CHUNWONGSE, J
OBOKATA, J
YAMAGUCHISHINOZAKI, K
OHTO, C
TORAZAWA, K
MENG, BY
SUGITA, M
DENO, H
KAMOGASHIRA, T
YAMADA, K
KUSUDA, J
TAKAIWA, F
KATO, A
TOHDOH, N
SHIMADA, H
SUGIURA, M
[J]. EMBO JOURNAL, 1986, 5 (09) : 2043 - 2049
[18] EFFICIENT SEQUENCE ALIGNMENT ALGORITHMS
WATERMAN, MS
[J]. JOURNAL OF THEORETICAL BIOLOGY, 1984, 108 (03) : 333 - 337
[19] THE CONTEXT DEPENDENT COMPARISON OF BIOLOGICAL SEQUENCES
WILBUR, WJ
LIPMAN, DJ
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1984, 44 (03) : 557 - 567
[20] IDENTIFICATION OF FUNCTIONAL OPEN READING FRAMES IN CHLOROPLAST GENOMES
WOLFE, KH
SHARP, PM
[J]. GENE, 1988, 66 (02) : 215 - 222

← 1 2 3 →