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 local and/or simon:
“Back now to autumn, leaving the ended husk
Of summer that brought them here for Show Saturday
The men with hunters, dog-breeding wool-defined women,
Children all saddle-swank, mugfaced middleaged wives
Glaring at jellies, husbands on leave from the garden
Watchful as weasels, car-tuning curt-haired sons
Back now, all of them, to their local lives....”
—Philip Larkin (1922–1986)
“Stevenson had noble ideas—as did the young Franklin for that matter. But Stevenson felt that the way to implement them was to present himself as a thoughtful idealist and wait for the world to flock to him. He considered it below him, or wrong, to scramble out among the people and ask them what they wanted. Roosevelt grappled voters to him. Stevenson shied off from them. Some thought him too pure to desire power, though he showed ambition when it mattered.”
—Garry Wills, U.S. historian. Certain Trumpets: The Call of Leaders, ch. 9, Simon & Schuster (1994)