Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization
Bauer, Markus ;  Klau, Gunnar W. ;  Reinert, Knut ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleAccurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization
AuthorBauer, Markus
AuthorKlau, Gunnar W.
AuthorReinert, Knut
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages30 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]07,06
Classification (DDC)005 Computer programming, programs, data
AbstractBackground: The discovery of functional non-coding RNA sequences has led to an increasing interest in algorithms related to RNA analysis. Traditional sequence alignment algorithms, however, fail at computing reliable alignments of low-homology RNA sequences. The spatial conformation of RNA sequences largely determines their function, and therefore RNA alignment algorithms have to take structural information into account.

Results: We present a graph-based representation for sequence-structure alignments, which we model as an integer linear program (ILP). We sketch how we compute an optimal or near-optimal solution to the ILP using methods from combinatorial optimization, and present results on a recently published benchmark set for RNA

Conclusions: The implementation of our algorithm yields better alignments in terms of two published scores than the other programs that we tested: This is especially the case with an increasing number of input sequences. Our program LaRA is freely available from http://www.planet-lisa.net.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2007
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-10-14 : 12:38:05
Last changed2015-03-03 : 01:32:00
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000003915