2011/12/31 by Fenix W. D. Huang, Huang, Fenix W. D., Christian M. Reidys +1
Biochemistry, Genetics and Molecular Biology · #32Q55 #Bacterial Genetics and Biotechnology #Combinatorics (math.CO) #FOS: Mathematics #RNA and protein synthesis mechanisms #RNA modifications and cancer
paper · pdf · doi:10.48550/arxiv.1201.0308
openalex publication_date 2011/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Background: We study the sparsification of dynamic programming folding algorithms of RNA structures. Sparsification applies to the mfe-folding of RNA structures and can lead to a significant reduction of time complexity. Results: We analyze the sparsification of a particular decomposition rule, Λ^*, that splits an interval for RNA secondary and pseudoknot structures of fixed topological genus. Essential for quantifying the sparsification is the size of its so called candidate set. We present a combinatorial framework which allows by means of probabilities of irreducible substructures to obtain the expected size of the set of Λ^*-candidates. We compute these expectations for arc-based energy models via energy-filtered generating functions (GF) for RNA secondary structures as well as RNA pseudoknot structures. For RNA secondary structures we also consider a simplified loop-energy model. This combinatorial analysis is then compared to the expected number of Λ^*-candidates obtained from folding mfe-structures. In case of the mfe-folding of RNA secondary structures with a simplified loop energy model our results imply that sparsification provides a reduction of time complexity by a constant factor of 91% (theory) versus a 96% reduction (experiment). For the "full" loop-energy model there is a reduction of 98% (experiment).