Authors: Cédric Saule ^1,2; Mireille Regnier ^3,4; Jean-Marc Steyaert ^5,6; Alain Denise ^7,8,6

• 1 Laboratoire de Recherche en Informatique
• 2 Inria Saclay - Ile de France
• 3 Algorithms and Models for Integrative Biology [LIX]
• 4 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
• 5 Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
• 6 Algorithms and Models for Integrative Biology
• 7 Laboratoire de Recherche en Informatique
• 8 Institut de génétique et microbiologie [Orsay]

In 2004, Condon and coauthors gave a hierarchical classification of exact RNA structure prediction algorithms according to the generality of structure classes that they handle. We complete this classification by adding two recent prediction algorithms. More importantly, we precisely quantify the hierarchy by giving closed or asymptotic formulas for the theoretical number of structures of given size n in all the classes but one. This allows to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms. \par