Enumerating and Exploring the Space of Clonal Trees

Tumor growth is a complex evolutionary process initiated by an abnormal ancestor cell progressively gaining mutations, which eventually results in uncontrolled cell division. Researchers use a structure called a clonal tree–which depicts ancestral relationships between mutated cell populations–to represent a tumor’s evolutionary history. Numerous methods have been developed to reconstruct a clonal tree from tumor sequencing data. To evaluate the accuracy of such tree inference methods, researchers typically use simulated data where the true evolutionary history is known. However, previous research has not thoroughly analyzed the space of clonal trees under different evolutionary models. Such exploration would help to better understand the underlying structure and characteristics of these spaces of trees and would aid in creation of more appropriate simulated datasets. We analyzed four different categories of clonal trees, each with their own set of assumptions. For each category, we designed and implemented enumeration algorithms that provably generate all such clonal trees with a specified number of mutations. We then used our algorithms to generate several datasets and analyzed the generated trees to discover patterns in the data across different assumptions. We also investigated two tree sampling methods to compare their output with our fully enumerated trees and found that one of the methods does a good job of representing the entire space of trees, while the other does quite poorly. Our findings have important implications for the creation of simulated data commonly used to assess new clonal tree inference methods. Code associated with the project is freely available at: https://bitbucket.org/oesperlab/tree-space/src/main/