Joint stochastic sampling for RNA secondary structure prediction

We present a novel method for prediction of common structures and alignment for two homologous RNA sequences. The method, termed joint sampling, is based on sampling from the structural alignment space of the sequences, i.e. the space of joint representations of common secondary structures and sequence alignments of the sequences. The structural alignment space is efficiently sampled by probabilistically generating structural alignments from building blocks termed structural alignment atoms. Structure and alignment predictions are obtained by clustering the samples of structures and alignments. The experimental results show that joint sampling offers improvements in structure prediction over a sampling method that generates structures from Boltzmann ensemble of single RNA sequence. In addition, the joint sampling offers more accurate estimate of alignment as compared to estimates from a hidden Markov model.