English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The last decade brought a significant increase in the amount of data and avariety of new inference methods for reconstructing the detailed evolutionaryhistory of various cancers. This brings the need of designing efficientprocedures for comparing rooted trees representing the evolution of mutationsin tumor phylogenies. Bernardini et al. [CPM 2019] recently introduced a notionof the rearrangement distance for fully-labelled trees motivated by thisnecessity. This notion originates from two operations: one that permutes thelabels of the nodes, the other that affects the topology of the tree. Eachoperation alone defines a distance that can be computed in polynomial time,while the actual rearrangement distance, that combines the two, was proven tobe NP-hard.  We answer two open question left unanswered by the previous work. First, whatis the complexity of computing the permutation distance? Second, is there aconstant-factor approximation algorithm for estimating the rearrangementdistance between two arbitrary trees? We answer the first one by showing, via atwo-way reduction, that calculating the permutation distance between two treeson $n$ nodes is equivalent, up to polylogarithmic factors, to finding thelargest cardinality matching in a sparse bipartite graph. In particular, byplugging in the algorithm of Liu and Sidford [ArXiv 2020], we obtain an$O(n^{4/3+o(1)})$ time algorithm for computing the permutation distance betweentwo trees on $n$ nodes. Then we answer the second question positively, anddesign a linear-time constant-factor approximation algorithm that does not needany assumption on the trees.

On Two Measures of Distance between Fully-Labelled Trees