Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions

Schwikowski, B., & Vingron, M. (2003). Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions. Discrete Applied Mathematics, 127(1), 95-117. doi:10.1016/S0166-218X(02)00288-3.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Zeitschriftenartikel
Alternativer Titel : Discret Appl. Math.

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Schwikowski, Benno, Autor
Vingron, Martin1, Autor           
Affiliations:
1Gene regulation (Martin Vingron), Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society, ou_1479639              

Inhalt

einblenden:
ausblenden:
Schlagwörter: computational molecular biology; algorithms; multiple alignment; evolutionary tree; phylogenetic tree; tree alignment program; dynamic programming
 Zusammenfassung: We present a novel technique for improving a fundamental aspect of iterated dynamic programming procedures on sequences, such as progressive sequence alignment. Instead of relying on the unrealistic assumption that each iteration can be performed accurately without including information from other sequences, our technique employs the combinatorial data structure of weighted sequence graphs to represent an exponential number of optimal and suboptimal sequences. The usual dynamic programming algorithm on linear sequences can be generalized to weighted sequence graphs, and therefore allows to align sequence graphs instead of individual sequences in subsequent stages. Thus, locally suboptimal, but globally correct solutions can for the first time be identified through iterated sequence alignment. We demonstrate the utility of our technique by applying it to the benchmark alignment problem of Sankoff et al. (J. Mol. Evol. 7 (1976) 133). Although a recent effort could improve on the original solution from 1976 slightly, our technique leads to even more significant improvements.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003-04-01
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 176233
ISI: 000181779800008
DOI: 10.1016/S0166-218X(02)00288-3
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Discrete Applied Mathematics
  Alternativer Titel : Discret Appl. Math.
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 127 (1) Artikelnummer: - Start- / Endseite: 95 - 117 Identifikator: ISSN: 0166-218X