Generalized Matching Distance: Tumor Phylogeny Comparison Beyond the Infinite Sites Assumption

As the field of tumor phylogenomics matures, numerous methods have been developed to infer tumor phylogenies from many types of sequencing data. The tumor phylogenies being inferred have transitioned from abiding strictly to the Infinite Sites Assumption (ISA), which says that mutations are gained once and never lost, to more relaxed and more biologically accurate models such as Camin-Sokal or k-Dollo models which allow mutations to be either gained or lost multiple times, respectively. As the tumor phylogenies being inferred have become more attuned to the underlying biology of cancer, methods of comparing, or computing distances, between these phylogenies have not yet caught up. In order to address this discrepancy, we propose the Generalized Matching Distance (GMD) Problem which allows for ISA distance measures to be applied to non-ISA phylogenies after a particular type of transformation. We provide a simple, but effective solution for exactly solving the GMD Problem which is often efficient enough for many tumor phylogenies. We also provide a heuristic approach to solving the GMD Problem for instances where our exact solution is not appropriate. In our simulated experiments, we show that by using our approach to solve the GMD Problem we can effectively use ISA tumor distance measures to compare phylogenies with parallel mutations (those that are gained multiple times). Additionally, we show that our heuristic approach works well on a subset of phylogenies under the Camin-Sokal and k-Dollo models. Finally, we apply our method for solving the GMD to three tumor phylogenies generated from a colorectal cancer patient. The data for our experiments and the code for using GMD is available at: https://bitbucket.org/oesperlab/gmd/src/master/