Identifying Robust Subclonal Structures through Tumor Progression Tree Alignment

Area of Science:

• Computational Biology
• Cancer Genomics
• Evolutionary Biology

Background:

• Understanding tumor evolutionary histories is crucial for cancer genomics.
• Clonal trees model tumor progression using rooted, unordered trees where nodes represent subclones labeled by mutations.

Purpose of the Study:

• To introduce and computationally solve the optimal multi-label tree alignment (omlta) problem for comparing clonal trees.
• To develop the first computational tool for optimal clonal tree alignment.

Main Methods:

• Introduced omlta, an algorithm to find the minimum number of mutation labels to remove for clonal tree isomorphism.
• Developed an algorithm with a running time of O(L^k), where L is the total number of mutation labels and k is the minimum number of labels to remove.
• Implemented the algorithm as a computational tool available at https://github.com/algo-cancer/omlta.

Main Results:

• Presented an algorithm to compute the optimal multi-label tree alignment (omlta).
• The implemented tool is the first to compute optimal alignments between clonal trees.
• Applied omlta to analyze 126 non-small cell lung cancer cases from the TRACERx study and melanoma single-cell data.

Conclusions:

• The developed omlta algorithm and tool enable optimal comparison of tumor evolutionary histories.
• This method advances the field of cancer genomics by providing a robust way to compare clonal trees.
• The application to real-world cancer data demonstrates the utility of omlta in understanding tumor evolution.