Complexity and Algorithms for MUL-Tree Pruning
Complexity and Algorithms for MUL-Tree Pruning
复制标题
多树剪枝的复杂性和算法
DOI：
10.1007/978-3-030-79987-8_23
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nadia El
中科院分区：
文献类型：
--
作者：
Mathieu Gascon;R. Dondi;Nadia El
多重标号树(或MUL-树)是一种有根树，其中每一片叶子都由某个集合中的一个元素来标记，但其中多个叶子可以由的相同元素来标记。多树在许多领域都有应用。在系统发育学中，它们可以代表基因家族的进化，其中基因由它们所属的物种来代表，叶标签的不唯一性来自于给定的基因组可能包含许多相似基因的事实。在这篇文章中，我们考虑了与导致单标记树的MUL-树的叶修剪(叶去除)有关的两个问题。首先，给定一组MUL树，MUL树集合一致性修剪(MULSETPC)问题要求对每棵树进行修剪，得到一组相容树，即标签同构的单标记树的集合。其次，一次处理每棵基因树，MUL树修剪用于协调(MULPR)问题要求修剪最小化与给定物种树的协调成本。我们证明了多集是NP-难的，当参数化为复制成本时，多集是W[2]-难的。然后，我们为MULPR开发了一个多项式时间启发式，并通过与EnSembl Genome Browser中的一组基因树上的蛮力精确方法进行比较，证明了它的准确性。
A multiply-labeled tree (or MUL-tree) is a rooted tree in which every leaf is labeled by an element from some set, but in which more than one leaf may be labeled by the same element of. MUL-trees have applications in many fields. In phylogenetics, they can represent the evolution of gene families, where genes are represented by the species they belong to, the non-uniqueness of leaf-labels coming from the fact that a given genome may contain many paralogous genes. In this paper, we consider two problems related to the leaf-pruning (leaf removal) of MUL-trees leading to single-labeled trees. First, given a set of MUL-trees, theMUL-tree Set Pruning for Consistency(MULSETPC) Problem asks for a pruning of each tree leading to a set of consistent trees, i.e. a collection of label-isomorphic single-labeled trees. Second, processing each gene tree at a time, theMUL-tree Pruning for Reconciliation(MULPR) Problem asks for a pruning minimizing a reconciliation cost with a given species tree. We show thatMULTSETPCis NP-hard and thatMULPRis W[2]-hard when parameterized by the duplication cost. We then develop a polynomial-time heuristic forMULPRand show its accuracy by comparing it to a brute-force exact method on a set of gene trees from the Ensembl Genome Browser.