---
OA_type: closed access
_id: '3769'
abstract:
- lang: eng
  text: 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.
acknowledgement: 10.1089/cmb.2008.0068
article_processing_charge: No
article_type: original
author:
- first_name: Anne
  full_name: Kupczok, Anne
  id: 2BB22BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Kupczok
- first_name: Arndt
  full_name: Von Haeseler, Arndt
  last_name: Von Haeseler
- first_name: Steffen
  full_name: Klaere, Steffen
  last_name: Klaere
citation:
  ama: Kupczok A, Von Haeseler A, Klaere S. An Exact Algorithm for the Geodesic Distance
    between Phylogenetic Trees. <i>Journal of Computational Biology</i>. 2008;15(6):577-591.
    doi:<a href="https://doi.org/10.1089/cmb.2008.0068">10.1089/cmb.2008.0068</a>
  apa: Kupczok, A., Von Haeseler, A., &#38; Klaere, S. (2008). An Exact Algorithm
    for the Geodesic Distance between Phylogenetic Trees. <i>Journal of Computational
    Biology</i>. Mary Ann Liebert. <a href="https://doi.org/10.1089/cmb.2008.0068">https://doi.org/10.1089/cmb.2008.0068</a>
  chicago: Kupczok, Anne, Arndt Von Haeseler, and Steffen Klaere. “An Exact Algorithm
    for the Geodesic Distance between Phylogenetic Trees.” <i>Journal of Computational
    Biology</i>. Mary Ann Liebert, 2008. <a href="https://doi.org/10.1089/cmb.2008.0068">https://doi.org/10.1089/cmb.2008.0068</a>.
  ieee: A. Kupczok, A. Von Haeseler, and S. Klaere, “An Exact Algorithm for the Geodesic
    Distance between Phylogenetic Trees.,” <i>Journal of Computational Biology</i>,
    vol. 15, no. 6. Mary Ann Liebert, pp. 577–591, 2008.
  ista: Kupczok A, Von Haeseler A, Klaere S. 2008. An Exact Algorithm for the Geodesic
    Distance between Phylogenetic Trees. Journal of Computational Biology. 15(6),
    577–591.
  mla: Kupczok, Anne, et al. “An Exact Algorithm for the Geodesic Distance between
    Phylogenetic Trees.” <i>Journal of Computational Biology</i>, vol. 15, no. 6,
    Mary Ann Liebert, 2008, pp. 577–91, doi:<a href="https://doi.org/10.1089/cmb.2008.0068">10.1089/cmb.2008.0068</a>.
  short: A. Kupczok, A. Von Haeseler, S. Klaere, Journal of Computational Biology
    15 (2008) 577–591.
date_created: 2018-12-11T12:05:04Z
date_published: 2008-07-16T00:00:00Z
date_updated: 2026-06-10T10:17:21Z
day: '16'
doi: 10.1089/cmb.2008.0068
extern: '1'
external_id:
  pmid:
  - '18631022'
intvolume: '        15'
issue: '6'
language:
- iso: eng
month: '07'
oa_version: None
page: 577 - 591
pmid: 1
publication: Journal of Computational Biology
publication_identifier:
  eissn:
  - 1557-8666
  issn:
  - 1066-5277
publication_status: published
publisher: Mary Ann Liebert
publist_id: '2458'
status: public
title: An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15
year: '2008'
...