An algebraic metric for phylogenetic trees |
| |
Authors: | Ricardo Alberich Gabriel Cardona Francesc Rosselló Gabriel Valiente |
| |
Institution: | 1. Department of Mathematics and Computer Science, University of the Balearic Islands, E-07122 Palma de Mallorca, Spain;2. Department of Software, Technical University of Catalonia, E-08034 Barcelona, Spain |
| |
Abstract: | The definition of similarity measures for phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in databases, and the assessment of phylogenetic reconstruction methods. The transposition distance for fully resolved trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this work, we generalize the transposition metric from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees (up to isomorphisms) with a fixed number of labeled leaves into a symmetric group. We also show that this transposition distance can be computed in linear time and we establish some of its basic properties. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|