Constrained Secondary Structure Prediction Using Stem Detection

Abstract

RNA sequence analysis and structure prediction are classical topics of computational biology and a powerful tool to examine complex genomic data. Over the decades, various tools have been developed to predict RNA secondary structures and sequence alignments, a majority of which utilize one of the two characteristic approaches: (a) thermodynamic minimum free energy or (b) probabilistic maximum likelihood prediction. However, despite numerous takes on modeling these approaches, the computational complexity of the developed algorithms hasn’t seen significant improvements. Most algorithms still operate with a polynomial time complexity of O(N3?). This cost is significantly large while processing large RNA sequences with hundreds of bases. In this thesis, a constrained structure prediction algorithm is presented that aims to diminish the computational overhead of traditional RNA structure prediction methods to O(N?2). The proposed algorithm employs pattern recognition methods to devise rules for constructing a confined space of possible secondary structures. This confined structure space is then searched to find a secondary structure that satisfies the optimality criterion. Through this document, we present the design details of the proposed algorithm implemented using the minimum free energy (MFE) model. Later, we compare its performance to Zuker’s algorithm which is the conventional dynamic programming equivalent of the MFE model. The proposed algorithm provides a significant reduction in CPU time to process longer sequences which can be attributed to its lower computational complexity.