Contact:[email protected] It has come to our attention that several concepts and results underlying the gfold software presented in our article ‘Topology and prediction of RNA pseudoknots’ (Reidys et al., 2011) are also present in earlier work by Bon et al. (2008); Orland and Zee (2002); Pillsbury et al. (2005b); Vernizzi et al. (2005) and (Pillsbury et al., 2005a). Here, we briefly examine these works in relation to the results of our paper. The classification and expansion of pseudoknotted RNA structures in terms of the topological genus of an associated fatgraph or double line graph were first proposed by Orland and Zee (2002) and Bon et al. (2008), although fatgraphs were applied to RNA secondary structures already by Penner and Waterman (1993) and Penner (2004). The enumerative results initiated by Orland and Zee (2002) are based on matrix models, while our generating functions are derived via representation theory Zagier (1995). Enumeration results on RNA structures according to genus were already obtained by Vernizzi et al. (2005), again using the formal framework of the matrix model. Genus as well as other topological invariants of fatgraphs were introduced and studied as descriptors of proteins in Penner et al. (2010). Pillsbury et al. (2005a) report recursion relations of time complexity O(N6) to generate RNA structures of genus one in the context of an RNA folding algorithm that is substantially different from our algorithm gfold. Aside from not incorporating loop-based energy models, gfold is not restricted to genus one RNA structures. The four basic irreducible shadows of genus one in Theorem 2.3 of our paper appeared first in Pillsbury et al. (2005b; Bon et al. (2008). The shadows of Reidys et al. (2011) are derived from (i) the notion of irreducibility formulated by Kleitman (1970) and (ii) the work on pseudoknot shapes by Jin and Reidys (2009; Reidys and Wang (2010). Irreducibility is equivalent to the concept of primitivity introduced by Bon et al. (2008), inspired by the work of Dyson (1949). The equation to compute the genus of a fatgraph is classical going back to Euler (1752) and was first applied in the context representing RNA structures by Orland and Zee (2002) and Bon et al. (2008). Additivity of genus under topological sums is elementary (Massey, 1967) and for reducible and nested RNA structures first discussed by Bon et al. (2008). Our Equations (2.1), (2.2) and (2.4) are thus textbook knowledge. Lemma 2.1 is also well known and was used e.g. by Penner and Waterman (1993) and Bon et al. (2008). Funding: 973 Project of the Ministry of Science and Technology; the PCSIRT Project of the Ministry of Education; National Science Foundation of China to CMR and his lab, as well as the Deutsche Forschungsgemeinschaft, projects STA 850/2-1 & STA 850/7-1; the European Union FP-7 project QUANTOMICS (no. 222664) to P.F.S. and his lab. J.E.A. and R.C.P. are supported by QGM, the Centre for Quantum Geometry of Moduli Spaces, funded by the Danish National Research Foundation. Conflict of Interest: none declared.

MOTIVATION: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered. RESULTS: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10-20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed. AVAILABILITY: The source code of gfold is freely available at http://www.combinatorics.cn/cbpc/gfold.tar.gz. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.