Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
Autore:
Morgenstern, B;
Indirizzi:
GSF Natl Res Ctr Environm & Hlth, Inst Biomath & Biometry, D-85764 Neuherberg, Germany GSF Natl Res Ctr Environm & Hlth Neuherberg Germany D-85764 erg, Germany
Titolo Testata:
APPLIED MATHEMATICS LETTERS
fascicolo: 1, volume: 15, anno: 2002,
pagine: 11 - 16
SICI:
0893-9659(200201)15:1<11:ASASFA>2.0.ZU;2-Y
Fonte:
ISI
Lingua:
ENG
Soggetto:
LINEAR-SPACE; MULTIPLE; ACID;
Keywords:
sequence alignment; string algorithm; fragment chaining; dynamic programming; complexity;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Physical, Chemical & Earth Sciences
Citazioni:
14
Recensione:
Indirizzi per estratti:
Indirizzo: Morgenstern, B Max Planck Inst Biochem, MIPS, Klopferspitz 18A, D-82152 Martinsried, Germany Max Planck Inst Biochem Klopferspitz 18A Martinsried Germany D-82152
Citazione:
B. Morgenstern, "A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences", APPL MATH L, 15(1), 2002, pp. 11-16

Abstract

In the segment-based approach to sequence alignment, nucleic acid, and protein sequence alignments are constructed from fragments, i.e., from pairs of ungapped segments of the input sequences. Given a set F of candidate fragments and a weighting function w : F --> R-0(+), the score of an alignment is defined as the sum of weights of the fragments it consists of, and the optimization problem is to find a consistent collection of pairwise disjointfragments with maximum sum of weights. Herein, a sparse dynamic programming algorithm is described that solves the pairwise segment-alignment problemin O(L + N-max) space where L is the maximum length of the input sequenceswhile N-max less than or equal to #F holds. With a recently introduced weighting function w, small sets F of candidate fragments are sufficient to obtain alignments of high quality, As a result, the proposed algorithm runs in essentially linear space. (C) 2001 Elsevier Science Ltd. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 19/01/20 alle ore 11:40:40