在没有水平基因转移的情况下,可以有效地将非二元基因树与二元物种树进行协调,但是在基因转移的情况下变得很难。这里,我们关注内共生基因转移(EGT)的特殊情况,即同一物种的线粒体和核基因组之间的转移。更确切地说,给定一个多分叉(非二元)基因树,其叶子标记为0或1,具体取决于相应的基因是否属于相应物种的线粒体基因组或核基因组,我们研究了推断最简约重复的问题,损失和EGT(DLE)对树的任何二进制细化。我们提出了一种通用的两步法:忽略叶子的0-1标记,输出最小化重复和丢失(DL)调节的二进制分辨率,然后,对于这样的决议,以最小化EGT事件的方式将已知数量的0和1分配给叶子。虽然第一步对应于研究良好的非二进制DL-Reconciliation问题,与第二步对应的标签分配问题的复杂性未知。我们证明这个问题是NP完全的,即使树被限制在一个单一的多发性切除术中,即使转移只能发生在一个方向。我们提出了一种通用算法,分别求解每个多边形,这对于单一的运营成本是最优的,以及一种多项式时间算法,用于在特殊情况下解决多切症,其中基因特定于除一个物种外的所有物种中的单个基因组(线粒体或核)。这项工作代表了在多分叉基因树的情况下与内共生基因转移和解的第一个算法研究。
Reconciling a non-binary gene tree with a binary species tree can be done efficiently in the absence of horizontal gene transfers, but becomes NP-hard in the presence of gene transfers. Here, we focus on the special case of endosymbiotic gene transfers (EGT), i.e. transfers between the mitochondrial and nuclear genome of the same species. More precisely, given a multifurcated (non-binary) gene tree with leaves labeled 0 or 1 depending on whether the corresponding genes belong to the mitochondrial or nuclear genome of the corresponding species, we investigate the problem of inferring a most parsimonious Duplication, Loss and EGT (DLE) Reconciliation of any binary refinement of the tree. We present a general two-steps method: ignoring the 0-1 labeling of leaves, output a binary resolution minimizing the Duplication and Loss (DL) Reconciliation and then, for such resolution, assign a known number of 0s and 1s to the leaves in a way minimizing EGT events. While the first step corresponds to the well studied non-binary DL-Reconciliation problem, the complexity of the label assignment problem corresponding to the second step is unknown. We show that this problem is NP-complete, even when the tree is restricted to a single polytomy, and even if transfers can occur in only one direction. We present a general algorithm solving each polytomy separately, which is shown optimal for a unitary cost of operation, 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. This work represents the first algorithmic study for reconciliation with endosymbiotic gene transfers in the case of a multifurcated gene tree.