title: On simulated annealing phase transitions in phylogeny reconstruction.
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. Whilst 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.
authors.affiliation: School of Biology, University of St Andrews, St Andrews, Fife KY16 9TH, UK; School of Mathematics and Statistics, Mathematical Institute, North Haugh, St Andrews, Fife KY16 9SS, UK.
authors.forename: Maximilian A R
authors.initials: MAR
authors.lastname: Strobl
authors.affiliation: School of Biology, University of St Andrews, St Andrews, Fife KY16 9TH, UK. Electronic address: Daniel.Barker@ed.ac.uk.
authors.forename: Daniel
authors.initials: D
authors.lastname: Barker
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D044367:Phase Transition; D010802:Phylogeny; D013696:Temperature
keywords: Heuristic methods; Optimisation; Phase transition; Phylogeny; Search landscape; Simulated annealing