Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Reordering a tree according to an order on its leaves

Abstract : In this article, we study two problems consisting in reordering a tree to fit with an order on its leaves provided as input, which were earlier introduced in the context of phylogenetic tree comparison for bioinformatics, OTCM and OTDE. The first problem consists in finding an order which minimizes the number of inversions with an input order on the leaves, while the second one consists in removing the minimum number of leaves from the tree to make it consistent with the input order on the remaining leaves. We show that both problems are NP-complete when the maximum degree is not bounded, as well as a problem on tree alignment, answering two questions opened in 2010 by Henning Fernau, Michael Kaufmann and Mathias Poths. We provide a polynomial-time algorithm for OTDE in the case where the maximum degree is bounded by a constant and an FPT algorithm in a parameter lower than the number of leaves to delete. Our results have practical interest not only for bioinformatics but also for digital humanities to evaluate, for example, the consistency of the dendrogram obtained from a hierarchical clustering algorithm with a chronological ordering of its leaves. We explore the possibilities of practical use of our results both on trees obtained by clustering the literary works of French authors and on simulated data.
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-03413413
Contributor : Philippe Gambette Connect in order to contact the contributor
Submitted on : Wednesday, November 3, 2021 - 5:39:25 PM
Last modification on : Thursday, November 25, 2021 - 6:04:45 AM

File

2021BulteauGambetteSeminck-pre...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03413413, version 1

Citation

Laurent Bulteau, Philippe Gambette, Olga Seminck. Reordering a tree according to an order on its leaves. 2021. ⟨hal-03413413⟩

Share

Metrics

Record views

44

Files downloads

36