Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction

Reeder J, Giegerich R (2005)
BIOINFORMATICS 21(17): 3516-3523.

Journal Article | Published | English

No fulltext has been uploaded

Author
;
Abstract
Motivation: The well-known Sankoff algorithm for simultaneous RNA sequence alignment and folding is currently considered an ideal, but computationally over-expensive method. Available tools implement this algorithm under various pragmatic restrictions. They are still expensive to use, and it is difficult to judge if the moderate quality of results is because of the underlying model or to its imperfect implementation. Results: We propose to redefine the consensus structure prediction problem in a way that does not imply a multiple sequence alignment step. For a family of RNA sequences, our method explicitly and independently enumerates the near-optimal abstract shape space, and predicts as the consensus an abstract shape common to all sequences. For each sequence, it delivers the thermodynamically best structure which has this common shape. Since the shape space is much smaller than the structure space, and identification of common shapes can be done in linear time (in the number of shapes considered), the method is essentially linear in the number of sequences. Our evaluation shows that the new method compares favorably with available alternatives.
Publishing Year
ISSN
PUB-ID

Cite this

Reeder J, Giegerich R. Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. BIOINFORMATICS. 2005;21(17):3516-3523.
Reeder, J., & Giegerich, R. (2005). Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. BIOINFORMATICS, 21(17), 3516-3523.
Reeder, J., and Giegerich, R. (2005). Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. BIOINFORMATICS 21, 3516-3523.
Reeder, J., & Giegerich, R., 2005. Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. BIOINFORMATICS, 21(17), p 3516-3523.
J. Reeder and R. Giegerich, “Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction”, BIOINFORMATICS, vol. 21, 2005, pp. 3516-3523.
Reeder, J., Giegerich, R.: Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction. BIOINFORMATICS. 21, 3516-3523 (2005).
Reeder, Jens, and Giegerich, Robert. “Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction”. BIOINFORMATICS 21.17 (2005): 3516-3523.
This data publication is cited in the following publications:
This publication cites the following data publications:

43 Citations in Europe PMC

Data provided by Europe PubMed Central.

The RNA shapes studio.
Janssen S, Giegerich R., Bioinformatics 31(3), 2015
PMID: 25273103
Detecting and comparing non-coding RNAs in the high-throughput era.
Bussotti G, Notredame C, Enright AJ., Int J Mol Sci 14(8), 2013
PMID: 23887659
Abstract folding space analysis based on helices.
Huang J, Backofen R, Voß B., RNA 18(12), 2012
PMID: 23104999
Computational prediction and experimental verification of miRNAs in Panicum miliaceum L.
Wu Y, Du J, Wang X, Fang X, Shan W, Liang Z., Sci China Life Sci 55(9), 2012
PMID: 23015130
Conservation and Occurrence of Trans-Encoded sRNAs in the Rhizobiales.
Reinkensmeier J, Schluter JP, Giegerich R, Becker A., Genes (Basel) 2(4), 2011
PMID: 24710299
Discriminatory power of RNA family models.
Honer zu Siederdissen C, Hofacker IL., Bioinformatics 26(18), 2010
PMID: 20823307
Fine-tuning structural RNA alignments in the twilight zone.
Bremges A, Schirmer S, Giegerich R., BMC Bioinformatics 11(), 2010
PMID: 20433706
Faster computation of exact RNA shape probabilities.
Janssen S, Giegerich R., Bioinformatics 26(5), 2010
PMID: 20080511
On quantitative effects of RNA shape abstraction.
Nebel ME, Scheid A., Theory Biosci. 128(4), 2009
PMID: 19756808
Stochastic sampling of the RNA structural alignment space.
Harmanci AO, Sharma G, Mathews DH., Nucleic Acids Res. 37(12), 2009
PMID: 19429694
An analysis of structural influences on selection in RNA genes.
Mimouni NK, Lyngso RB, Griffiths-Jones S, Hein J., Mol. Biol. Evol. 26(1), 2009
PMID: 18948299
RNAspa: a shortest path approach for comparative prediction of the secondary structure of ncRNA molecules.
Horesh Y, Doniger T, Michaeli S, Unger R., BMC Bioinformatics 8(), 2007
PMID: 17908318
Structural analysis of aligned RNAs.
Voss B., Nucleic Acids Res. 34(19), 2006
PMID: 17020924
Versatile and declarative dynamic programming using pair algebras.
Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 16156887

24 References

Data provided by Europe PubMed Central.

Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure.
Mathews DH, Sabina J, Zuker M, Turner DH., J. Mol. Biol. 288(5), 1999
PMID: 10329189
RNA secondary structure: a complete mathematical analysis
Waterman, Mathematical Biosciences 42(3-4), 1978
Rfam: an RNA family database.
Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR., Nucleic Acids Res. 31(1), 2003
PMID: 12520045
Conserved RNA secondary structures in Picornaviridae genomes.
Witwer C, Rauscher S, Hofacker IL, Stadler PF., Nucleic Acids Res. 29(24), 2001
PMID: 11812840
Finding the most significant common sequence and structure motifs in a set of RNA sequences.
Gorodkin J, Heyer LJ, Stormo GD., Nucleic Acids Res. 25(18), 1997
PMID: 9278497
5S ribosomal RNA database Y2K.
Szymanski M, Barciszewska MZ, Barciszewski J, Erdmann VA., Nucleic Acids Res. 28(1), 2000
PMID: 10592212
An extensive class of small RNAs in Caenorhabditis elegans.
Lee RC, Ambros V., Science 294(5543), 2001
PMID: 11679672
Secondary structure prediction for aligned RNA sequences.
Hofacker IL, Fekete M, Stadler PF., J. Mol. Biol. 319(5), 2002
PMID: 12079347
Neuronal untranslated BC1 RNA: targeted gene elimination in mice.
Skryabin BV, Sukonina V, Jordan U, Lewejohann L, Sachser N, Muslimov I, Tiedge H, Brosius J., Mol. Cell. Biol. 23(18), 2003
PMID: 12944471
On the computational complexity of 2-interval pattern matching problems,
Vialette, Theoretical Computer Science 312(2-3), 2004
Identification of virus-encoded microRNAs.
Pfeffer S, Zavolan M, Grasser FA, Chien M, Russo JJ, Ju J, John B, Enright AJ, Marks D, Sander C, Tuschl T., Science 304(5671), 2004
PMID: 15118162
Pure multiple RNA secondary structure alignments: a progressive profile approach.
Hochsmann M, Voss B, Giegerich R., IEEE/ACM Trans Comput Biol Bioinform 1(1), 2004
PMID: 17048408
Abstract shapes of RNA.
Giegerich R, Voss B, Rehmsmeier M., Nucleic Acids Res. 32(16), 2004
PMID: 15371549
A comprehensive comparison of comparative RNA structure prediction approaches.
Gardner PP, Giegerich R., BMC Bioinformatics 5(), 2004
PMID: 15458580
Fast folding and comparison of RNA secondary structures
Hofacker, Monatshefte für Chemie Chemical Monthly 125(2), 1994
Algorithms for Loop Matchings
Nussinov, SIAM Journal on Applied Mathematics 35(1), 1978
Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
Sankoff, SIAM Journal on Applied Mathematics 45(5), 1985

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 16020472
PubMed | Europe PMC

Search this title in

Google Scholar