License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2018.24
URN: urn:nbn:de:0030-drops-93263
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9326/
Go to the corresponding LIPIcs Volume Portal

El-Kebir, Mohammed

Parsimonious Migration History Problem: Complexity and Algorithms

pdf-format:
LIPIcs-WABI-2018-24.pdf (2 MB)

Abstract

In many evolutionary processes we observe extant taxa in different geographical or anatomical locations. To reconstruct the migration history from a given phylogenetic tree T, one can model locations using an additional character and apply parsimony criteria to assign a location to each internal vertex of T. The migration criterion assumes that migrations are independent events. This assumption does not hold for evolutionary processes where distinct taxa from different lineages comigrate from one location to another in a single event, as is the case in metastasis and in certain infectious diseases. To account for such cases, the comigration criterion was recently introduced, and used as an optimization criterion in the Parsimonious Migration History (PMH) problem. In this work, we show that PMH is NP-hard. In addition, we show that a variant of PMH is fixed parameter tractable (FPT) in the number of locations. On simulated instances of practical size, we demonstrate that our FPT algorithm outperforms a previous integer linear program in terms of running time.

BibTeX - Entry

@InProceedings{elkebir:LIPIcs:2018:9326,
  author =	{Mohammed El-Kebir},
  title =	{{Parsimonious Migration History Problem: Complexity and Algorithms}},
  booktitle =	{18th International Workshop on Algorithms in  Bioinformatics (WABI 2018)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Laxmi Parida and Esko Ukkonen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9326},
  URN =		{urn:nbn:de:0030-drops-93263},
  doi =		{10.4230/LIPIcs.WABI.2018.24},
  annote =	{Keywords: Reconciliation, maximum parsimony, metastasis, infection, phylogenetics, phylogeography, fixed parameter tractability}
}

Keywords: Reconciliation, maximum parsimony, metastasis, infection, phylogenetics, phylogeography, fixed parameter tractability
Collection: 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Issue Date: 2018
Date of publication: 02.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI