Accurate Multiple Sequence-Structure Alignment of RNA Sequences Using Combinatorial Optimization

Markus Bauer, Gunnar W. Klau, and Knut Reinert – 2007

Background: 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 alignments. 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.

Titel
Accurate Multiple Sequence-Structure Alignment of RNA Sequences Using Combinatorial Optimization
Verfasser
Markus Bauer, Gunnar W. Klau, and Knut Reinert
Verlag
Freie Universität Berlin, Institute of Computer Science
Ort
Takustr. 9, 14195 Berlin, Germany
Datum
2007-03
Kennung
B-07-06
Sprache
eng
Art
Text