Reducing the search space in RNA helix based folding. European Conference on Computational Biology

RNA has many pivotal functions especially in the regulation of gene expression by ncRNAs. Identification of their structure is important for understanding their function and often requires a more in-depth analysis of the folding space. Here, the major drawback is the exponential growth of the folding space. Therefore, methods are either limited in the sequence length they can analyze or they make use of heuristics, sampling or abstraction.

With RNAHELICES1, we introduced a position-specific abstraction based on helices which we termed helix index shapes or hishapes for short. Based on this, we developed two methods, one for energy barrier estimation, called HIPATH, and one for abstract structure comparison, termed HITED. Furthermore, we could show the superior performance of HIPATH compared to other existing methods and the competitive accuracy of HITED.

Despite polynomial complexity when returning k-best hishapes, the number of possible hishapes is still exponential. This makes it necessary to reduce the number of hishape classes. By applying two rules (termed Nos and No+) that modify candidate selection during the recursive calculation in Dynamic Programming (DP), we investigate the search space prior to and following the application of both rules.