A space-efficient algorithm for aligning large genomic sequences

被引：19

作者：

Morgenstern, B ^{[1
]}

机构：

[1] Max Planck Inst Biochem, D-82152 Martinsried, Germany

来源：

BIOINFORMATICS | 2000年 / 16卷 / 10期

关键词：

D O I：

10.1093/bioinformatics/16.10.948

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

In the segment-by-segment approach to sequence alignment, pairwise and multiple alignments are generated by comparing gap-free segments of the sequences under study This method is particularly efficient in detecting local homologies, and it has been used to identify functional regions irt large genomic sequences. Herein, an algorithm is outlined that calculates optimal pairwise segment-by-segment alignments in essentially linear space.

引用

页码：948 / 949

页数：2

共 9 条

[1] Abdeddaim S., 2000, P JOURN OUV BIOL INF, P1
[2] LINEAR-SPACE ALGORITHMS THAT BUILD LOCAL ALIGNMENTS FROM FRAGMENTS
CHAO, KM
MILLER, W
[J]. ALGORITHMICA, 1995, 13 (1-2) : 106 - 134
[3] SPARSE DYNAMIC-PROGRAMMING .1. LINEAR COST-FUNCTIONS
EPPSTEIN, D
GALIL, Z
GIANCARLO, R
ITALIANO, GF
[J]. JOURNAL OF THE ACM, 1992, 39 (03) : 519 - 545
[4] Analysis of vertebrate SCL loci identifies conserved enhancers
Göttgens, B
Barton, LM
Gilbert, JGR
Bench, AJ
Sanchez, MJ
Bahn, S
Mistry, S
Grafham, D
McMurray, A
Vaudin, M
Amaya, E
Bentley, DR
Green, AR
[J]. NATURE BIOTECHNOLOGY, 2000, 18 (02) : 181 - 186
[5] LINEAR SPACE ALGORITHM FOR COMPUTING MAXIMAL COMMON SUBSEQUENCES
HIRSCHBERG, DS
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 341 - 343
[6] DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment
Morgenstern, B
[J]. BIOINFORMATICS, 1999, 15 (03) : 211 - 218
[7] Multiple DNA and protein sequence alignment based on segment-to-segment comparison
Morgenstern, B
Dress, A
Werner, T
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1996, 93 (22) : 12098 - 12103
[8] OPTIMAL ALIGNMENTS IN LINEAR-SPACE
MYERS, EW
MILLER, W
[J]. COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1988, 4 (01): : 11 - 17
[9] THE CONTEXT DEPENDENT COMPARISON OF BIOLOGICAL SEQUENCES
WILBUR, WJ
LIPMAN, DJ
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1984, 44 (03) : 557 - 567

← 1 →