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.

(2022). MUL-tree pruning for consistency and optimal reconciliation - complexity and algorithms [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from https://hdl.handle.net/10446/234196

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

Dondi, Riccardo;
2022-01-01

Abstract

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.
articolo
2022
Gascon, Mathieu; Dondi, Riccardo; El-Mabrouk, Nadia
(2022). MUL-tree pruning for consistency and optimal reconciliation - complexity and algorithms [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from https://hdl.handle.net/10446/234196
File allegato/i alla scheda:
File Dimensione del file Formato  
TCS2022.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 802.39 kB
Formato Adobe PDF
802.39 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/234196
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact