Download:
[PostScript]
[PDF]
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.