Parsimonious migration history problem: Complexity and algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication18th International Workshop on Algorithms in Bioinformatics, WABI 2018
EditorsLaxmi Parida, Esko Ukkonen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770828
StatePublished - Aug 1 2018
Externally publishedYes
Event18th International Workshop on Algorithms in Bioinformatics, WABI 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other18th International Workshop on Algorithms in Bioinformatics, WABI 2018


  • Fixed parameter tractability
  • Infection
  • Maximum parsimony
  • Metastasis
  • Phylogenetics
  • Phylogeography
  • Reconciliation

ASJC Scopus subject areas

  • Software

Cite this