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:
“The improved American highway system ... isolated the American-in-transit. On his speedway ... he had no contact with the towns which he by-passed. If he stopped for food or gas, he was served no local fare or local fuel, but had one of Howard Johnson’s nationally branded ice cream flavors, and so many gallons of Exxon. This vast ocean of superhighways was nearly as free of culture as the sea traversed by the Mayflower Pilgrims.”
—Daniel J. Boorstin (b. 1914)
“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)