Hide and vanish: data sets where the most parsimonious tree is known but hard to find, and their implications for tree search methods

GOLOBOFF, PABLO

MOLECULAR PHYLOGENETICS AND EVOLUTION

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2014 vol. 79 p. 118 - 131

1055-7903

Three different types of data sets, for which the uniquely most parsimonious tree can be known exactlybut is hard to find with heuristic tree search methods, are studied. Tree searches are complicated more bythe shape of the tree landscape (i.e. the distribution of homoplasy on different trees) than by the sheerabundance of homoplasy or character conflict. Data sets of Type 1 are those constructed by Radel et al.(2013). Data sets of Type 2 present a very rugged landscape, with narrow peaks and valleys, but relativelylow amounts of homoplasy. For such a tree landscape, subjecting the trees to TBR and saving suboptimaltrees produces much better results when the sequence of clipping for the tree branches is randomizedinstead of fixed. An unexpected finding for data sets of Types 1 and 2 is that starting a search from a random tree instead of a random addition sequence Wagner tree may increase the probability that thesearch finds the most parsimonious tree; a small artificial example where these probabilities can be calculated exactly is presented. Data sets of Type 3, the most difficult data sets studied here, comprise onlycongruent characters, and a single island with only one most parsimonious tree. Even if there is a singleisland, missing entries create a very flat landscape which is difficult to traverse with tree search algorithms because the number of equally parsimonious trees that need to be saved and swapped to effectively move around the plateaus is too large. Minor modifications of the parameters of tree drifting,ratchet, and sectorial searches allow travelling around these plateaus much more efficiently than savingand swapping large numbers of equally parsimonious trees with TBR. For these data sets, two new relatedcriteria for selecting taxon addition sequences in Wagner trees (the ??selected?? and ??informative?? additionsequences) produce much better results than the standard random or closest addition sequences. Thesenew methods for Wagner trees and for moving around plateaus can be useful when analyzing phylogenomic data sets formed by concatenation of genes with uneven taxon representation (??sparse?? supermatrices), which are likely to present a tree landscape with extensive plateaus.