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 [J].

MYERS, EW ;

MILLER, W .

COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1988, 4 (01) :11-17

[12] CHLOROPLAST GENE ORGANIZATION DEDUCED FROM COMPLETE SEQUENCE OF LIVERWORT MARCHANTIA-POLYMORPHA CHLOROPLAST DNA [J].

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 .

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 [J].

RABANI, Y ;

GALIL, Z .

THEORETICAL COMPUTER SCIENCE, 1992, 95 (02) :231-244

[15] SOFTWARE TOOLS FOR ANALYZING PAIRWISE ALIGNMENTS OF LONG SEQUENCES [J].

SCHWARTZ, S ;

MILLER, W ;

YANG, CM ;

HARDISON, RC .

NUCLEIC ACIDS RESEARCH, 1991, 19 (17) :4663-4667

[16] FINE-STRUCTURAL FEATURES OF THE CHLOROPLAST GENOME - COMPARISON OF THE SEQUENCED CHLOROPLAST GENOMES [J].

SHIMADA, H ;

SUGIURA, M .

NUCLEIC ACIDS RESEARCH, 1991, 19 (05) :983-995

[17] THE COMPLETE NUCLEOTIDE-SEQUENCE OF THE TOBACCO CHLOROPLAST GENOME - ITS GENE ORGANIZATION AND EXPRESSION [J].

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 .

EMBO JOURNAL, 1986, 5 (09) :2043-2049

[18] EFFICIENT SEQUENCE ALIGNMENT ALGORITHMS [J].

WATERMAN, MS .

JOURNAL OF THEORETICAL BIOLOGY, 1984, 108 (03) :333-337

[19] THE CONTEXT DEPENDENT COMPARISON OF BIOLOGICAL SEQUENCES [J].

WILBUR, WJ ;

LIPMAN, DJ .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1984, 44 (03) :557-567

[20] IDENTIFICATION OF FUNCTIONAL OPEN READING FRAMES IN CHLOROPLAST GENOMES [J].

WOLFE, KH ;

SHARP, PM .

GENE, 1988, 66 (02) :215-222