GPPS: an ILP-based approach for inferring cancer progression with mutation losses from single cell data

Background Cancer progression reconstruction is an important development stemming from the phylogenetics field, where the goal is to infer the mutational history of a set of tumor cells carrying these cancerous mutations. Many methods have been developed in recent years for inferring such a history from bulk-sequencing data, where they construct a perfect phylogeny of the mutations: a mutation which is gained in a history is never lost. Single Cell Sequencing (SCS) technologies are an emerging alternative which offers a much higher resolution, providing evidence of the existence of back mutations in cancer: a phenomenon which is currently widely ignored, and is not modeled by a perfect phylogeny. Results For these reasons we present gpps, an approach which combines Integer Linear Programming (ILP) with a Hill Climbing approach for reconstructing a tumor phylogeny from SCS data according to a more general model than the perfect phylogeny: allowing each mutation to be lost at most a fixed number of times, thus modeling back mutations. We test gpps on real data as well as synthetic data which simulates the error rates of SCS technologies, comparing to state-of-the-art tumor phylogeny inference methods. Here we reveal that gpps performs as well as or better than any of the tools, even on measures which do not take into account mutation losses. Most notably, we have been able to analyze a ER+ breast cancer dataset consisting of 40 somatic mutations over 47 cells, confirming the driver mutations of the original study.