Bayesian inference in phylogeny generates a posterior distribution for a parameter (composed of a phylogenetic tree (its branch lengths and topology) and a model of evolution) based on the prior for that parameter and the likelihood of the data (generated by a multiple alignment). The Bayesian approach has become more popular due to advances in computational machinery, especially, Markov Chain Monte Carlo algorithms. Bayesian inference has a number of applications in molecular phylogenetics, for example, estimation of species phylogeny and species divergence times.

Basic Bayesian Theory

Recall that for Bayesian inference:

The denominator is the marginal probability of the data, averaged over all possible parameter values weighted by their prior distribution. Formally,

where is the parameter space for .

In the original Metropolis algorithm, given a current -value , and a new -value , the new value is accepted with probability:

The LOCAL algorithm of Larget and Simon

The LOCAL algorithm begins by selecting an internal branch of the tree at random. The nodes at the ends of this branch are each connected to two other branches. One of each pair is chosen at random. Imagine taking these three selected edges and stringing them like a clothesline from left to right, where the direction (left/right) is also selected at random. The two endpoints of the first branch selected will have a sub-tree hanging like a piece of clothing strung to the line. The algorithm proceeds by multiplying the three selected branches by a common random amount, akin to stretching or shrinking the clothesline. Finally the leftmost of the two hanging sub-trees is disconnected and reattached to the clothesline at a location selected uniformly at random. This is the candidate tree.

Suppose we began by selecting the internal branch with length $$ (in Figure (a) (to be added)) that separates taxa and from the rest. Suppose also that we have (randomly) selected branches with lengths and from each side, and that we oriented these branches as shown in Figure(b). Let , be the current length of the clothesline. We select the new length to be , where is a uniform random variable on . Then for the LOCAL algorithm, the acceptance probability can be computed to be:

Assessing Convergence

Suppose we want to estimate a branch length of a 2-taxon tree under JC, in which n₁ sites are unvaried and n₂ are variable. Assume exponential prior distribution with rate . The density is . The probabilities of the possible site patterns are:

for unvaried sites, and

Thus the unnormalized posterior distribution is:

or, alternately,

Update branch length by choosing new value uniformly at random from a window of half-width centered at the current value:

where is uniformly distributed between and . The acceptance probability is:

Example: , . We will compare results for two values of , and . In each case, we will begin with an initial length of and update the length times. (See Figure 3.2 (to be added) for results.)

Metropolis-coupled MCMC (Geyer)

If the target distribution has multiple peaks, separated by low valleys, the Markov chain may have difficulty in moving from one peak to another. As a result, the chain may get stuck on one peak and the resulting samples will not approximate the posterior density correctly. This is a serious practical concern for phylogeny reconstruction, as multiple local peaks are known to exist in the tree space during heuristic tree search under maximum parsimony (MP), maximum likelihood (ML), and minimum evolution (ME) criteria, and the same can be expected for stochastic tree search using MCMC. Many strategies have been proposed to improve mixing of Markov chains in presence of multiple local peaks in the posterior density. One of the most successful algorithms is the Metropolis-coupled MCMC (or ).

In this algorithm, $m$ chains are run in parallel, with different stationary distributions , $$, where the first one, is the target density, while , are chosen to improve mixing. For example, one can choose incremental heating of the form:

so that the first chain is the cold chain with the correct target density, while chains are heated chains. Note that raising the density π(.) to the power with has the effect of flattening out the distribution, similar to heating a metal. In such a distribution, it is easier to traverse between peaks (separated by valleys) than in the original distribution. After each iteration, a swap of states between two randomly chosen chains is proposed through a Metropolis-type step. Let be the current state in chain , . A swap between the states of chains and is accepted with probability:

At the end of the run, output from only the cold chain is used, while those from the hot chains are discarded. Heuristically, the hot chains will visit the local peaks rather easily, and swapping states between chains will let the cold chain occasionally jump valleys, leading to better mixing. However, if is unstable, proposed swaps will seldom be accepted. This is the reason for using several chains which differ only incrementally. (See Figure3.3 (to be added)).

An obvious disadvantage of the algorithm is that chains are run and only one chain is used for inference. For this reason, is ideally suited for implementation on parallel machines, since each chain will in general require the same amount of computation per iteration.

References

• Geyer, C.J. (1991) Markov chain Monte Carlo maximum likelihood. In Computing Science and Statistics: Proceedings of the 23rd Symposium of the Interface (ed. E.M. Keramidas), pp. 156-163. Interface Foundation, Fairfax Station, VA.
• Yang, Z. and B. Rannala. (1997) Bayesian phylogenetic inference using DNA sequences: A Markov chain Monte Carlo method. Molecular Biology and Evolution, 14, 717-724.
• Larget, B. and D.L. Simon. (1999) Markov chain Monte Carlo algorithms for the Bayesian analysis of phylogenetic trees. Molecular Biology and Evolution, 16, 750-759.
• Huelsenbeck, J.P. and F. Ronquist. (2001) MrBayes: Bayesian inference in phylogenetic trees. Bioinformatics, 17, 754-755.
• Ronquist, F. and J.P. Huelsenbeck. (2003) MrBayes3: Bayesian phylogenetic inference under mixed models. Bioinformatics, 19, 1572-1574.
• Rannala, B. and Z. Yang. (2003) Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci. Genetics, 164, 1645-1656.

This bioinformatics-related article is a stub. You can help Wikipedia by expanding it. In biology, phylogenetics (Greek: phylon = tribe, race and genetikos = relative to birth, from genesis = birth) is the study of evolutionary relatedness among various groups of organisms (e. ... Computational phylogenetics is the study of computational algorithms, methods and computer programs for use in phylogenetic analyses. ... Molecular phylogeny is the use of the structure of molecules to gain information on an organisms evolutionary relationships. ... This cladogram shows the relationship among various insect groups. ... Shared characteristics that define a cladistic grouping. ... It has been suggested that Evolutionary tree be merged into this article or section. ... A phylogenetic network is any graph used to visualize evolutionary relationships between species or organisms. ... Long branch attraction (LBA) is a phenomenon in phylogenetic analyses (most commonly those employing maximum parsimony) when rapidly evolving lineages are inferred to be closely related, regardless of their true evolutionary relationships. ... Maximum parsimony is a simple but popular technique used in cladistics to predict an accurate phylogenetic tree for a set of taxa (commonly a set of species or reproductively-isolated populations of a single species). ... Maximum likelihood estimation (MLE) is a popular statistical method used to make inferences about parameters of the underlying probability distribution of a given data set. ... In bioinformatics, neighbor-joining is a bottom-up clustering method used for the creation of phylogenetic trees. ... UPGMA (Unweighted Pair Group Method with Arithmetic mean) is a simple bottom-up data clustering method used in bioinformatics for the creation of phylogenetic trees. ... Types of Clade (Note: Stem-based is now branch-based, to avoid confusion with the term stem group which means total clade minus crown clade.) The PhyloCode is a developing draft for a formal set of rules governing phylogenetic nomenclature. ... DNA barcoding is a taxonomic method which uses a short genetic marker in an organisms mitochondrial DNA to quickly and easily identify it as belonging to a particular species. ... This is a list of topics in evolutionary biology and evolution. ... Map of the human X chromosome (from the NCBI website). ...