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

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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Reeder, Jens; Giegerich, RobertUniBi
Abstract / Bemerkung
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.
Page URI


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, Jens, and Giegerich, Robert. 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.

52 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

The BRaliBase dent-a tale of benchmark design and interpretation.
Löwes B, Chauve C, Ponty Y, Giegerich R., Brief Bioinform 18(2), 2017
PMID: 26984616
Multiple sequence alignment modeling: methods and applications.
Chatzou M, Magis C, Chang JM, Kemena C, Bussotti G, Erb I, Notredame C., Brief Bioinform 17(6), 2016
PMID: 26615024
Bridging the gap between in vitro and in vivo RNA folding.
Leamy KA, Assmann SM, Mathews DH, Bevilacqua PC., Q Rev Biophys 49(), 2016
PMID: 27658939
Predicting RNA secondary structures from sequence and probing data.
Lorenz R, Wolfinger MT, Tanzer A, Hofacker IL., Methods 103(), 2016
PMID: 27064083
Studying RNA Homology and Conservation with Infernal: From Single Sequences to RNA Families.
Barquist L, Burge SW, Gardner PP., Curr Protoc Bioinformatics 54(), 2016
PMID: 27322404
Non-Coding RNAs in Lung Cancer: Contribution of Bioinformatics Analysis to the Development of Non-Invasive Diagnostic Tools.
Kunz M, Wolf B, Schulze H, Atlan D, Walles T, Walles H, Dandekar T., Genes (Basel) 8(1), 2016
PMID: 28035947
The RNA shapes studio.
Janssen S, Giegerich R., Bioinformatics 31(3), 2015
PMID: 25273103
Shape and secondary structure prediction for ncRNAs including pseudoknots based on linear SVM.
Achawanantakun R, Sun Y., BMC Bioinformatics 14 Suppl 2(), 2013
PMID: 23369147
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
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
Abstract folding space analysis based on helices.
Huang J, Backofen R, Voß B., RNA 18(12), 2012
PMID: 23104999
TurboFold: iterative probabilistic estimation of secondary structures for multiple RNA sequences.
Harmanci AO, Sharma G, Mathews DH., BMC Bioinformatics 12(), 2011
PMID: 21507242
Structator: fast index-based search for RNA sequence-structure patterns.
Meyer F, Kurtz S, Backofen R, Will S, Beckstette M., BMC Bioinformatics 12(), 2011
PMID: 21619640
Local absence of secondary structure permits translation of mRNAs that lack ribosome-binding sites.
Scharff LB, Childs L, Walther D, Bock R., PLoS Genet 7(6), 2011
PMID: 21731509
Conservation and Occurrence of Trans-Encoded sRNAs in the Rhizobiales.
Reinkensmeier J, Schlüter JP, Giegerich R, Becker A., Genes (Basel) 2(4), 2011
PMID: 24710299
Faster computation of exact RNA shape probabilities.
Janssen S, Giegerich R., Bioinformatics 26(5), 2010
PMID: 20080511
Fine-tuning structural RNA alignments in the twilight zone.
Bremges A, Schirmer S, Giegerich R., BMC Bioinformatics 11(), 2010
PMID: 20433706
Multi-objective pairwise RNA sequence alignment.
Taneda A., Bioinformatics 26(19), 2010
PMID: 20679330
Folding and finding RNA secondary structure.
Mathews DH, Moss WN, Turner DH., Cold Spring Harb Perspect Biol 2(12), 2010
PMID: 20685845
Discriminatory power of RNA family models.
Höner zu Siederdissen C, Hofacker IL., Bioinformatics 26(18), 2010
PMID: 20823307
An analysis of structural influences on selection in RNA genes.
Mimouni NK, Lyngsø RB, Griffiths-Jones S, Hein J., Mol Biol Evol 26(1), 2009
PMID: 18948299
RNA structure prediction from evolutionary patterns of nucleotide composition.
Smit S, Knight R, Heringa J., Nucleic Acids Res 37(5), 2009
PMID: 19129237
Stochastic sampling of the RNA structural alignment space.
Harmanci AO, Sharma G, Mathews DH., Nucleic Acids Res 37(12), 2009
PMID: 19429694
Simultaneous alignment and folding of 28S rRNA sequences uncovers phylogenetic signal in structure variation.
Letsch HO, Greve C, Kück P, Fleck G, Stocsits RR, Misof B., Mol Phylogenet Evol 53(3), 2009
PMID: 19654047
Accurate and efficient reconstruction of deep phylogenies from structured RNAs.
Stocsits RR, Letsch H, Hertel J, Misof B, Stadler PF., Nucleic Acids Res 37(18), 2009
PMID: 19723687
On quantitative effects of RNA shape abstraction.
Nebel ME, Scheid A., Theory Biosci 128(4), 2009
PMID: 19756808
From consensus structure prediction to RNA gene finding.
Bernhart SH, Hofacker IL., Brief Funct Genomic Proteomic 8(6), 2009
PMID: 19833701
Shape based indexing for faster search of RNA family databases.
Janssen S, Reeder J, Giegerich R., BMC Bioinformatics 9(), 2008
PMID: 18312625
WAR: Webserver for aligning structural RNAs.
Torarinsson E, Lindgreen S., Nucleic Acids Res 36(web server issue), 2008
PMID: 18492721
Analysis and classification of RNA tertiary structures.
Abraham M, Dror O, Nussinov R, Wolfson HJ., RNA 14(11), 2008
PMID: 18824509
RNAalifold: improved consensus structure prediction for RNA alignments.
Bernhart SH, Hofacker IL, Will S, Gruber AR, Stadler PF., BMC Bioinformatics 9(), 2008
PMID: 19014431
RNAs everywhere: genome-wide annotation of structured RNAs.
Athanasius F Bompfünewerer Consortium, Backofen R, Bernhart SH, Flamm C, Fried C, Fritzsch G, Hackermüller J, Hertel J, Hofacker IL, Missal K, Mosig A, Prohaska SJ, Rose D, Stadler PF, Tanzer A, Washietl S, Will S., J Exp Zool B Mol Dev Evol 308(1), 2007
PMID: 17171697
RNase MRP and the RNA processing cascade in the eukaryotic ancestor.
Woodhams MD, Stadler PF, Penny D, Collins LJ., BMC Evol Biol 7 Suppl 1(), 2007
PMID: 17288571
RNA localization signals: deciphering the message with bioinformatics.
Hamilton RS, Davis I., Semin Cell Dev Biol 18(2), 2007
PMID: 17452113
Multiple structural alignment and clustering of RNA sequences.
Torarinsson E, Havgaard JH, Gorodkin J., Bioinformatics 23(8), 2007
PMID: 17324941
Murlet: a practical multiple alignment tool for structural RNA sequences.
Kiryu H, Tabei Y, Kin T, Asai K., Bioinformatics 23(13), 2007
PMID: 17459961
RNA structure: bioinformatic analysis.
Jossinet F, Ludwig TE, Westhof E., Curr Opin Microbiol 10(3), 2007
PMID: 17548241
Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix.
Havgaard JH, Torarinsson E, Gorodkin J., PLoS Comput Biol 3(10), 2007
PMID: 17937495
Semiautomated improvement of RNA alignments.
Andersen ES, Lind-Thomsen A, Knudsen B, Kristensen SE, Havgaard JH, Torarinsson E, Larsen N, Zwieb C, Sestoft P, Kjems J, Gorodkin J., RNA 13(11), 2007
PMID: 17804647
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
MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing.
Lindgreen S, Gardner PP, Krogh A., Bioinformatics 23(24), 2007
PMID: 18006551
RNAshapes: an integrated RNA analysis package based on abstract shapes.
Steffen P, Voss B, Rehmsmeier M, Reeder J, Giegerich R., Bioinformatics 22(4), 2006
PMID: 16357029
Beyond Mfold: recent advances in RNA bioinformatics.
Reeder J, Höchsmann M, Rehmsmeier M, Voss B, Giegerich R., J Biotechnol 124(1), 2006
PMID: 16530285
Prediction of RNA secondary structure by free energy minimization.
Mathews DH, Turner DH., Curr Opin Struct Biol 16(3), 2006
PMID: 16713706
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

Daten bereitgestellt von Europe PubMed Central.

A comprehensive comparison of comparative RNA structure prediction approaches.
Gardner PP, Giegerich R., BMC Bioinformatics 5(), 2004
PMID: 15458580
Abstract shapes of RNA.
Giegerich R, Voss B, Rehmsmeier M., Nucleic Acids Res. 32(16), 2004
PMID: 15371549
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
Rfam: an RNA family database.
Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR., Nucleic Acids Res. 31(1), 2003
PMID: 12520045
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
Secondary structure prediction for aligned RNA sequences.
Hofacker IL, Fekete M, Stadler PF., J. Mol. Biol. 319(5), 2002
PMID: 12079347

An extensive class of small RNAs in Caenorhabditis elegans.
Lee RC, Ambros V., Science 294(5543), 2001
PMID: 11679672
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

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

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
5S ribosomal RNA database Y2K.
Szymanski M, Barciszewska MZ, Barciszewski J, Erdmann VA., Nucleic Acids Res. 28(1), 2000
PMID: 10592212


Conserved RNA secondary structures in Picornaviridae genomes.
Witwer C, Rauscher S, Hofacker IL, Stadler PF., Nucleic Acids Res. 29(24), 2001
PMID: 11812840

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

PMID: 16020472
PubMed | Europe PMC

Suchen in

Google Scholar