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

Markus Bauer, Gunnar W. Klau, and Knut Reinert
Institut für Mathematik und Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: {mbauer,gunnar,reinert}



Report B 07-06
March 2007


Abstract 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. 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. 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 here.

Get the report here or by anonymous ftp:
File: pub/reports/tr-b-07-06.pdf