Bayesian Inference in Phylogeny - The LOCAL Algorithm of Larget and Simon

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:

Read more about this topic:  Bayesian Inference In Phylogeny

Famous quotes containing the words simon and/or local:

    Food=joy ... guilt ... anger ... pain ... nurturing ... friendship ... hatred ... the way you look and feel.... Food=everything you can imagine.
    Susan Powter, U.S. talk-show host. Food, p. 15, Simon & Schuster (1995)

    While it may not heighten our sympathy, wit widens our horizons by its flashes, revealing remote hidden affiliations and drawing laughter from far afield; humor, in contrast, strikes up fellow feeling, and though it does not leap so much across time and space, enriches our insight into the universal in familiar things, lending it a local habitation and a name.
    —Marie Collins Swabey. Comic Laughter, ch. 5, Yale University Press (1961)