On simulated annealing phase transitions in phylogeny reconstruction

Maximilian A.R. Strobl, Daniel Barker

Research output: Contribution to journalArticlepeer-review

Abstract

Phylogeny reconstruction with global criteria is NP-complete or NP-hard, hence in general requires a heuristic search. We investigate the powerful, physically inspired, general-purpose heuristic simulated annealing, applied to phylogeny reconstruction. Simulated annealing mimics the physical process of annealing, where a liquid is gently cooled to form a crystal. During the search, periods of elevated specific heat occur, analogous to physical phase transitions. These simulated annealing phase transitions play a crucial role in the outcome of the search. Nevertheless, they have received comparably little attention, for phylogeny or other optimisation problems. We analyse simulated annealing phase transitions during searches for the optimal phylogenetic tree for 34 real-world multiple alignments. In the same way in which melting temperatures differ between materials we observe distinct specific heat profiles for each input file. We propose this reflects differences in the search landscape and can serve as a measure for problem difficulty and for suitability of the algorithm’s parameters. We discuss application in algorithmic optimisation and as a diagnostic to assess parameterisation before computationally costly, large phylogeny reconstructions are launched. While the focus here lies on phylogeny reconstruction under maximum parsimony, it is plausible that our results are more widely applicable to optimisation procedures in science and industry.
Original languageEnglish
Pages (from-to)46–55
JournalMolecular phylogenetics and evolution
Volume101
Early online date2 May 2016
DOIs
Publication statusPublished - Aug 2016

Keywords

  • phylogeny
  • optimisation
  • heuristic methods
  • simulated annealing
  • phase transition
  • search landscape

Fingerprint

Dive into the research topics of 'On simulated annealing phase transitions in phylogeny reconstruction'. Together they form a unique fingerprint.

Cite this