New Metrics for Phylogenies

Article type: Research Article

Authors: Bolikowski, Łukasz | Gambin, Anna

Affiliations: Interdisciplinary Center for Mathematical and Computational Modeling Al. Żwirki i Wigury 93, 02-089 Warsaw, Poland | Institute of Informatics, Warsaw University Banacha 2, 02-097 Warsaw, Poland. E-mail: aniag@mimuw.edu.pl

Abstract: In this paper we propose two new metrics defined on the space of phylogenetic trees. The problem of determining how distant two trees are from each other is crucial because many various methods exist for reconstructing phylogenetic trees from molecular data. These techniques (in fact often heuristics) applied to the same data set result in significantly different trees. We investigate the basic properties of new metrics and present efficient algorithms approximating the distance between two trees for partition metric. Computational experiments, which has been performed for large family of trees justify the applicability of our algorithms. The interesting application of our framework is the identification of the ancestral paralog position in the paralog families. We propose to select the set of genes (exemplars) that minimize the partition metric distance between gene tree and species tree.

Journal: Fundamenta Informaticae, vol. 78, no. 2, pp. 199-216, 2007