Enumerating and Exploring the Space of Clonal Trees
Bryce Bernstein, Kendra Winhall, Layla OesperAbstract
Motivation
Tumors are the result of a complex evolutionary process. Researchers use a structure called a clonal tree, which depicts ancestral relationships between mutated cell populations, to represent a tumor’s evolutionary history. A better understanding of the complete space of all clonal trees under certain assumptions has important implications for understanding and interpreting output from clonal tree inference algorithms. It is also an interesting mathematical problem.
Results
We designed several algorithms for enumerating different categories of clonal trees with a specified number of mutations. We then provide theoretical analysis of four different categories of clonal trees that utilize two models of mutation acquisition (Infinite Sites Assumption and k-Dollo). We used our algorithms to generate several datasets and analyzed the generated trees, uncovering some expected and some unexpected patterns. Our analysis includes comparison of our enumerated datasets to two common sampling procedures used to create simulated data, and shows that they sample from the space differently. Finally, for one dataset we found that for small numbers of mutations, linear trees were much more prevalent than branching trees.
Availability and Implementation
Code associated with the project is available at: https://bitbucket.org/oesperlab/tree-space/src/main/.