Landscapes on Spaces of Trees

TBI-Preprint 01-01-006

Titel:
Landscapes on Spaces of Trees

Author(s):
Oliver Bastert, Dan Rockmore, Peter F. Stadler, Gottfried Tinhofer

Abstract:
Combinatorial optimization problems defined on sets of phylogenetic trees are an important issue in computational biology, for instance the problem of reconstruction a phylogeny using maximum likelihood or parsimony approaches. The collection of possible phylogenetic trees is arranged as a so-called Robinson graph by means of the nearest neighborhood interchange move. The coherent algebra and spectra of Robinson graphs are discussed in some detail as their knowledge is important for an understanding of the landscape structure. We consider simple model landscapes as well as landscapes arising from the maximum parsimony problem, focusing on two complementary measures of ruggedness: the amplitude spectrum arising from projecting the cost functions onto the eigenspaces of the underlying graph and the topology of local minima and their connecting saddle points.

Keywords: Fitness landscapes, phylogenetic trees, spectral graph theory, parsimony problem
MSC: 05C38, 05C85.

Return to 2001 working papers list.