Accéder directement au contenu Accéder directement à la navigation

# Constructing a Consensus Phylogeny from a Leaf-Removal Distance

Abstract : Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing {possibly discordant} evolutionary scenarios for a given set of genes or species, and aims at finding a single tree that minimizes the leaf-removal distance to the input trees. This problem is a specific instance of the general consensus/supertree problem, widely used to combine or summarize discordant evolutionary trees. The problem we introduce is specifically tailored to address the case of discrepancies between the input trees due to the misplacement of individual taxa. Most supertree or consensus tree problems are computationally intractable, and we show that the problem we introduce is also NP-hard. We provide tractability results in form of a 2-approximation algorithm. We also introduce a variant that minimizes the maximum number $d$ of leaves that are removed from any input tree, and provide a parameterized algorithm for this problem with parameter $d$.
Type de document :
Communication dans un congrès
Domaine :

Littérature citée [18 références]

https://hal.archives-ouvertes.fr/hal-02155266
Contributeur : Celine Scornavacca <>
Soumis le : mardi 12 novembre 2019 - 11:27:21
Dernière modification le : mercredi 26 février 2020 - 19:06:07
Document(s) archivé(s) le : jeudi 13 février 2020 - 17:08:16

### Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Cédric Chauve, Mark Jones, Manuel Lafond, Celine Scornavacca, Mathias Weller. Constructing a Consensus Phylogeny from a Leaf-Removal Distance. SPIRE 2017, Sep 2017, Palermo, Italy. pp.129--143, ⟨10.1007/978-3-319-67428-5\_12⟩. ⟨hal-02155266⟩

### Métriques

Consultations de la notice

## 71

Téléchargements de fichiers