dorsal/arxiv
View SchemaThe transposition distance for phylogenetic trees
| Authors | Francesc Rossello, Gabriel Valiente |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0604024 |
| URL | https://arxiv.org/abs/q-bio/0604024 |
Abstract
The search for similarity and dissimilarity measures on phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in phylogenetic databases, and the assessment of clustering results in bioinformatics. The transposition distance for fully resolved phylogenetic trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this paper, we generalize the transposition distance from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees with a fixed number of labeled leaves into a symmetric group and a generalization of Reidys-Stadler's involution metric for RNA contact structures. We also present simple linear-time algorithms for computing it.
{
"annotation_id": "a15f0352-1a2e-4209-9cf4-22ac00de6f2e",
"date_created": "2026-03-02T18:01:34.919000Z",
"date_modified": "2026-03-02T18:01:34.919000Z",
"file_hash": "f0c7fa9df6f5fdb1260f47e9252470fb7eb92055b6106a39b6682bd42900e89b",
"private": false,
"record": {
"abstract": "The search for similarity and dissimilarity measures on phylogenetic trees\nhas been motivated by the computation of consensus trees, the search by\nsimilarity in phylogenetic databases, and the assessment of clustering results\nin bioinformatics. The transposition distance for fully resolved phylogenetic\ntrees is a recent addition to the extensive collection of available metrics for\ncomparing phylogenetic trees. In this paper, we generalize the transposition\ndistance from fully resolved to arbitrary phylogenetic trees, through a\nconstruction that involves an embedding of the set of phylogenetic trees with a\nfixed number of labeled leaves into a symmetric group and a generalization of\nReidys-Stadler\u0027s involution metric for RNA contact structures. We also present\nsimple linear-time algorithms for computing it.",
"arxiv_id": "q-bio/0604024",
"authors": [
"Francesc Rossello",
"Gabriel Valiente"
],
"categories": [
"q-bio.PE",
"cs.CE",
"math.GR",
"q-bio.OT"
],
"title": "The transposition distance for phylogenetic trees",
"url": "https://arxiv.org/abs/q-bio/0604024"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9afa6a5a-c1c5-4dbd-8b90-76aff8e98478",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}