Unknown

Dataset Information

0

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

SUBMITTER: Bauer M 

PROVIDER: S-EPMC1955456 | biostudies-literature | 2007

REPOSITORIES: biostudies-literature

altmetric image

Publications

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

Bauer Markus M   Klau Gunnar W GW   Reinert Knut K  

BMC bioinformatics 20070727


<h4>Background</h4>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.<h4>Results</h4>We present a graph-based representation for sequence-  ...[more]

Similar Datasets

| S-EPMC3389763 | biostudies-literature
| S-EPMC1579236 | biostudies-literature
| S-EPMC8734264 | biostudies-literature
| S-EPMC4489222 | biostudies-literature
| S-EPMC6330006 | biostudies-literature
| S-EPMC3303701 | biostudies-literature
| S-EPMC4179140 | biostudies-literature
| S-EPMC2677745 | biostudies-literature
| S-EPMC5037421 | biostudies-literature
| S-EPMC7735675 | biostudies-literature