Phylogenetic Network Simplification

点击翻译按钮获取中文摘要

A multi-labeled tree (or MUL-tree, for short) is a phylogenetic tree in which every leaf label may appear more than once. Such trees have applications to the construction of phylogenetic networks by folding operations [Huber & Moulton, Mathematical Biology, 2006]. We considered the MUL-tree Set Pruning for Consistency problem (MULSETPC), which takes as input a set of MUL-trees and asks if there exists a perfect pruning of each MUL-tree that results in a consistent set of single-labeled trees. MULSETPC was known to be NP-complete [Gascon, Dondi, and El-Mabrouk, Proceedings of IWOCA 2021] when the MUL-trees are binary, each leaf label is used at most three times, and the number of MUL-trees is unbounded. We resolved an open question posed by Gascon et al. by proving a much stronger result, namely that MULULSETPC is NP-complete even when there are only two MUL-trees, every leaf label is used at most twice, and either every MUL-tree is binary or every MUL-tree has constant height. Furthermore, we introduced an extension of MULSETPC that we call MULSETPComp, which replaces the notion of consistency with compatibility, and proved that MULSETPComp is NP-complete even when there are only two MUL-trees, every leaf label is used at most thrice, and every MUL-tree has constant height. Finally, we designed a polynomial-time algorithm for instances of MULSETPC with a constant number of binary MUL-trees, in the special case where every leaf label occurs exactly once in at least one MUL-tree.