An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.

A. Kupczok, A. Von Haeseler, S. Klaere, Journal of Computational Biology 15 (2008) 577–591.

Download
No fulltext has been uploaded. References only!

DOI
Journal Article | Published
Author
Kupczok, AnneIST Austria; von Haeseler,Arndt; Klaere,Steffen
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.
Publishing Year
Date Published
2008-01-01
Journal Title
Journal of Computational Biology
Acknowledgement
10.1089/cmb.2008.0068
Volume
15
Issue
6
Page
577 - 591
IST-REx-ID

Cite this

Kupczok A, Von Haeseler A, Klaere S. An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees. Journal of Computational Biology. 2008;15(6):577-591. doi:4200
Kupczok, A., Von Haeseler, A., & Klaere, S. (2008). An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees. Journal of Computational Biology. Mary Ann Liebert. https://doi.org/4200
Kupczok, Anne, Arndt Von Haeseler, and Steffen Klaere. “An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.” Journal of Computational Biology. Mary Ann Liebert, 2008. https://doi.org/4200.
A. Kupczok, A. Von Haeseler, and S. Klaere, “An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.,” Journal of Computational Biology, vol. 15, no. 6. Mary Ann Liebert, pp. 577–591, 2008.
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.
Kupczok, Anne, et al. “An Exact Algorithm for the Geodesic Distance between Phylogenetic Trees.” Journal of Computational Biology, vol. 15, no. 6, Mary Ann Liebert, 2008, pp. 577–91, doi:4200.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar