Improved gibbs sampling for detecting mosaic structures in DNA sequence alignments

A recently proposed method for detecting mosaic structures in DNA sequence alignments is based on the combination of hidden Markov models (HMMs) with phylo- genetic trees. Inference is done in a Bayesian way by sampling the model parameters and hidden state sequences from the posterior distribution with Markov chain Monte Carlo (MCMC). In an earlier method, proposed in [1], this was effected with a nested Gibbs-within-Gibbs scheme. The present article discusses a modification of the MCMC sampling method, based on a modification of the standard forward-backward algorithm and an unnested Gibbs sampling procedure. We have tested the modified algorithm on various synthetic and real-world DNA sequence alignments, where we have observed a significant improvement in the mixing and convergence of the Markov chain. As a practical consequence, the computational costs are substantially reduced, and the predictions become more reliable