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
| CREATOR | Luís Cunha, Jack Kuipers, Thiago Lopes |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-07529