Journal Article

Efficient Sampling of Parsimonious Inversion Histories with Application to Genome Rearrangement in <i>Yersinia</i>

István Miklós and Aaron E. Darling

in Genome Biology and Evolution

Published on behalf of Society for Molecular Biology and Evolution

Volume 1, issue , pages 153-164
Published in print January 2009 |
Published online June 2009 | e-ISSN: 1759-6653 | DOI:

More Like This

Show all results sharing these subjects:

  • Bioinformatics and Computational Biology
  • Evolutionary Biology
  • Genetics and Genomics


Show Summary Details


Inversions are among the most common mutations acting on the order and orientation of genes in a genome, and polynomial-time algorithms exist to obtain a minimal length series of inversions that transform one genome arrangement to another. However, the minimum length series of inversions (the optimal sorting path) is often not unique as many such optimal sorting paths exist. If we assume that all optimal sorting paths are equally likely, then statistical inference on genome arrangement history must account for all such sorting paths and not just a single estimate. No deterministic polynomial algorithm is known to count the number of optimal sorting paths nor sample from the uniform distribution of optimal sorting paths.

Here, we propose a stochastic method that uniformly samples the set of all optimal sorting paths. Our method uses a novel formulation of parallel Markov chain Monte Carlo. In practice, our method can quickly estimate the total number of optimal sorting paths. We introduce a variant of our approach in which short inversions are modeled to be more likely, and we show how the method can be used to estimate the distribution of inversion lengths and breakpoint usage in pathogenic Yersinia pestis.

The proposed method has been implemented in a program called “MC4Inversion.” We draw comparison of MC4Inversion to the sampler implemented in BADGER and a previously described importance sampling (IS) technique. We find that on high-divergence data sets, MC4Inversion finds more optimal sorting paths per second than BADGER and the IS technique and simultaneously avoids bias inherent in the IS technique.

Keywords: genome rearrangement; MCMC; Yersinia; inversion

Journal Article.  9353 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology ; Evolutionary Biology ; Genetics and Genomics

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.