Format

Send to

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 2008 Jul-Aug;15(6):577-91. doi: 10.1089/cmb.2008.0068.

An exact algorithm for the geodesic distance between phylogenetic trees.

Author information

  • 1Center for Integrative Bioinformatics Vienna, Max F. Perutz Laboratories, University of Vienna, Medical University of Vienna, Veterinary University of Vienna, Austria.

Abstract

The geometrical representation of the space of phylogenetic trees implies a metric on the space of weighted trees. This metric, the geodesic distance, is the length of the shortest path through that space. We present an exact algorithm to compute this metric. For biologically reasonable trees, the implementation allows fast computations of the geodesic distance, although the running time of the algorithm is worst-case exponential. The algorithm was applied to pairs of 118 gene trees of the metazoa. The results show that a special path in tree space, the cone path, which can be computed in linear time, is a good approximation of the geodesic distance. The program GeoMeTree is a python implementation of the geodesic distance, and it is approximations and is available from www.cibiv.at/software/geometree.

KEYWORDS:

Robinson-Foulds distance; cone path; geodesic path; phylogeny; tree space

PMID:
18631022
DOI:
10.1089/cmb.2008.0068
[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Support Center