We introduce new methods for characterizing commonly occurring cancer sub-types and the specific molecular abnormalities that produce them. Previous computational approaches to this problem have been hindered by the heterogeneous makeup of most tumors, which contain cells at multiple stages of progression, ranging from healthy to aggressively malignant. However, by analyzing data from single-cell assays, our approach is able to take advantage of the heterogeneous composition of tumors to infer likely progression pathways for their evolution.

We use phylogenetic algorithms to infer the evolution of the cell populations in an individual tumor. The phylogenies for many patients are then used to create a profile of commonly used pathways. This approach is combined with expectation maximization to infer unknown parameters used in phylogeny construction.

The problem of merging phylogenies inferred on different datasets from the same patient arises in our work. This problem is given a combinatorial formulation, demonstrated to be NP-hard in the general case, and a mixed-integer linear program is presented which solves it quickly on real world inputs.

We demonstrate our methods on a set of fluorescent in situ hybridization (FISH) data measuring cell-by-cell gene and chromosome copy numbers in a large sample of breast cancers. The results validate the proposed computational methods by showing consistency with several previous findings on beast cancers. They also provide novel insights into the mechanisms of tumor progression in these patients.