title: Characterizing Local Optima for Maximum Parsimony.
abstract: Finding the best phylogenetic tree under the maximum parsimony optimality criterion is computationally difficult. We quantify the occurrence of such optima for well-behaved sets of data. When nearest neighbor interchange operations are used, multiple local optima can occur even for "perfect" sequence data, which results in hill-climbing searches that never reach a global optimum. In contrast, we show that when neighbors are defined via the subtree prune and regraft metric, there is a single local optimum for perfect sequence data, and thus, every such search finds a global optimum quickly. We further characterize conditions for which sequences simulated under the Cavender-Farris-Neyman and Jukes-Cantor models of evolution yield well-behaved search spaces.
authors.affiliation: Departments of Mathematics and Chemistry, Johns Hopkins University, Baltimore, MD, USA.
authors.forename: Ellen
authors.initials: E
authors.lastname: Urheim
authors.affiliation: Department of Computer Science, Graduate Center, City University of New York, New York, NY, USA.|Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, NY, USA.|Invertebrate Zoology, American Museum of Natural History, New York, NY, USA.
authors.forename: Eric
authors.initials: E
authors.lastname: Ford
authors.affiliation: Department of Computer Science, Graduate Center, City University of New York, New York, NY, USA. stjohn@lehman.cuny.edu.|Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, NY, USA. stjohn@lehman.cuny.edu.|Invertebrate Zoology, American Museum of Natural History, New York, NY, USA. stjohn@lehman.cuny.edu.
authors.forename: Katherine
authors.identifier: 0000-0002-7140-2432
authors.initials: K
authors.lastname: St John
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D019143:Evolution, Molecular; D016013:Likelihood Functions; D055641:Mathematical Concepts; D008957:Models, Genetic; D010802:Phylogeny; D012440:Saccharomyces / Q000145:classification / Q000235:genetics
keywords: Attraction basins; Compatibility; Maximum parsimony; Phylogenetic islands; Tree searching