Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization

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. Conclusion: 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 for academic purposes from http:// www. planet- lisa. net.