MOTIVATION: The combinatorial sequential Monte Carlo (CSMC) has been demonstrated to be an efficient complementary method to the standard Markov chain Monte Carlo (MCMC) for Bayesian phylogenetic tree inference using biological sequences. It is appealing to combine the CSMC and MCMC in the framework of the particle Gibbs (PG) sampler to jointly estimate the phylogenetic trees and evolutionary parameters. However, the Markov chain of the PG may mix poorly for high dimensional problems (e.g. phylogenetic trees). Some remedies, including the PG with ancestor sampling and the interacting particle MCMC, have been proposed to improve the PG. But they either cannot be applied to or remain inefficient for the combinatorial tree space. RESULTS: We introduce a novel CSMC method by proposing a more efficient proposal distribution. It also can be combined into the PG sampler framework to infer parameters in the evolutionary model. The new algorithm can be easily parallelized by allocating samples over different computing cores. We validate that the developed CSMC can sample trees more efficiently in various PG samplers via numerical experiments. AVAILABILITY AND IMPLEMENTATION: The implementation of our method and the data underlying this article are available at https://github.com/liangliangwangsfu/phyloPMCMC. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: For families, kinship coefficients are quantifications of the amount of genetic sharing between a pair of individuals. These coefficients are critical for understanding the breeding habits and genetic diversity of diploid populations. Historically, computations of the inbreeding coefficient were used to prohibit inbred marriages and prohibit breeding of some pairs of pedigree animals. Such prohibitions foster genetic diversity and help prevent recessive Mendelian disease at a population level. RESULTS: This paper gives the fastest known algorithms for computing the kinship coefficient of a set of individuals with a known pedigree, especially for large pedigrees. These algorithms outperform existing methods. In addition, the algorithms given here consider the possibility that the founders of the known pedigree may themselves be inbred and compute the appropriate inbreeding-adjusted kinship coefficients, which has not been addressed in literature. The exact kinship algorithm has running-time O(n2) for an n-individual pedigree. The recursive-cut exact kinship algorithm has running time O(s2m) where s is the number of individuals in the largest segment of the pedigree and m is the number of cuts. The approximate algorithm has running-time O(nd) for an n-individual pedigree on which to estimate the kinship coefficients of n individuals of interest from n founder kinship coefficients and d is the number of samples. AVAILABILITY AND IMPLEMENTATION: The above polynomial-time exact algorithm and the linear-time approximation algorithms are implemented as PedKin in C++ and are available under the GNU GPL v2.0 open source license. The PedKin source code is available at: http://www.intrepidnetcomputing.com/research/code/.

Many problems of practical interest rely on Continuous-time Markov chains (CTMCs) defined over combinatorial state spaces, rendering the computation of transition probabilities, and hence probabilistic inference, difficult or impossible with existing methods. For problems with countably infinite states, where classical methods such as matrix exponentiation are not applicable, the main alternative has been particle Markov chain Monte Carlo methods imputing both the holding times and sequences of visited states. We propose a particle-based Monte Carlo approach where the holding times are marginalized analytically. We demonstrate that in a range of realistic inferential setups, our scheme dramatically reduces the variance of the Monte Carlo approximation and yields more accurate parameter posterior approximations given a fixed computational budget. These experiments are performed on both synthetic and real datasets, drawing from two important examples of CTMCs having combinatorial state spaces: string-valued mutation models in phylogenetics and nucleic acid folding pathways.

We propose a novel method for scalable parallelization of SMC algorithms, Entangled Monte Carlo simulation (EMC). EMC avoids the transmission of particles between nodes, and instead reconstructs them from the particle genealogy. In particular, we show that we can reduce the communication to the particle weights for each machine while efficiently maintaining implicit global coherence of the parallel simulation. We explain methods to efficiently maintain a genealogy of particles from which any particle can be reconstructed. We demonstrate using examples from Bayesian phylogenetic that the computational gain from parallelization using EMC significantly outweighs the cost of particle reconstruction. The timing experiments show that reconstruction of particles is indeed much more efficient as compared to transmission of particles.