540 SYSTEMATIC BIOLOGY VOL. 61 be accompanied by a critical assessment of conver- gence. Arguably, the best way of accomplishing this is to compare samples obtained from independent MCMC analyses. It is typically the tree samples that are most divergent in phylogenetic analyses, and we therefore introduced the average standard deviation of split frequencies (ASDSF) in MrBayes to allow quantitative assessment of the similarity among such samples. ASDSF is calculated by comparing split or clade fre- quencies across multiple independent MCMC runs that ideally should be started from different randomly cho- sen starting trees (Lakner et al. 2008). ASDSF should approach 0.0 as runs converge to the same distribution. The frequencies of rare splits or clades are difficult to estimate accurately and these groupings are usually of marginal interest. Therefore, it may be advantageous to exclude them from the diagnostic. MrBayes allows the user to set a cutoff frequency (default value 0.10); all splits or clades occurring minimally at that frequency in at least one of the runs will be incorporated in the ASDSF. To allow users to monitor MCMC progress, MrBayes can run several analyses in parallel and report the av- erage (ASDSF) or maximum standard deviation of split frequencies at regular intervals. More detailed diag- nostics can be obtained using the “sump” and “sumt” commands after the run has completed. They include ASDSF across runs for each of the sampled clades in addition to the potential scale reduction factor (PSRF; Gelman and Rubin 1992) for branch lengths, node times, and substitution model parameters. PSRF compares the variance within and between runs and should approach 1.0 as runs converge. MrBayes 3.2 also reports the ef- fective sample size, widely used for single-run conver- gence diagnostics. MrBayes 3.2 also introduces several new features intended to improve MCMC convergence rates. A number of new tree proposal mechanisms have been added, including subtree-swapping moves and extend- ing subtree-pruning-and-regrafting moves, and the de- fault mix of proposals has been optimized (Lakner et al. 2008). MrBayes 3.2 further includes a completely new type of tree proposal that is guided using parsimony scores. The details of the parsimony- biased proposals will be presented elsewhere; how- ever, tentative empirical results show that they can improve the speed of convergence by an order of magnitude on some problems (see also Ho¨ hna and Drummond 2012). For nontree proposals, MrBayes 3.2 implements auto-tuning that automatically adjusts tun- ing parameters such that a target acceptance frequency is reached (Roberts and Rosenthal 2009). Since previ- ous versions, MrBayes supports Metropolis coupling (heated chains) to accelerate convergence. To sim- plify monitoring of convergence, MrBayes 3.2 prints ASDSF values, acceptance rates of moves, and ac- ceptance rates of swaps between Metropolis-coupled chains to a separate file with a “.mcmc” suffix during runs. Faster and More Convenient Computation Much of the computational effort in a phylogenetic MCMC analysis is spent calculating likelihoods. To improve speed, MrBayes 3.2 now employs streaming single-instruction-multiple-data extensions (SSE) for all likelihood calculations. SSE instructions are supported by most current CPUs and provide low-level paralleliza- tion of arithmetic operations. Importantly, MrBayes 3.2 also supports the use of the BEAGLE library for likeli- hood calculations (Ayres et al. 2012). With BEAGLE, the likelihood calculations can be farmed out to one or more graphics processing units (GPUs) on compatible hard- ware, resulting in significant speedups for codon and amino acid models in particular. BEAGLE can also be used for likelihood computation on the CPU. MrBayes 3.2 does not support multithreading, but it does implement the message passing interface (MPI) for efficient parallel processing across large computer clus- ters (Altekar et al. 2004). On many hardware platforms, including Mac OS and Linux, it is possible to use the MPI-enabled Unix version of MrBayes to take advan- tage of multiple cores. However, MPI parallelization is across chains, which means that the maximum number of cores or processors that can be used by MrBayes is the same as the total number of heated and nonheated chains across all simultaneous runs. For instance, two runs of four chains each would be maximally acceler- ated on a system with eight processors or cores. The MPI version can be combined with BEAGLE to further ex- pand the opportunity for computational parallelization. Finally, to facilitate long runs, MrBayes 3.2 imple- ments checkpointing across all models. At a frequency determined by the user, all parameter samples are printed to a “.ckp” file. If desired, the analysis can later be restarted from the checkpoint file, and the final re- sults will appear as if the run had never been stopped. New Models Many phylogenetic hypotheses concern the structure of the phylogenetic tree. To facilitate such analyses, MrBayes 3.2 implements three types of constraints on the tree: hard, negative, and partial. A hard constraint forces a split or clade to be present in all trees sampled in the MCMC analysis, whereas a negative constraint forces a split or clade to be absent. Unlike hard and negative constraints, a partial constraint (or backbone constraint) can leave the position of some taxa indeter- minate. The indeterminate taxa are allowed to appear on either side of the specified split if the tree is unrooted, or either within or outside the specified clade if the tree is rooted. Several hard, negative, and partial constraints can be combined into complicated priors on the shape of the tree. However, constraints are either on or off; they cannot be associated with probabilities in the cur- rent version. Unlike previous versions, MrBayes 3.2 supports re- laxed clock models and dating. Three different relaxed clock models are available: the Compound Poisson