Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: A simple and spaceefficient fragmentchaining algorithm for alignment of DNA and protein sequences
Autore: Morgenstern, B;
 Indirizzi:
 GSF Natl Res Ctr Environm & Hlth, Inst Biomath & Biometry, D85764 Neuherberg, Germany GSF Natl Res Ctr Environm & Hlth Neuherberg Germany D85764 erg, Germany
 Titolo Testata:
 APPLIED MATHEMATICS LETTERS
fascicolo: 1,
volume: 15,
anno: 2002,
pagine: 11  16
 SICI:
 08939659(200201)15:1<11:ASASFA>2.0.ZU;2Y
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 LINEARSPACE; 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, D82152 Martinsried, Germany Max Planck Inst Biochem Klopferspitz 18A Martinsried Germany D82152



 Citazione:
 B. Morgenstern, "A simple and spaceefficient fragmentchaining algorithm for alignment of DNA and protein sequences", APPL MATH L, 15(1), 2002, pp. 1116
Abstract
In the segmentbased 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 > R0(+), 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 segmentalignment problemin O(L + Nmax) space where L is the maximum length of the input sequenceswhile Nmax 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