Interesting phylogenetic search heuristics


#1

I thought it would be fun to have a discussion about interesting optimization heuristics for phylogenetic inference. Please post to contribute! Here’s one from the parsimony literature:

The Parsimony Ratchet Nixon, Cladistics 1999; PDF.

  1. Generate a starting tree (e.g., a “Wagner” tree followed by some level of branch swapping or not)
  2. Randomly select a subset of characters, each of which is given additional weight (e.g., add 1 to the weight of each selected character).
  3. Perform branch swapping (e.g., “branch-breaking” or TBR) on the current tree using the reweighted matrix, keeping only one (or a few) trees.
  4. Set all weights for the characters to the “original” weights (typically, equal weights).
  5. Perform branch swapping (e.g., branch-breaking or TBR) on the current tree (from step 3) keeping one (or a few) trees.
  6. Return to step 2. Steps 2–6 are considered to be one iteration, and typically, 50–200 or more iterations are performed. The number of characters to be sampled for reweighting in step 2 is determined by the user; I have found that between 5 and 25% of the characters provide good results in most cases.

In this context, a “weight” is a per-column multiplier of the parsimony score used in the grand parsimony total.

I think this one is interesting, and I don’t know of anything like it being used in the likelihood literature. Does anyone else? Seems to me that the closest would be a love child between heated chains and the bootstrap.


#2

@rutgeraldo has his “Likeihood Ratchet”, but I don’t know where it might be implemented.


#3

Pretty neat!


#4

Here’s a new one from @Alexis_RAxML & co:

It’s related to some ideas I presented in a talk at Evolution 2013 and which we’re finally getting around to writing up.