Determining distances and consensus between mutation trees

Luís Cunha, Jack Kuipers, Thiago Lopes · 2025

Read Determining distances and consensus between mutation trees by Luís Cunha, Jack Kuipers, Thiago Lopes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-07529.txt.

Description

A tumor's history can be drawn as a tree of mutations, but noisy sequencing leaves the true tree uncertain. Luís Cunha and co-authors define a way to measure the distance between two such trees: the subtree movement, which relocates a branch from one spot to another. They prove that deciding this distance is NP-complete, so exact answers are likely out of reach for large trees.

A related common-subtree problem, solvable in polynomial time, gives a usable upper bound. For sets of trees, both the median and closest consensus problems are NP-complete too, even with three trees. Their algorithms still produce consensus trees that summarize real tumors better than any single input tree.

Catalog record

CREATORLuís Cunha, Jack Kuipers, Thiago Lopes
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-07529

Browse the full library · About the Tower of Babel