© Copyright 2000, 2001, Donald Simon & Bret Larget, Department of Mathematics and Computer Science, Duquesne University.

Larget, B. and D. Simon (1999).
Markov chain Monte Carlo algorithms
for the Bayesian analysis of phylogenetic trees.
*Molecular Biology and Evolution* **16**:750-759.

GLOBAL with a molecular clock does these steps:

- Choose a tree representation at random by choosing a left/right orientation for the subtrees at each internal node with equal probability.
- Perturb each valley depth independently by a small uniform amount, reflecting excess back into range if a depth would rise above the leaf level.
- Evaluate the resultant tree and accept or reject by Metropolis-Hastings.

- Choose to reroot with probability
*p*or update tree otherwise. - If reroot tree,
- Choose a point in the unrooted tree for the new root uniformly at random.

- Otherwise
- Perturb each valley depth (two for each valley) independently by a small uniform amount, reflecting excess back into range if a depth becomes negative.
- Evaluate the resultant tree and accept or reject by Metropolis-Hastings.

- Pick uniformly at random an internal branch of the tree.
- If this branch does not adjoin the root:
- Define the local neighborhood to be the two nodes of the selected branch,
*u*and*v*, and nodes adjacent to these. The children of*u*are*a*and*b*, the children of*v*are*u*and*c*, and*v*'s parent is*w*. - The heights of
*a*,*b*, and*c*above*w*are sorted and labeled*h*<_{1}*h*<_{2}*h*._{3} - Choose two positions above
*w*independently, one uniformly at random between 0 and*h*and the other uniformly at random between 0 and_{1}*h*. If the option_{2}`use-beta`

is true, these two positions are selected according to a scaled Beta distribution whose mean is the current position. - The position farther from
*w*is the proposed position of*u*. The position closer to*w*is the proposed position of*v*. - If the proposed position of
*u*is a distance less than*h*from_{1}*w*:- Randomly choose one of the three children nodes to connect to
*v*and connect the others to*u*.

- Randomly choose one of the three children nodes to connect to
- Otherwise the tree topology is forced and the lowest child is connected to
*v*.

- Define the local neighborhood to be the two nodes of the selected branch,
- Else, if the randomly chosen branch does adjoin the root:
- Define the local neighborhood to be the two nodes of the selected branch,
*u*and*v*where*v*is the root of the tree and nodes adjacent to these. The children of*u*are*a*and*b*, and the children of*v*are*u*and*c*. - The heights of
*a*,*b*, and*c*above*v*are sorted and labeled*h*<_{1}*h*<_{2}*h*._{3} - The proposed distance between the root
*v*and the nearest child among*a*,*b*, and*c*is a random multiple of*h*._{1} - The proposed location of
*u*is a height above the proposed location of*v*chosen randomly between 0 and*h*. If_{2}`use-beta`

is true, the location is selected according to a scaled Beta distribution with mean at the current location. - If the proposed position of
*u*is closer to the proposed location of*v*- Randomly choose one of the three children nodes to connect to
*v*and connect the others to*u*.

- Randomly choose one of the three children nodes to connect to
- Otherwise the tree topology is forced and the lowest child is connected to
*v*.

- Define the local neighborhood to be the two nodes of the selected branch,
- Accept or reject the tree by Metropolis-Hastings.

- Pick uniformly at random an edge of the unrooted tree.
- Define the local neighborhood to be the two nodes of the selected branch,
*u*and*v*, and nodes adjacent to these. The neighbors of*u*are randomly labeled*a*and*b*with equal probability and independently the neighbors of*v*are randomly labeled*c*and*d*with equal probability. - The length of the path from
*a*to*c*is multiplied by a random factor. - One node from
*u*and*v*is randomly chosen with equal probability and moved with its corresponding subtree to a location on the path from*a*to*c*chosen uniformly at random. - Accept or reject the tree by Metropolis-Hastings.

Unconstrained parameters kappa, ttp, and gamma are updated by adding a random uniform perturbation, reflecting the excess back into range should the proposed value become negative.

Parameters whose sum or weighted sum is fixed are proposed from a Dirichlet distribution with expected values at the current values.

Back to the table of contents.

This page was most recently updated on January 19, 2001.

bambe@mathcs.duq.edu