Ab initio Prediction of RNA Nucleotide Interactions with Backbone k-Tree Model
Preprint
Abstract
Given the importance of non-coding RNAs to cellular regulatory functions and rapid growth of RNA transcripts, computational prediction of RNA tertiary structure remains highly demanded yet significantly challenging. Even for a short RNA sequence, the space of tertiary conformations is immense; existing methods to identify native-like conformations mostly resort to random sampling of conformations to gain computational feasibility. However native conformations may not be examined and prediction accuracy may be compromised due to sampling. In particular, the state-of-the-art methods have yet to deliver the desired prediction performance for RNAs of length beyond 50. This paper presents the work to tackle a key step in the RNA tertiary structure prediction problem, the prediction of the nucleotide interactions that constitute the desired tertiary structure. The research is established upon a novel graph model, called backbone k-tree, to markably constrain nucleotide interaction relationships in RNA tertiary structure. It is shown that the new model makes it possible to efficiently predict the optimal set of nucleotide interactions from the query sequence, including the interactions in all recently revealed families. Evident by the preliminary results, the new method can predict with a high accuracy the nucleotide interactions that constitute the tertiary structure of the query sequence, thus providing a viable solution towards ab initio prediction of RNA tertiary structure.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Treewidth computations I. Upper boundsInformation and Computation, 2010
- Atomic accuracy in predicting and designing noncanonical RNA structureNature Methods, 2010
- RNA2D3D: A program for Generating, Viewing, and Comparing 3-Dimensional Models of RNAJournal of Biomolecular Structure and Dynamics, 2008
- The MC-Fold and MC-Sym pipeline infers RNA structure from sequence dataNature, 2008
- Automated de novo prediction of native-like RNA tertiary structuresProceedings of the National Academy of Sciences, 2007
- FR3D: finding local and composite recurrent structural motifs in RNA 3D structuresJournal of Mathematical Biology, 2007
- Quantitative analysis of nucleic acid three-dimensional structuresJournal of Molecular Biology, 2001
- Geometric nomenclature and classification of RNA base pairsRNA, 2001
- Forbidden minors characterization of partial 3-treesDiscrete Mathematics, 1990
- Linear time algorithms for NP-hard problems restricted to partial k-treesDiscrete Applied Mathematics, 1989