2026-08-14T15:28:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17039 2024-03-06T10:58:35Z ddc:004 open_access

Non-Binary Tree Reconciliation with Endosymbiotic Gene Transfer Gascon, Mathieu El-Mabrouk, Nadia Reconciliation Duplication Endosymbiotic gene transfer Multifurcated gene tree Polytomy Gene transfer between the mitochondrial and nuclear genome of the same species, called endosymbiotic gene transfer (EGT), is a mechanism which has largely shaped gene contents in eukaryotes since a unique ancestral endosymbiotic event know to be at the origin of all mitochondria. The gene tree-species tree reconciliation model has been recently extended to account for EGTs: given a binary gene tree and a binary species tree, the EndoRex software outputs an optimal DLE-Reconciliation, that is an embedding of the gene tree into the species tree inducing a most parsimonious history of Duplications, Losses and EGT events. Here, we provide the first algorithmic study for DLE-Reconciliation in the case of a multifurcated (non-binary) gene tree. We present a general two-steps method: first, ignoring the mitochondrial-nuclear (or 0-1) labeling of leaves, output a binary resolution minimizing the DL-Reconciliation and, for each resolution, assign a known number of 0s and 1s to the leaves in a way minimizing EGT events. While Step 1 corresponds to the well studied non-binary DL-Reconciliation problem, the complexity of the formal label assignment problem related to Step 2 is unknown. Here, we show it is NP-complete even for a single polytomy (non-binary node). We then provide a heuristic which is exact for the unitary cost of operations, and a polynomial-time algorithm for solving a polytomy in the special case where genes are specific to a single genome (mitochondrial or nuclear) in all but one species. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathieu Gascon and Nadia El-Mabrouk 2022 Is Part Of LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2022.5 urn:nbn:de:0030-drops-170390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode