Landscapes on Spaces of Trees

Oliver Bastert, Dan Rockmore, Peter F. Stadler and Gottfried Tinhofer

Working Papers from Santa Fe Institute

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.

Date: 2001-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:01-01-006

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().