1 Search Results for "Noutahi, Emmanuel"

Document
DOI: 10.4230/LIPIcs.CPM.2016.14
Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost

Authors: Manuel Lafond, Emmanuel Noutahi, and Nadia El-Mabrouk

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
Polytomies in gene trees are multifurcated nodes corresponding to unresolved parts of the tree, usually due to insufficient differentiation between sequences of homologous gene copies. Apart from gene sequences, other information such as that contained in the species tree can be used to resolve such intricate parts of a gene tree. The problem of resolving a multifurcated tree has been considered by many authors, the objective function often being the number of duplications and losses reflected by the reconciliation of the resolved gene tree with the species tree. Here, we present PolytomySolver, an algorithm accounting for a more general model allowing different costs for duplications and losses per species. The time complexity of this algorithm is linear for the unit cost and is quadratic for the general cost, which outperforms the best known solutions so far by a linear factor. We show on simulated trees that the gain in theoretical complexity has a real practical impact on running times.
Cite as

Manuel Lafond, Emmanuel Noutahi, and Nadia El-Mabrouk. Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lafond_et_al:LIPIcs.CPM.2016.14,
  author =	{Lafond, Manuel and Noutahi, Emmanuel and El-Mabrouk, Nadia},
  title =	{{Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.14},
  URN =		{urn:nbn:de:0030-drops-60907},
  doi =		{10.4230/LIPIcs.CPM.2016.14},
  annote =	{Keywords: gene tree, polytomy, reconciliation, resolution, weighted cost, phylogeny}
}
  • Refine by Author
  • 1 El-Mabrouk, Nadia
  • 1 Lafond, Manuel
  • 1 Noutahi, Emmanuel

  • Refine by Classification

  • Refine by Keyword
  • 1 gene tree
  • 1 phylogeny
  • 1 polytomy
  • 1 reconciliation
  • 1 resolution
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact