MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space.

Since its introduction in 2001, MrBayes has grown in popularity as a software package for Bayesian phylogenetic inference using Markov chain Monte Carlo (MCMC) methods. With this note, we announce the release of version 3.2, a major upgrade to the latest official release presented in 2003. The new version provides convergence diagnostics and allows multiple analyses to be run in parallel with convergence progress monitored on the fly. The introduction of new proposals and automatic optimization of tuning parameters has improved convergence for many problems. The new version also sports significantly faster likelihood calculations through streaming single-instruction-multiple-data extensions (SSE) and support of the BEAGLE library, allowing likelihood calculations to be delegated to graphics processing units (GPUs) on compatible hardware. Speedup factors range from around 2 with SSE code to more than 50 with BEAGLE for codon problems. Checkpointing across all models allows long runs to be completed even when an analysis is prematurely terminated. New models include relaxed clocks, dating, model averaging across time-reversible substitution models, and support for hard, negative, and partial (backbone) tree constraints. Inference of species trees from gene trees is supported by full incorporation of the Bayesian estimation of species trees (BEST) algorithms. Marginal model likelihoods for Bayes factor tests can be estimated accurately across the entire model space using the stepping stone method. The new version provides more output options than previously, including samples of ancestral states, site rates, site d(N)/d(S) rations, branch rates, and node dates. A wide range of statistics on tree parameters can also be output for visualization in FigTree and compatible software.

A SAT-based algorithm for finding attractors in synchronous Boolean networks.

This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

Compositional properties of random Boolean networks.

Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with n vertices has up to 2(n) states. Therefore, for large n , computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network's dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from O (2(n)) to O (2(l)), where l is the number of relevant vertices in the largest component.