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

ABSTRACT:

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 implemen

SUBMITTER: Bauer M 

PROVIDER: S-EPMC1955456 | biostudies-literature | 2007 Jul

REPOSITORIES: biostudies-literature