  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.
