EssentCell: Discovering Essential Evolutionary Relations in Noisy Single-Cell Data

Single-cell sequencing (SCS) enables investigating tumor evolution at a single cell resolution. A common type of analysis to investigate evolutionary structure from an SCS experiment is to determine a phylogenetic tree structure from the data. This problem has been well-studied under the assumption that mutations only accumulate in the evolution of cancer and there is a simple characterization of when the data is compatible with a perfect phylogeny based on the absence of a special "conflict" submatrix. SCS data can be represented as a binary matrix, where the ij-th entry indicates whether cell i has mutation j. In practice, SCS data is noisy, so a natural question is what is the minimum number of entries to flip in the data matrix, in order that the matrix becomes "conflict-free" and thus compatible with a perfect phylogeny. Furthermore, the false positive rate is orders of magnitude smaller than the false negative rate, so that at most a few false positives occur with high probability. We consider a variation of the minimum-flip problem in which the number of false positives in the solution is a parameter. Often, there can be multiple optimal solutions, so a natural question is what relations are true among all optimal solutions for a small range of possible false positives values; we call such relations essential. In this work, we propose an efficient algorithm based on integer linear programming to determine all essential relations in the data. We test our software tool, EssentCell, on several data sets and discuss the results found.