2026-07-24T02:53:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14354 2024-03-06T10:53:57Z ddc:004 open_access

The Most Parsimonious Reconciliation Problem in the Presence of Incomplete Lineage Sorting and Hybridization Is NP-Hard LeMay, Matthew Wu, Yi-Chieh Libeskind-Hadas, Ran phylogenetics reconciliation deep coalescence hybridization NP-hardness The maximum parsimony phylogenetic reconciliation problem seeks to explain incongruity between a gene phylogeny and a species phylogeny with respect to a set of evolutionary events. While the reconciliation problem is well-studied for species and gene trees subject to events such as duplication, transfer, loss, and deep coalescence, recent work has examined species phylogenies that incorporate hybridization and are thus represented by networks rather than trees. In this paper, we show that the problem of computing a maximum parsimony reconciliation for a gene tree and species network is NP-hard even when only considering deep coalescence. This result suggests that future work on maximum parsimony reconciliation for species networks should explore approximation algorithms and heuristics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew LeMay and Yi-Chieh Wu and Ran Libeskind-Hadas 2021 Is Part Of LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2021.1 urn:nbn:de:0030-drops-143546 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.1 eng https://creativecommons.org/licenses/by/4.0/legalcode