From Gene Trees to Species Trees Through a Supertree Approach

Abstract : Gene trees are leaf-labeled trees inferred from molecular se- quences. Due to duplication events arising in genome evolution, gene trees usually have multiple copies of some labels, i.e. species. Inferring a species tree from a set of multi-labeled gene trees (MUL trees) is a well- known problem in computational biology. We propose a novel approach to tackle this problem, mainly to transform a collection of MUL trees into a collection of evolutionary trees, each containing single copies of labels. To that aim, we provide several algorithmic building stones and describe how they fit within a general species tree inference process. Most algorithms have a linear-time complexity, except for an FPT algorithm proposed for a problem that we show to be intractable.
Type de document :
Communication dans un congrès
Dediu, Adrian Horia, Ionescu, Armand Mihai, Martin-Vide, Carlos. LATA'09: Third International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragone, Espagne, Springer, 5457, pp.10-19, 2009, Lecture Notes in Computer Science (LNCS). 〈http://grammars.grlmc.com/LATA2009/〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00367086
Contributeur : Vincent Berry <>
Soumis le : mardi 10 mars 2009 - 12:24:57
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:33:53

Fichier

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

Identifiants

  • HAL Id : lirmm-00367086, version 1

Collections

Citation

Celine Scornavacca, Vincent Berry, Vincent Ranwez. From Gene Trees to Species Trees Through a Supertree Approach. Dediu, Adrian Horia, Ionescu, Armand Mihai, Martin-Vide, Carlos. LATA'09: Third International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragone, Espagne, Springer, 5457, pp.10-19, 2009, Lecture Notes in Computer Science (LNCS). 〈http://grammars.grlmc.com/LATA2009/〉. 〈lirmm-00367086〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

102