MCMC genome rearrangement.
BACKGROUND
As more and more genomes have been sequenced, genomic data is rapidly accumulating. Genome-wide mutations are believed more neutral than local mutations such as substitutions, insertions and deletions, therefore phylogenetic investigations based on inversions, transpositions and inverted transpositions are less biased by the hypothesis on neutral evolution. Although efficient algorithms exist for obtaining the inversion distance of two signed permutations, there is no reliable algorithm when both inversions and transpositions are considered. Moreover, different type of mutations happen with different rates, and it is not clear how to weight them in a distance based approach.


RESULTS
We introduce a Markov Chain Monte Carlo method to genome rearrangement based on a stochastic model of evolution, which can estimate the number of different evolutionary events needed to sort a signed permutation. The performance of the method was tested on simulated data, and the estimated numbers of different types of mutations were reliable. Human and Drosophila mitochondrial data were also analysed with the new method. The mixing time of the Markov Chain is short both in terms of CPU times and number of proposals.


BACKGROUND
The source code in C is available on request from the author.
Miklós
István
I
Department of Statistics, University of Oxford, Oxford, UK. miklos@stats.ox.ac.uk
D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D004252:DNA Mutational Analysis; D019143:Evolution, Molecular; D015321:Gene Rearrangement / Q000235:genetics*; D015810:Linkage Disequilibrium / Q000235:genetics*; D008390:Markov Chains; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009010:Monte Carlo Method; D009154:Mutation; D017422:Sequence Analysis, DNA / Q000379:methods*