The last decade brought a significant increase in the amount of data and a variety of new inference methods for reconstructing the detailed evolutionary history of various cancers. This brings the need of designing efficient procedures for comparing rooted trees representing the evolution of mutations in tumor phylogenies. Bernardini et al. [CPM 2019] recently introduced a notion of the rearrangement distance for fully-labelled trees motivated by this necessity. This notion originates from two operations: One that permutes the labels of the nodes, the other that affects the topology of the tree. Each operation alone defines a distance that can be computed in polynomial time, while the actual rearrangement distance, that combines the two, was proven to be NP-hard. We answer two open question left unanswered by the previous work. First, what is the complexity of computing the permutation distance? Second, is there a constant-factor approximation algorithm for estimating the rearrangement distance between two arbitrary trees? We answer the first one by showing, via a two-way reduction, that calculating the permutation distance between two trees on n nodes is equivalent, up to polylogarithmic factors, to finding the largest cardinality matching in a sparse bipartite graph. In particular, by plugging in the algorithm of Liu and Sidford [ArXiv 2020], we obtain an∼O(n4/3+o(1) time algorithm for computing the permutation distance between two trees on n nodes. Then we answer the second question positively, and design a linear-time constant-factor approximation algorithm that does not need any assumption on the trees. 2012 ACM Subject Classification Theory of computation ! Design and analysis of algorithms; Theory of computation ! Approximation algorithms analysis; Theory of computation ! Problems, reductions and completeness.

Bernardini, G., Bonizzoni, P., Gawrychowski, P. (2020). On Two Measures of Distance between Fully-Labelled Trees. Intervento presentato a: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), Copenhagen [10.4230/LIPIcs.CPM.2020.6].

On Two Measures of Distance between Fully-Labelled Trees

Giulia Bernardini;Paola Bonizzoni;
2020

Abstract

The last decade brought a significant increase in the amount of data and a variety of new inference methods for reconstructing the detailed evolutionary history of various cancers. This brings the need of designing efficient procedures for comparing rooted trees representing the evolution of mutations in tumor phylogenies. Bernardini et al. [CPM 2019] recently introduced a notion of the rearrangement distance for fully-labelled trees motivated by this necessity. This notion originates from two operations: One that permutes the labels of the nodes, the other that affects the topology of the tree. Each operation alone defines a distance that can be computed in polynomial time, while the actual rearrangement distance, that combines the two, was proven to be NP-hard. We answer two open question left unanswered by the previous work. First, what is the complexity of computing the permutation distance? Second, is there a constant-factor approximation algorithm for estimating the rearrangement distance between two arbitrary trees? We answer the first one by showing, via a two-way reduction, that calculating the permutation distance between two trees on n nodes is equivalent, up to polylogarithmic factors, to finding the largest cardinality matching in a sparse bipartite graph. In particular, by plugging in the algorithm of Liu and Sidford [ArXiv 2020], we obtain an∼O(n4/3+o(1) time algorithm for computing the permutation distance between two trees on n nodes. Then we answer the second question positively, and design a linear-time constant-factor approximation algorithm that does not need any assumption on the trees. 2012 ACM Subject Classification Theory of computation ! Design and analysis of algorithms; Theory of computation ! Approximation algorithms analysis; Theory of computation ! Problems, reductions and completeness.
Si
paper
Tree distance, Cancer progression, Approximation algorithms, Fine-grained complexity
English
31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
9783959771498
Bernardini, G., Bonizzoni, P., Gawrychowski, P. (2020). On Two Measures of Distance between Fully-Labelled Trees. Intervento presentato a: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), Copenhagen [10.4230/LIPIcs.CPM.2020.6].
Bernardini, G; Bonizzoni, P; Gawrychowski, P
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/277045
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
Social impact