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

Single-cell sequencing (SCS) enables the study of tumor evolution at the resolution of a single cell. SCS data can be represented as a binary matrix, where the $ij$-th entry indicates whether cell $i$ has mutation $j$. There is a simple characterization of when the data is compatible with a perfect phylogeny based on the absence of a special "conflict" submatrix. In practice, SCS data are noisy, which raises the natural question of the minimum number of entries that must be flipped in the data matrix to make it conflict-free and thus compatible with a perfect phylogeny. Furthermore, the likelihood of a false positive is several orders of magnitude smaller than that of a false negative rate. We consider a variation of the minimum-flip problem parameterized by the number of false positives. Restricting the false positive rate to a small range, often multiple optimal solutions can arise. While previous work has focused on reconstructing a single optimal phylogenetic tree, we are interested in the relations that are present among all optimal solutions; we call such relations essential. In this work, we propose an efficient algorithm based on integer linear programming to determine the essential relation on the cells given an SCS data matrix. We test our tool, ${\sf EssentCell}$, on several data sets and discuss the results found.