License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2023.9
URN: urn:nbn:de:0030-drops-186357
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18635/
Roddur, Mrinmoy Saha ;
Snir, Sagi ;
El-Kebir, Mohammed
Inferring Temporally Consistent Migration Histories
Abstract
Not only do many biological populations undergo evolution, but population members may also migrate from one location to another. For example, tumor cells may migrate from the primary tumor and seed a new metastasis, and pathogens may migrate from one host to another. One may represent a population’s migration history by labeling the vertices of a given phylogeny T with locations such that an edge incident to vertices with distinct locations represents a migration. Additionally, in some biological populations, taxa from distinct lineages may comigrate from one location to another in a single event, a phenomenon known as a comigration. Here, we show that a previous problem statement for inferring migration histories that are parsimonious in terms of migrations and comigrations may lead to temporally inconsistent solutions. To remedy this deficiency, we introduce precise definitions of temporal consistency of comigrations in a phylogeny, leading to three successive problems. First, we formulate the Temporally Consistent Comigrations (TCC) problem to check if a set of comigrations is temporally consistent and provide a linear time algorithm for solving this problem. Second, we formulate the Parsimonious Consistent Comigration (PCC) problem, which aims to find comigrations given a location labeling of a phylogeny. We show that PCC is NP-hard. Third, we formulate the Parsimonious Consistent Comigration History (PCCH) problem, which infers the migration history given a phylogeny and locations of its extant vertices only. We show that PCCH is NP-hard as well. On the positive side, we propose integer linear programming models to solve the PCC and PCCH problems. We apply our approach to real and simulated data.
BibTeX - Entry
@InProceedings{roddur_et_al:LIPIcs.WABI.2023.9,
author = {Roddur, Mrinmoy Saha and Snir, Sagi and El-Kebir, Mohammed},
title = {{Inferring Temporally Consistent Migration Histories}},
booktitle = {23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
pages = {9:1--9:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-294-5},
ISSN = {1868-8969},
year = {2023},
volume = {273},
editor = {Belazzougui, Djamal and Ouangraoua, A\"{i}da},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18635},
URN = {urn:nbn:de:0030-drops-186357},
doi = {10.4230/LIPIcs.WABI.2023.9},
annote = {Keywords: Metastasis, Migration, Integer Linear Programming, Maximum parsimony}
}
