Dolphyin: A Combinatorial Algorithm for Identifying $1$-Dollo Phylogenies in Cancer

The clonal theory of cancer states that tumors are composed of heterogeneous clones, which are groups of cells with similar genotypes. Clones arise from an evolutionary process during which somatic mutations accumulate in cell populations [25]. By performing bulk or single-cell sequencing on these clones’ DNA or RNA, scientists can identify common somatic mutations such as single-nucleotide variants (SNVs), copy number aberrations (CNAs), or structural variants (SVs). Then, algorithms attempt to infer phylogenies, which represent the evolution of the tumor, from sequencing data for important downstream analysis and clinical decision-making [30]. These phylogenetic inference algorithms utilize sequencing-technology specific error characteristics and constraints on how these somatic mutations accumulate, which constitute an evolutionary model specific to the somatic mutations of interest [29].

In this work, we focus on the presence or absence of SNVs in single-cell DNA sequencing data. More precisely, we are given single-cell data in the form of a matrix $B$ where each row in the data is a taxon, representing a tumor cell, and each column is a single-nucleotide variant (SNV), hereafter referred to as a character. The entries in the data matrix would then be either $0$ or $1$, indicating the absence or presence of a mutation in a particular cell. We wish to find a phylogeny, i.e. a rooted, node-labeled tree $T$ whose leaves represent the extant cells of the tumor, internal nodes represent ancestral tumor cells, and the root represents a normal cell [25], that explains this data. We would then need to assume an evolutionary model that constrains the phylogenies allowed on this data. Under the well-studied two-state perfect phylogeny model [1, 20, 15], for example, no character can be lost once gained in a path starting from the root of tree $T$. Detecting whether an assumed error-free binary data matrix allows a phylogeny under the perfect phylogeny model is solvable in polynomial time [18, 1].

However, the restrictiveness of the perfect phylogeny model of evolution has inspired investigation into a wide range of more generalized and biologically-plausible models [4, 13]. Many analyses have operated under the flexible $k$-Dollo model of evolution, under which any character may be gained exactly once but lost in the tumor’s evolution at most $k$ times [9, 28, 12, 7]. This flexibility affords the incorporation of common biological events, such as CNAs that may delete previously gained SNVs, and can thus be much more realistically versatile in biological analysis. The $\mathrm{\infty }$-Dollo phylogeny inference [11, 26] and tree size-constrained versions of Dollo phylogeny inference [11] are known to be NP-hard. Additionally, the problem variant for Dollo inference where the total number of losses summed over all characters is minimized, rather than outright bounded per character, can be solved in polynomial time when the resulting phylogeny is clade-constrained [9].

An important subcase of the $k$-Dollo problem is the $k=1$ subcase or $1$-Dollo problem, also known as the persistent phylogeny problem (Figure 1). The $1$-Dollo problem has been extensively studied, using various problem statements, for over 20 years [17]. For example, characterizations of the $1$-Dollo problem have yielded an exact algorithm that solves the $1$-Dollo problem in time polynomial to the number of taxa and exponential to the number of characters [2]. Other work has also developed Integer Linear Programming (ILP) solutions to the $1$-Dollo problem and shown a connection between galled trees and $1$-Dollo phylogenies [19]. Graph-based approaches, specifically the ability to manipulate colored graphs representative of data matrices using sequenced and specific graph operations, have additionally yielded polynomial-time algorithms for a restricted version of the $1$-Dollo problem [3]. However, the complexity of the general $1$-Dollo problem remains an open question [3].

Separately, tumor phylogenies can either be linear – dash that is, phylogeny $T$ has no nontrivial branching points in which cell evolution diverges – dash or branching otherwise, based on the tumor’s selective pressures. In this work, we define “branching points” to entail internal nodes in $T$ with more than one child that are also internal nodes. Many phylogenies on real data, while branching, have exhibited a disproportionately small number of branching points relative to the number of taxa [28, 23]. Such phylogenies plausibly arise when the tumor microenvironment exerts severe enough selective pressure to limit branching to a few, highly viable offshoot clones [10]. This observation motivates phylogenetic inference that is specialized for finding linear or near-linear phylogenies. For example, machine learning techniques have been used to determine if a tumor phylogeny is likely linear [27] and, in previous work, we showed that determining the minimum number of changes from $0$ to $1$ in a data matrix such that the altered matrix is then representative of even a linear perfect phylogeny is NP-hard [31]. However, as far we are aware, determining $1$-Dollo phylogenies on data that are strictly linear has not yet been explicitly examined.

In this paper, our aims are first theoretical and second experimental. First, we draw an equivalence between determining if a data matrix $B$ admits a $1$-Dollo linear phylogeny and determining if $B$ has the consecutive ones property, which is a known property verifiable in polynomial time [16]. We use this theoretical characterization of matrices admitting $1$-Dollo linear phylogenies to discuss natural problem variants, such as determining $1$-Dollo linear phylogenies with fixed character-state vectors for the root or terminating leaf, and show that determining the minimal number of false negative entries in a sequencing data input to allow such a phylogeny, contrastingly, is NP-hard. As a tree can be recursively decomposed around its branching points, we then use this linear subcase of the $1$-Dollo problem to recursively characterize all matrices admitting any $1$-Dollo phylogeny, regardless of branching, with a series of necessary and sufficient conditions. Second, we develop a combinatorial algorithm, Dolphyin (DOllo Linear PHYlogeny INference Method), that uses this theoretical characterization to practically determine $1$-Dollo phylogenies on sequencing data. We show that Dolphyin, which relies on determining linear chains of taxa satisfying the $1$-Dollo model of evolution and then recursing on remaining taxa, is runtime-competitive with SPhyR – dash an ILP-based method of inference for the $k$-Dollo problem. Additionally, we adapt Dolphyin to probabilistically correct for false-negative errors in sequencing. We apply Dolphyin to simulated datasets with false-negative errors and show that Dolphyin yields $1$-Dollo phylogenies with inferred rates of error at or below the true rate of error. Finally, we apply Dolphyin to 99 real datasets of acute myeloid leukemia (AML) single cell sequencing data [23] and find that Dolphyin infers $1$-Dollo phylogenies for 55 datasets with false negative error rates consistent with the used sequencing technology.

Suppose we have sequenced $m$ cells of a tumor and identified $n$ single-nucleotide variants (SNVs). We are given a binary matrix $B\in {\{0,1\}}^{m\times n}$, whose $m$ rows or taxa correspond to the sequenced cells and whose $n$ columns or characters correspond to the SNVs. The tumor cells share a common evolutionary history, represented by a rooted and node-labeled tree $T$. Here, we require $T$ to adhere to the $k$-Dollo evolutionary model [13], defined as follows.

We omit the subscript $T$ from node labeling ${𝐛}_T(v)$ and taxa mapping ${\sigma }_T(t)$ if it is clear from context that they apply to a particular tree $T$. In this paper, we restrict our attention to the common case where at most $k=1$ loss per character is allowed and, unless otherwise stated, assume that the root must be labeled by all $0$s, i.e. $𝐛(r)={𝐛}_0=\mathrm{𝟎}$. We call such trees simply $1$-Dollo phylogenies for $B$. Thus, we seek to solve the following problem.

We note that the above problem is also known as the persistent phylogeny problem [2]. In addition to the above problem, we are also interested in the problem where $T$ is required to be a $1$-Dollo linear phylogeny for $B$.

We characterize the solution spaces of both 1DP and 1DLP, starting with the more restrictive problem, 1DLP, in Section 3.1. We then build on this result by discussing the complexity of common problem variants to 1DLP. Finally, we demonstrate in Section 3.2 that solutions to the 1DP problem can be recursively characterized in terms of itself and $1$-Dollo linear phylogenies. Due to space constraints, we delegate the proofs of all lemmas and theorems to the supplement.

To simplify the exposition, we introduce the following definition of a compact phylogeny and lemma, stating that one can assume without loss of generality that all internal, non-root nodes of solutions $T$ must either correspond to observed taxa or are branching points, and all internal edges must be either a gain or a loss edge for some character. Intuitively, any internal, non-root nodes of a given $1$-Dollo phylogeny $T^{\prime }$ that do not correspond to one of these two cases can always be contracted to create a compact $1$-Dollo phylogeny $T$.

We introduce Dolphyin (DOllo Linear PHYlogeny INference), a combinatorial algorithm that uses the above, recursive, combinatorial characterization of rooted $1$-Dollo phylogenies to solve R1DP altogether. Given any binary matrix $B$ and binary vector ${𝐛}_0$, Dolphyin determines a $1$-Dollo phylogeny on $B$ rooted at ${𝐛}_0$ by exhaustively searching over all possible values of $X_0,C_0^{+},C_0^{-}$ and determining a set of values such that (i) $X_0,C_0^{+},C_0^{-}$ are in agreement with $B$ and ${𝐛}_0$ and (ii) given the $1$-Dollo matrix decomposition of $X_0,C_0^{+},C_0^{-}$ on $B$ and ${𝐛}_0$ into submatrices $\{B_0,B_1,\mathrm{\dots },B_{\mathrm{\ell }}\}$, there exists a $1$-Dollo linear phylogeny $T_0$ on $B_0$ rooted at ${𝐛}_0$ terminating on ${𝐛}_{\ast }=𝐛({𝐛}_0,C_0^{-},C_0^{+})$ and $1$-Dollo phylogenies $T_1,\mathrm{\dots },T_{\mathrm{\ell }}$ on $B_1,\mathrm{\dots },B_{\mathrm{\ell }}$ each rooted at ${𝐛}_{\ast }$. This $1$-Dollo linear phylogeny $T_0$ can be inferred in $O(mn)$ time, and $1$-Dollo phylogenies $T_1,\mathrm{\dots },T_{\mathrm{\ell }}$ are then inferred through recursive calls of Dolphyin on matrices $B_1,\mathrm{\dots },B_{\mathrm{\ell }}$. Dolphyin then returns the $1$-Dollo phylogeny $T$ rooted at ${𝐛}_0$ on $B$ as the tree formed by the construction on $T_0,\mathrm{\dots },T_{\mathrm{\ell }}$ described in Theorem 27. This same Theorem 27 shows that this entire procedure is necessary and sufficient to solve any instance of R1DP. As an additional optimization, Dolphyin preprocesses all matrices by first removing all duplicate columns and rows, as well as trivial columns that contain 0, 1, or $m$ $1$s.

Dolphyin, and its subsequent analysis and comparison to SPhyR, was implemented on an Apple 2.3 GHz 8-Core Intel Core i9 Macbook Pro in C++11. Dolphyin is available at: https://github.com/elkebir-group/Dolphyin with commit hash fbf400f used for the experiments in this paper.

This work examines the problem of inferring a $1$-Dollo, or persistent phylogeny on single-cell sequencing DNA data for SNVs. We first examine the subcase in which our $1$-Dollo phylogeny must be linear, and we prove an equivalence between whether a binary data matrix $B$ admits a $1$-Dollo linear phylogeny and whether $B$ has the known consecutive ones property, which can be verified in polynomial time [16]. We also develop polynomial-time algorithms for natural extensions of the $1$-Dollo linear subcase, such as the cases when we restrict our $1$-Dollo phylogeny to be rooted at and/or terminate at some states. Using the linear subcase, we recursively characterize all binary matrices that admit a $1$-Dollo phylogeny with a series of conditions that are provably necessary and sufficient. Unfortunately, determining whether a matrix $B$ is $1$-Dollo using this characterization takes exponential time, leaving the hardness of the $1$-Dollo phylogeny problem open. In addition, we show that the problem of minimizing false negatives in data as to admit a $1$-Dollo linear phylogeny is NP-hard.

We use these theoretical results to develop Dolphyin, a combinatorial algorithm that infers $1$-Dollo phylogenies from sequencing data. Dolphyin directly leverages our above characterization of matrices admitting $1$-Dollo phylogenies by identifying $1$-Dollo linear phylogenies on subsets of taxa and recursing on remaining taxa and characters. Dolphyin also incorporates probabilistic error correction and thus can also be applied to data with false negative sequencing errors. We use Dolphyin to first analyze errorless, simulated datasets and show that Dolphyin is runtime competitive with SPhyR [12], a previous ILP-based approach for inferring $k$-Dollo phylogenies. We then apply Dolphyin to simulated datasets with false negative errors and demonstrate that Dolphyin, in the median case, infers $1$-Dollo phylogenies with an inferred error rate at or below the ground truth rate. We finally apply Dolphyin to 99 real acute myeloid leukemia datasets [23] and find that Dolphyin infers $1$-Dollo phylogenies on the majority of these datasets with an error rate at or below the previously, experimentally-estimated false negative error rate specific to the sequencing technology producing these datasets.

In future work, we may consider more advanced error correction schemes for more widely applying Dolphyin to existing datasets. We may also attempt to extend a similar, combinatorial and recursive framework to the $k$-Dollo model of evolution for $k>1$, or models of evolution with more than one gain. However, we note that even determining a specifically linear and errorless phylogeny with two gains or losses, per character, is NP-hard [8]. Additionally, while we may consider problem extensions such as determining a maximal number of taxa or characters admitting $1$-Dollo phylogenies in data, we note that the equivalence of 1DLP to the consecutive ones property makes several natural formulations NP-hard in even the linear and errorless cases [22]. Finally, while we argue that the first recursive call of Dolphyin is $O(2^{m+2n}mn)$ in the worst case, we would like to derive a more precise running time taking into account all recursive calls.

In summary, our work adds to the theoretical body of knowledge on the $1$-Dollo, or persistent phylogeny, model of evolution and provides a practical algorithm for inferring phylogenies that leverages these theoretical results. We hope that this combinatorial approach will aid advances in determining the complexity of $1$-Dollo problems and their variants.