Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

An exact mathematical programming approach to multiple RNA sequence-structure alignment
Bauer, Markus ;  Klau, Gunnar W. ;  Reinert, Knut ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelAn exact mathematical programming approach to multiple RNA sequence-structure alignment
AutorBauer, Markus
AutorKlau, Gunnar W.
AutorReinert, Knut
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl25 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]07,07
DDC005 Programmierung, Programme, Daten
510 Mathematik
ZusammenfassungOne of the main tasks in computational biology is the computation of alignments of genomic sequences to reveal their commonalities. In case of DNA or protein sequences, sequence information alone is usually sufficient to compute reliable alignments. RNA molecules, however, build spatial conformations—the secondary structure—that are
more conserved than the actual sequence. Hence, computing reliable alignments of RNA molecules has to take into account the secondary structure. We present a novel framework for the computation of exact multiple sequence-structure alignments: We give a graph-theoretic representation of the sequence-structure alignment problem and phrase it as an integer linear program. We identify a class of constraints that make the problem easier to solve and relax the original integer linear program in a Lagrangian manner. Experiments on a recently published benchmark show that our algorithms has a comparable performance than more costly dynamic programming algorithms, and outperforms all other approaches in terms of solution quality with an increasing number of input sequences.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr2007
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am14.10.2009 - 13:13:05
Letzte Änderung23.01.2014 - 16:21:33
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000003920
Zugriffsstatistik
 

LOADING...