  Phylogenies depicting the evolutionary history of genetically heterogeneous
subpopulations of cells from the same cancer, i.e., cancer phylogenies, offer
valuable insights about cancer development and guide treatment strategies. Many
methods exist that reconstruct cancer phylogenies using point mutations
detected with bulk DNA sequencing. However, these methods become inaccurate
when reconstructing phylogenies with more than 30 mutations, or, in some cases,
fail to recover a phylogeny altogether. Here, we introduce Orchard, a cancer
phylogeny reconstruction algorithm that is fast and accurate using up to 1000
mutations. Orchard samples without replacement from a factorized approximation
of the posterior distribution over phylogenies, a novel result derived in this
paper. Each factor in this approximate posterior corresponds to a conditional
distribution for adding a new mutation to a partially built phylogeny. Orchard
optimizes each factor sequentially, generating a sequence of incrementally
larger phylogenies that ultimately culminate in a complete tree containing all
mutations. Our evaluations demonstrate that Orchard outperforms
state-of-the-art cancer phylogeny reconstruction methods in reconstructing more
plausible phylogenies across 90 simulated cancers and 14 B-progenitor acute
lymphoblastic leukemias (B-ALLs). Remarkably, Orchard accurately reconstructs
cancer phylogenies using up to 1,000 mutations. Additionally, we demonstrate
that the large and accurate phylogenies reconstructed by Orchard are useful for
identifying patterns of somatic mutations and genetic variations among distinct
cancer cell subpopulations.
