Branching Out: An Alternative Approach to Variational Inference Based Clonal Tree Reconstruction Using Wilson’s Algorithm

Abstract

In this thesis, we explore the application of variational inference in reconstructing tumor phylogenies, or clone trees, from copy number aberrations measured in single-cell DNA sequencing data. As a first step, we identify a key computational bottleneck in existing variational inference algorithms for clone tree inference [10], and propose a computationally attractive alternative. Specifically, we analyze and test the weighted spanning tree sampling algorithm LARS used in the clone tree inference pipeline VicTree [10]. Through comprehensive testing, we discover that LARS is not robust and fails to properly sample from its target sampling distribution. As an alternative, we propose applying Wilson’s sampling algorithm [13], and find that it significantly outperforms LARS at sampling from the target distribution. Furthermore, Wilson’s algorithm provides substantial computational benefits over LARS, and scales much better in the problem size. Having demonstrated the superior performance of Wilson’s sampling algorithm to LARS, we attempt to incorporate it into the VicTree variational inference pipeline. Preliminary results show that the clone tree reconstruction with the modified VicTree algorithm is promising, as it is more accurate and significantly faster than before, though our analysis also identifies several issues with the modified VicTree pipeline.