Cédric Saule ; Mireille Regnier ; Jean-Marc Steyaert ; Alain Denise - Counting RNA pseudoknotted structures (extended abstract)

dmtcs:2834 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) - https://doi.org/10.46298/dmtcs.2834
Counting RNA pseudoknotted structures (extended abstract)Article

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

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


Volume: DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: bioinformatics,RNA structures,pseudoknots,enumeration,bijective combinatorics,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 315 times.
This article's PDF has been downloaded 337 times.