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.


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 for academic purposes from http://www.planet-lisa.net.
Bauer
Markus
M
Department of Mathematics and Computer Science, Free University Berlin, Berlin, Germany. mbauer@inf.fu-berlin.de
Klau
Gunnar W
GW
Reinert
Knut
K
D000465:Algorithms; D003198:Computer Simulation; D016014:Linear Models; D008956:Models, Chemical; D008957:Models, Genetic; D012313:RNA / Q000737:chemistry* / Q000235:genetics*; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid
D012313:RNA