Ergodic - any tree topology can be transformed into any other tree topology

SimulFold: Simultaneously Inferring RNA

Structures Including Pseudoknots, Alignments,

and Trees Using a Bayesian MCMC Framework

Irmtraud M. Meyer1,2*, Istvan Miklos3,4,5

PLoS Computational Biology  August 2007 | Volume 3 | Issue 8 | e149

To summarize, all of the existing RNA structure prediction
programs face at least one of the following challenges: (1) the
MFE structure rather than the evolutionarily conserved
structure that is likely to correspond to the functional
structure is predicted, (2) unstructured regions of the RNA
are not explicitly modeled, (3) input alignments are fixed and
cannot be altered and improved, (4) pseudoknotted struc-
tures are either completely ignored or computationally too
expensive to predict, (5) only two evolutionarily related RNA
sequences are used as input, or (6) the evolutionary relation-
ship between the RNA sequences is not explicitly modeled.

The idea of co-estimating RNA secondary structures,
multiple sequence alignments, and evolutionary trees was
first suggested in a theory paper by David Sankoff in 1985
[50].


We introduce a joint distribution of RNA
structures, alignments, and trees in a Bayesian framework. As
it is not feasible to analytically calculate any interesting
statistics in this model in reasonable computational time, we
propose a Markov chain Monte Carlo (MCMC) method with
which we can sample from the posterior distribution.

For changing the topology of the tree, we pick a tree node at
random and swap this node and its aunt node to alter its
topology (see Figure 2). These moves have been shown [68,71]
to be ergodic, i.e., any tree topology can be transformed into
any other tree topology using these moves.