Combinatorics of RNA Secondary Structures with Base Triples

Research output: Contribution to journalResearch articleContributedpeer-review


  • Robert Müller - , University of Kaiserslautern-Landau (Author)
  • Markus Nebel - (Author)


The structure of RNA has been the subject of intense research over the last decades due to its importance for the correct functioning of RNA molecules in biological processes. Hence, a large number of models for RNA folding and corresponding algorithms for structure prediction have been developed. However, previous models often only consider base pairs, although every base is capable of up to three edge-to-edge interactions with other bases. Recently, Höner zu Siederdissen et al. presented an extended model of RNA secondary structure, including base triples together with a folding algorithm—the first thermodynamics-based algorithm that allows the prediction of secondary structures with base triples. In this article, we investigate the search space processed by this new algorithm, that is, the combinatorics of extended RNA secondary structures with base triples. We present generalized definitions for structural motifs like hairpins, stems, bulges, or interior loops occurring in structures with base triples. Furthermore, we prove precise asymptotic results for the number of different structures (size of search space) and expectations for various parameters associated with structural motifs (typical shape of folding). Our analysis shows that the asymptotic number of secondary structures of size n increases exponentially to compared to the classic model by Stein and Waterman for which structures exist. A comparison with the classic model reveals large deviations in the expected structural appearance, too. The inclusion of base triples constitutes a significant refinement of the combinatorial model of RNA secondary structure, which, by our findings, is quantitatively characterized. Our results are of special theoretical interest, because a closer look at the numbers involved suggests that extended RNA secondary structures constitute a new combinatorial class not bijective with any other combinatorial objects studied so far.


Original languageEnglish
Pages (from-to)619-648
Number of pages30
JournalJournal of Computational Biology
Issue number7
Publication statusPublished - 2015
Externally publishedYes

External IDs

Scopus 84937001067