Perturbing trees for improved searches

1. Perturbing the search space is a powerful search strategy. The fundamental concept is to modify the cost of the trees in such a way that we can find even better trees from already good ones, that is, from trees that are local optima. The perturb command in POY implements this kind of search strategy.

2. perturb works in the following way: for iterations, POY perturbs the characters using the arguments and options that we specify, searches for optimal trees in the altered character landscape, and finally searches the current best tree using the original characters.

3. The parsimony Ratchet is a classic powerful perturbation strategy in phylogenetic research. In POY, the ratchet argument within the perturb command works by up-weighting a percentage of characters. The default settings of perturb () performs a ratchet in which 25% of the characters are up-weighted by a factor of 2.

4. Let us now perturb our data with the ratchet. First, we will read the data, and the trees stored in the fuse tutorial, to perturb them:

               read ("course.fasta", "fuse_course.tree")
               perturb ()
   

5. How many iterations are performed by default? How many characters do you have in your analysis?

6. As you saw in the previous command, one problem we have is that the ratchet works on characters, and this data set has few of them: only 8. Our experience is that an excellent strategy is to apply the ratchet on the characters produced by the implied alignment, that is, on the static approximation.

7. To do this, we use the transform command as an argument of the perturb command:

               perturb (transform (static_approx))
   

   which executes the following algorithm:
   • For iterations
     • Run the parsimony ratchet
     • Transform back to the original dynamic homology characters
     • Run a new search in the resulting tree
     • If the new tree is better, replace the original.

8. Now lets perform a ratchet with SPR and static approximation:

               perturb (transform (static_approx), swap (spr))
   

9. Alternatively, we can try to escape the local optima by perturbing the cost of the matrix employed by the dynamic homology characters:

               perturb (transform (tcm:(1,1)))
   

   Can you describe what this command does? An important observation is that running five iterations of this command does not help at all. Can you see why?