Hierarchical Analysis of RNA Secondary Structures with Pseudoknots Based on Sections

Abstract

Predicting RNA structures containing pseudoknots remains computationally challenging due to high processing costs and complexity. While standard methods for pseudoknot prediction require O(N6) time complexity, we present a hierarchical approach that significantly reduces computational cost while maintaining prediction accuracy. Our method analyzes RNA structures by dividing them into contiguous regions of unpaired bases derived from known secondary structures ("sections"). We examine pseudoknot interactions between sections using a nearest-neighbor energy model and dynamic programming. The algorithm scales as O(n2{ell}4), offering substantial computational advantages over existing global prediction methods. Our analysis of 726 transfer messenger RNA and 455 Ribonuclease P RNA sequences reveals that biologically relevant pseudoknots are highly concentrated among section pairs with large minimum free energy gains. Over 90% of connected section pairs appear within just the top 3% of section pairs ranked by MFE gain. For 2-clusters, our method achieves high prediction accuracy with sensitivity exceeding 0.90 and positive predictive value above 0.80. For 3-clusters, we discovered asymmetric behavior where "former" section pairs (formed early in the sequence) predict accurately, while "latter" section pairs show different formation patterns. The hierarchical section-based approach demonstrates that local energy considerations can effectively predict pseudoknot formations between unpaired regions. Our work provides strong evidence for the effectiveness of local energy calculations in pseudoknot prediction and offers insights into the dynamic processes governing RNA structure formation.