DOI: 10.1093/bioinformatics/btq014. Faster computation of exact RNA shape probabilities

Faster computation of exact RNA shape probabilities

10.1093/bioinformatics/btq014

Crossref journal-article

Oxford University Press (OUP)

Bioinformatics (286)

Abstract

Abstract Motivation: Abstract shape analysis allows efficient computation of a representative sample of low-energy foldings of an RNA molecule. More comprehensive information is obtained by computing shape probabilities, accumulating the Boltzmann probabilities of all structures within each abstract shape. Such information is superior to free energies because it is independent of sequence length and base composition. However, up to this point, computation of shape probabilities evaluates all shapes simultaneously and comes with a computation cost which is exponential in the length of the sequence. Results: We device an approach called RapidShapes that computes the shapes above a specified probability threshold T by generating a list of promising shapes and constructing specialized folding programs for each shape to compute its share of Boltzmann probability. This aims at a heuristic improvement of runtime, while still computing exact probability values. Conclusion: Evaluating this approach and several substrategies, we find that only a small proportion of shapes have to be actually computed. For an RNA sequence of length 400, this leads, depending on the threshold, to a 10–138 fold speed-up compared with the previous complete method. Thus, probabilistic shape analysis has become feasible in medium-scale applications, such as the screening of RNA transcripts in a bacterial genome. Availability: RapidShapes is available via http://bibiserv.cebitec.uni-bielefeld.de/rnashapes Contact: robert@techfak.uni-bielefeld.de Supplementary information: Supplementary data are available at Bioinformatics online.

Bibliography

Janssen, S., & Giegerich, R. (2010). Faster computation of exact RNA shape probabilities. Bioinformatics, 26(5), 632â639.

Authors 2

Stefan Janssen (first)
Robert Giegerich (additional)

References 32 Referenced 18

10.1093/bioinformatics/btm223 / Bioinformatics / Efficient parameter estimation for RNA secondary structure prediction by Andronescu (2007)
10.1101/gr.5159906 / Genome Res. / Many novel mammalian microRNA candidates identified by extensive cloning and RAKE analysis by Berezikov (2006)
10.1186/1471-2105-9-474 / BMC Bioinformatics / RNAalifold: improved consensus structure prediction for RNA alignments by Bernhart (2008)
10.1016/j.jcss.2007.03.011 / J. Comput. Syst. Sci. / The most probable annotation problem in HMMs and its application to bioinformatics by Brejová (2007)
10.1073/pnas.0712329105 / Proc. Natl Acad. Sci. USA / Centroid estimation in discrete high-dimensional spaces with applications in biology by Carvalho (2008)
10.1093/bioinformatics/bti632 / Bioinformatics / Structure clustering features on the Sfold Web server by Chan (2005)
10.1261/rna.7220505 / RNA / Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency by Clote (2005)
10.1093/nar/gkg938 / Nucleic Acids Res. / A statistical sampling algorithm for RNA secondary structure prediction by Ding (2003)
10.1093/bioinformatics/btl246 / Bioinformatics / CONTRAfold: RNA secondary structure prediction without physics-based models by Do (2006)
10.1186/1471-2105-5-105 / BMC Bioinformatics / Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for RNA secondary structure prediction by Doshi (2004)
{'key': '2023012511004116100_B11', 'volume-title': 'Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids', 'author': 'Durbin', 'year': '1999'} / Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids by Durbin (1999)
10.1016/j.scico.2003.12.005 / Sci. Comp. Program. / A discipline of dynamic programming over sequence data by Giegerich (2004)
10.1093/nar/gkh779 / Nucleic Acids Res. / Abstract Shapes of RNA by Giegerich (2004)
10.1093/nar/gki081 / Nucleic Acids Res. / Rfam: annotating non-coding RNAs in complete genomes by Griffiths-Jones (2005)
10.1093/bioinformatics/btn601 / Bioinformatics / Prediction of RNA secondary structure using generalized centroid estimators by Hamada (2009)
10.1371/journal.pcbi.0030193 / PLoS Comput. Biol. / Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix by Havgaard (2007)
10.1007/BF00818163 / Monatsh. Chem. / Fast folding and comparison of RNA secondary structures by Hofacker (1994)
10.1186/1471-2105-9-131 / BMC Bioinformatics / Shape based indexing for faster search of RNA family databases by Janssen (2008)
10.1089/cmb.2006.0153 / J. Comput. Biol. / Asymptotics of RNA shapes by Lorenz (2008)
10.1038/ng.73 / Nat. Genet. / The birth and death of microRNA genes in Drosophila by Lu (2008)
10.1038/nrm1403 / Nat. Rev. Mol. Cell Biol. / Gene regulation by riboswitches by Mandal (2004)
10.1006/jmbi.1999.2700 / J. Mol. Biol. / Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure by Mathews (1999)
10.1016/j.sbi.2006.05.010 / Curr. Opin. Struct. Biol. / Prediction of RNA secondary structure by free energy minimization by Mathews (2006)
10.1002/bip.360290621 / Biopolymers / The equilibrium partition function and base pair binding probabilities for RNA secondary structure by McCaskill (1990)
10.1186/1471-2199-5-10 / BMC Mol. Biol. / Co-transcriptional folding is encoded within RNA genes by Meyer (2004)
10.1007/s12064-009-0074-z / Theory Biosci. / On quantitative effects of RNA shape abstraction by Nebel (2009)
10.1093/bioinformatics/btm179 / Bioinformatics / Locomotif: from graphical motif description to RNA motif search by Reeder (2007)
10.1093/bioinformatics/bti577 / Bioinformatics / Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction by Reeder (2005)
10.1093/bioinformatics/btk010 / Bioinformatics / RNAshapes: an integrated RNA analysis package based on abstract shapes by Steffen (2006)
10.1186/1741-7007-4-5 / BMC Biol. / Complete probabilistic analysis of RNA shapes by Voß (2006)
10.4161/rna.6.4.9014 / RNA Biol. / The Escherichia coli ibpA thermometer is comprised of stable and unstable structural elements by Waldminghaus (2009)
10.1002/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G / Biopolymers / Complete suboptimal folding of RNA and the stability of secondary structures by Wuchty (1999)

Dates

Type	When
Created	15 years, 7 months ago (Jan. 15, 2010, 8:14 p.m.)
Deposited	2 years, 7 months ago (Jan. 25, 2023, 6:03 a.m.)
Indexed	1 year, 3 months ago (May 23, 2024, 5:57 a.m.)
Issued	15 years, 7 months ago (Jan. 14, 2010)
Published	15 years, 7 months ago (Jan. 14, 2010)
Published Online	15 years, 7 months ago (Jan. 14, 2010)
Published Print	15 years, 5 months ago (March 1, 2010)

Funders 0

None

BibTeX

@article{Janssen_2010, title={Faster computation of exact RNA shape probabilities}, volume={26}, ISSN={1367-4803}, url={http://dx.doi.org/10.1093/bioinformatics/btq014}, DOI={10.1093/bioinformatics/btq014}, number={5}, journal={Bioinformatics}, publisher={Oxford University Press (OUP)}, author={Janssen, Stefan and Giegerich, Robert}, year={2010}, month=jan, pages={632–639} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2024,
        5,
        23
      ]
    ],
    "date-time": "2024-05-23T09:57:48Z",
    "timestamp": 1716458268190
  },
  "reference-count": 32,
  "publisher": "Oxford University Press (OUP)",
  "issue": "5",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2016,
            10,
            2
          ]
        ],
        "date-time": "2016-10-02T00:00:00Z",
        "timestamp": 1475366400000
      },
      "content-version": "vor",
      "delay-in-days": 2453,
      "URL": "http://creativecommons.org/licenses/by-nc/2.0/uk/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2010,
        3,
        1
      ]
    ]
  },
  "abstract": "<jats:title>Abstract</jats:title>\n               <jats:p>Motivation: Abstract shape analysis allows efficient computation of a representative sample of low-energy foldings of an RNA molecule. More comprehensive information is obtained by computing shape probabilities, accumulating the Boltzmann probabilities of all structures within each abstract shape. Such information is superior to free energies because it is independent of sequence length and base composition. However, up to this point, computation of shape probabilities evaluates all shapes simultaneously and comes with a computation cost which is exponential in the length of the sequence.</jats:p>\n               <jats:p>Results: We device an approach called RapidShapes that computes the shapes above a specified probability threshold T by generating a list of promising shapes and constructing specialized folding programs for each shape to compute its share of Boltzmann probability. This aims at a heuristic improvement of runtime, while still computing exact probability values.</jats:p>\n               <jats:p>Conclusion: Evaluating this approach and several substrategies, we find that only a small proportion of shapes have to be actually computed. For an RNA sequence of length 400, this leads, depending on the threshold, to a 10\u2013138 fold speed-up compared with the previous complete method. Thus, probabilistic shape analysis has become feasible in medium-scale applications, such as the screening of RNA transcripts in a bacterial genome.</jats:p>\n               <jats:p>Availability: \u00a0RapidShapes is available via http://bibiserv.cebitec.uni-bielefeld.de/rnashapes</jats:p>\n               <jats:p>Contact: \u00a0robert@techfak.uni-bielefeld.de</jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.</jats:p>",
  "DOI": "10.1093/bioinformatics/btq014",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2010,
        1,
        16
      ]
    ],
    "date-time": "2010-01-16T01:14:00Z",
    "timestamp": 1263604440000
  },
  "page": "632-639",
  "source": "Crossref",
  "is-referenced-by-count": 18,
  "title": "Faster computation of exact RNA shape probabilities",
  "prefix": "10.1093",
  "volume": "26",
  "author": [
    {
      "given": "Stefan",
      "family": "Janssen",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Practical Computer Science, Faculty of Technology, Bielefeld University, D-33615 Bielefeld, Germany"
        }
      ]
    },
    {
      "given": "Robert",
      "family": "Giegerich",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Practical Computer Science, Faculty of Technology, Bielefeld University, D-33615 Bielefeld, Germany"
        }
      ]
    }
  ],
  "member": "286",
  "published-online": {
    "date-parts": [
      [
        2010,
        1,
        14
      ]
    ]
  },
  "reference": [
    {
      "key": "2023012511004116100_B1",
      "doi-asserted-by": "crossref",
      "first-page": "i19",
      "DOI": "10.1093/bioinformatics/btm223",
      "article-title": "Efficient parameter estimation for RNA secondary structure prediction",
      "volume": "23",
      "author": "Andronescu",
      "year": "2007",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B2",
      "doi-asserted-by": "crossref",
      "first-page": "1289",
      "DOI": "10.1101/gr.5159906",
      "article-title": "Many novel mammalian microRNA candidates identified by extensive cloning and RAKE analysis",
      "volume": "16",
      "author": "Berezikov",
      "year": "2006",
      "journal-title": "Genome Res."
    },
    {
      "key": "2023012511004116100_B3",
      "doi-asserted-by": "crossref",
      "first-page": "474",
      "DOI": "10.1186/1471-2105-9-474",
      "article-title": "RNAalifold: improved consensus structure prediction for RNA alignments",
      "volume": "9",
      "author": "Bernhart",
      "year": "2008",
      "journal-title": "BMC Bioinformatics"
    },
    {
      "key": "2023012511004116100_B4",
      "doi-asserted-by": "crossref",
      "first-page": "1060",
      "DOI": "10.1016/j.jcss.2007.03.011",
      "article-title": "The most probable annotation problem in HMMs and its application to bioinformatics",
      "volume": "73",
      "author": "Brejov\u00e1",
      "year": "2007",
      "journal-title": "J. Comput. Syst. Sci."
    },
    {
      "key": "2023012511004116100_B5",
      "doi-asserted-by": "crossref",
      "first-page": "3209",
      "DOI": "10.1073/pnas.0712329105",
      "article-title": "Centroid estimation in discrete high-dimensional spaces with applications in biology",
      "volume": "105",
      "author": "Carvalho",
      "year": "2008",
      "journal-title": "Proc. Natl Acad. Sci. USA"
    },
    {
      "key": "2023012511004116100_B6",
      "doi-asserted-by": "crossref",
      "first-page": "3926",
      "DOI": "10.1093/bioinformatics/bti632",
      "article-title": "Structure clustering features on the Sfold Web server",
      "volume": "21",
      "author": "Chan",
      "year": "2005",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B7",
      "doi-asserted-by": "crossref",
      "first-page": "578",
      "DOI": "10.1261/rna.7220505",
      "article-title": "Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency",
      "volume": "11",
      "author": "Clote",
      "year": "2005",
      "journal-title": "RNA"
    },
    {
      "key": "2023012511004116100_B8",
      "doi-asserted-by": "crossref",
      "first-page": "7280",
      "DOI": "10.1093/nar/gkg938",
      "article-title": "A statistical sampling algorithm for RNA secondary structure prediction",
      "volume": "31",
      "author": "Ding",
      "year": "2003",
      "journal-title": "Nucleic Acids Res."
    },
    {
      "key": "2023012511004116100_B9",
      "doi-asserted-by": "crossref",
      "first-page": "e90",
      "DOI": "10.1093/bioinformatics/btl246",
      "article-title": "CONTRAfold: RNA secondary structure prediction without physics-based models",
      "volume": "22",
      "author": "Do",
      "year": "2006",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B10",
      "doi-asserted-by": "crossref",
      "first-page": "105",
      "DOI": "10.1186/1471-2105-5-105",
      "article-title": "Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for RNA secondary structure prediction",
      "volume": "5",
      "author": "Doshi",
      "year": "2004",
      "journal-title": "BMC Bioinformatics"
    },
    {
      "key": "2023012511004116100_B11",
      "volume-title": "Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids",
      "author": "Durbin",
      "year": "1999"
    },
    {
      "key": "2023012511004116100_B12",
      "doi-asserted-by": "crossref",
      "first-page": "215",
      "DOI": "10.1016/j.scico.2003.12.005",
      "article-title": "A discipline of dynamic programming over sequence data",
      "volume": "51",
      "author": "Giegerich",
      "year": "2004",
      "journal-title": "Sci. Comp. Program."
    },
    {
      "key": "2023012511004116100_B13",
      "doi-asserted-by": "crossref",
      "first-page": "4843",
      "DOI": "10.1093/nar/gkh779",
      "article-title": "Abstract Shapes of RNA",
      "volume": "32",
      "author": "Giegerich",
      "year": "2004",
      "journal-title": "Nucleic Acids Res."
    },
    {
      "key": "2023012511004116100_B14",
      "doi-asserted-by": "crossref",
      "first-page": "D121",
      "DOI": "10.1093/nar/gki081",
      "article-title": "Rfam: annotating non-coding RNAs in complete genomes",
      "volume": "33",
      "author": "Griffiths-Jones",
      "year": "2005",
      "journal-title": "Nucleic Acids Res."
    },
    {
      "key": "2023012511004116100_B15",
      "doi-asserted-by": "crossref",
      "first-page": "465",
      "DOI": "10.1093/bioinformatics/btn601",
      "article-title": "Prediction of RNA secondary structure using generalized centroid estimators",
      "volume": "25",
      "author": "Hamada",
      "year": "2009",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B16",
      "doi-asserted-by": "crossref",
      "first-page": "1896",
      "DOI": "10.1371/journal.pcbi.0030193",
      "article-title": "Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix",
      "volume": "3",
      "author": "Havgaard",
      "year": "2007",
      "journal-title": "PLoS Comput. Biol."
    },
    {
      "key": "2023012511004116100_B17",
      "doi-asserted-by": "crossref",
      "first-page": "167",
      "DOI": "10.1007/BF00818163",
      "article-title": "Fast folding and comparison of RNA secondary structures",
      "volume": "125",
      "author": "Hofacker",
      "year": "1994",
      "journal-title": "Monatsh. Chem."
    },
    {
      "key": "2023012511004116100_B18",
      "doi-asserted-by": "crossref",
      "first-page": "131",
      "DOI": "10.1186/1471-2105-9-131",
      "article-title": "Shape based indexing for faster search of RNA family databases",
      "volume": "9",
      "author": "Janssen",
      "year": "2008",
      "journal-title": "BMC Bioinformatics"
    },
    {
      "key": "2023012511004116100_B19",
      "doi-asserted-by": "crossref",
      "first-page": "31",
      "DOI": "10.1089/cmb.2006.0153",
      "article-title": "Asymptotics of RNA shapes",
      "volume": "15",
      "author": "Lorenz",
      "year": "2008",
      "journal-title": "J. Comput. Biol."
    },
    {
      "key": "2023012511004116100_B20",
      "doi-asserted-by": "crossref",
      "first-page": "351",
      "DOI": "10.1038/ng.73",
      "article-title": "The birth and death of microRNA genes in Drosophila",
      "volume": "40",
      "author": "Lu",
      "year": "2008",
      "journal-title": "Nat. Genet."
    },
    {
      "key": "2023012511004116100_B21",
      "doi-asserted-by": "crossref",
      "first-page": "451",
      "DOI": "10.1038/nrm1403",
      "article-title": "Gene regulation by riboswitches",
      "volume": "5",
      "author": "Mandal",
      "year": "2004",
      "journal-title": "Nat. Rev. Mol. Cell Biol."
    },
    {
      "key": "2023012511004116100_B22",
      "doi-asserted-by": "crossref",
      "first-page": "911",
      "DOI": "10.1006/jmbi.1999.2700",
      "article-title": "Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure",
      "volume": "288",
      "author": "Mathews",
      "year": "1999",
      "journal-title": "J. Mol. Biol."
    },
    {
      "key": "2023012511004116100_B23",
      "doi-asserted-by": "crossref",
      "first-page": "270",
      "DOI": "10.1016/j.sbi.2006.05.010",
      "article-title": "Prediction of RNA secondary structure by free energy minimization",
      "volume": "16",
      "author": "Mathews",
      "year": "2006",
      "journal-title": "Curr. Opin. Struct. Biol."
    },
    {
      "key": "2023012511004116100_B24",
      "doi-asserted-by": "crossref",
      "first-page": "1105",
      "DOI": "10.1002/bip.360290621",
      "article-title": "The equilibrium partition function and base pair binding probabilities for RNA secondary structure",
      "volume": "29",
      "author": "McCaskill",
      "year": "1990",
      "journal-title": "Biopolymers"
    },
    {
      "key": "2023012511004116100_B25",
      "doi-asserted-by": "crossref",
      "first-page": "10",
      "DOI": "10.1186/1471-2199-5-10",
      "article-title": "Co-transcriptional folding is encoded within RNA genes",
      "volume": "5",
      "author": "Meyer",
      "year": "2004",
      "journal-title": "BMC Mol. Biol."
    },
    {
      "key": "2023012511004116100_B26",
      "doi-asserted-by": "crossref",
      "first-page": "211",
      "DOI": "10.1007/s12064-009-0074-z",
      "article-title": "On quantitative effects of RNA shape abstraction",
      "volume": "128",
      "author": "Nebel",
      "year": "2009",
      "journal-title": "Theory Biosci."
    },
    {
      "key": "2023012511004116100_B27",
      "doi-asserted-by": "crossref",
      "first-page": "i392",
      "DOI": "10.1093/bioinformatics/btm179",
      "article-title": "Locomotif: from graphical motif description to RNA motif search",
      "volume": "23",
      "author": "Reeder",
      "year": "2007",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B28",
      "doi-asserted-by": "crossref",
      "first-page": "3516",
      "DOI": "10.1093/bioinformatics/bti577",
      "article-title": "Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction",
      "volume": "21",
      "author": "Reeder",
      "year": "2005",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B29",
      "doi-asserted-by": "crossref",
      "first-page": "500",
      "DOI": "10.1093/bioinformatics/btk010",
      "article-title": "RNAshapes: an integrated RNA analysis package based on abstract shapes",
      "volume": "22",
      "author": "Steffen",
      "year": "2006",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2023012511004116100_B30",
      "doi-asserted-by": "crossref",
      "first-page": "5",
      "DOI": "10.1186/1741-7007-4-5",
      "article-title": "Complete probabilistic analysis of RNA shapes",
      "volume": "4",
      "author": "Vo\u00df",
      "year": "2006",
      "journal-title": "BMC Biol."
    },
    {
      "key": "2023012511004116100_B31",
      "doi-asserted-by": "crossref",
      "DOI": "10.4161/rna.6.4.9014",
      "article-title": "The Escherichia coli ibpA thermometer is comprised of stable and unstable structural elements",
      "volume": "6",
      "author": "Waldminghaus",
      "year": "2009",
      "journal-title": "RNA Biol."
    },
    {
      "key": "2023012511004116100_B32",
      "doi-asserted-by": "crossref",
      "first-page": "145",
      "DOI": "10.1002/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G",
      "article-title": "Complete suboptimal folding of RNA and the stability of secondary structures",
      "volume": "49",
      "author": "Wuchty",
      "year": "1999",
      "journal-title": "Biopolymers"
    }
  ],
  "container-title": "Bioinformatics",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://academic.oup.com/bioinformatics/article-pdf/26/5/632/48860643/bioinformatics_26_5_632.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "syndication"
    },
    {
      "URL": "https://academic.oup.com/bioinformatics/article-pdf/26/5/632/48860643/bioinformatics_26_5_632.pdf",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2023,
        1,
        25
      ]
    ],
    "date-time": "2023-01-25T11:03:21Z",
    "timestamp": 1674644601000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://academic.oup.com/bioinformatics/article/26/5/632/212857"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2010,
        1,
        14
      ]
    ]
  },
  "references-count": 32,
  "journal-issue": {
    "issue": "5",
    "published-print": {
      "date-parts": [
        [
          2010,
          3,
          1
        ]
      ]
    }
  },
  "URL": "http://dx.doi.org/10.1093/bioinformatics/btq014",
  "relation": {},
  "ISSN": [
    "1367-4811",
    "1367-4803"
  ],
  "subject": [],
  "published-other": {
    "date-parts": [
      [
        2010,
        3,
        1
      ]
    ]
  },
  "published": {
    "date-parts": [
      [
        2010,
        1,
        14
      ]
    ]
  }
}