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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00367086
Contributor : Vincent Berry <>
Submitted on : Tuesday, March 10, 2009 - 12:24:57 PM
Last modification on : Wednesday, September 18, 2019 - 11:05:26 AM
Long-term archiving on : Tuesday, June 8, 2010 - 8:33:53 PM

File

lata2009_submission_99.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Celine Scornavacca, Vincent Berry, Vincent Ranwez. From Gene Trees to Species Trees Through a Supertree Approach. LATA: Language and Automata Theory and Applications, Apr 2009, Tarragone, Spain. pp.10-19, ⟨10.1007/978-3-642-00982-2_60⟩. ⟨lirmm-00367086⟩

Share

Metrics

Record views

432

Files downloads

191