克隆树空间的枚举与探索：基于 Infinite Sites 与 k-Dollo 模型的理论分析与数据集生成
Enumerating and Exploring the Space of Clonal Trees
研究设计了多种算法，用于枚举指定突变数量下不同类别的克隆树，并对 Infinite Sites Assumption 与 k-Dollo 两种突变获得模型下的四类克隆树做了理论分析。利用这些算法生成了多个数据集并分析所生成的树，发现了一些符合预期与出乎意料的模式。分析还将枚举数据集与两种常用模拟数据采样流程进行比较，显示二者对空间的采样方式不同。其中一个数据集显示，在突变数量较小时，线性树比分支树普遍得多。相关代码已公开。
来源：Bioinformatics Advances · doi.org
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/.