Mathematics – Combinatorics
Scientific paper
2011-12-31
Mathematics
Combinatorics
27 pages, 12 figures
Scientific paper
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, $\Lambda^*$, 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 $\Lambda^*$-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 $\Lambda^*$-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).
Huang Fenix W. D.
Reidys Christian M.
No associations
LandOfFree
On the combinatorics of sparsification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the combinatorics of sparsification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the combinatorics of sparsification will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-231084