MUL-tree pruning for consistency and optimal reconciliation - complexity and algorithms

A multi-labeled tree (or MUL-tree) is a rooted tree in which every leaf is labeled by an element from some set X, but in which more than one leaf may be labeled by the same element of X. 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 (genes related through duplication). 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, the MUL-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 one tree at a time, the MUL-tree Pruning for Reconciliation (MULPR) Problem asks for a pruning that minimizes a “reconciliation” cost, i.e. an evolutionary cost of the gene family through duplication, given a known species tree. We show that MULSETPC is NP-hard and that MULPR is W[2]-hard when parameterized by the duplication cost, NP-hard when the number of occurrences of each label in a MUL-tree is bounded by two and that the optimization version of MULPR is hard to approximate within factor (1−o(1))ln⁡|X|. We then develop a polynomial-time heuristic for MULPR and show its accuracy by comparing it to a brute-force exact method on a set of gene trees from the Ensembl Genome Browser.