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.

Abstract Motivated by computing duplication patterns in sequences, a new problem called the longest letter-duplicated subsequence (LLDS) is proposed. Given a sequence S of length n, a letter-duplicated subsequence is a subsequence of S in the form of $$x_1^{d_1}x_2^{d_2}\ldots x_k^{d_k}$$ x 1 d 1 x 2 d 2 … x k d k with $$x_i\in \Sigma $$ x i ∈ Σ , $$x_j\ne x_{j+1}$$ x j ≠ x j + 1 and $$d_i\ge 2$$ d i ≥ 2 for all i in [k] and j in $$[k-1]$$ [ k - 1 ] . A linear time algorithm for computing a longest letter-duplicated subsequence (LLDS) of S can be easily obtained. In this paper, we focus on two variants of this problem: (1) ‘all-appearance’ version, i.e., all letters in $$\Sigma $$ Σ must appear in the solution, and (2) the weighted version. For the former, we obtain dichotomous results: We prove that, when each letter appears in S at least 4 times, the problem and a relaxed version on feasibility testing (FT) are both NP-hard. The reduction is from $$(3^+,1,2^-)$$ ( 3 + , 1 , 2 - ) -SAT, where all 3-clauses (i.e., containing 3 lals) are monotone (i.e., containing only positive literals) and all 2-clauses contain only negative literals. We then show that when each letter appears in S at most 3 times, then the problem admits an O(n) time algorithm. Finally, we consider the weighted version, where the weight of a block $$x_i^{d_i} (d_i\ge 2)$$ x i d i ( d i ≥ 2 ) could be any positive function which might not grow with $$d_i$$ d i . We give a non-trivial $$O(n^2)$$ O ( n 2 ) time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of S whose weight is maximized.

Given a sequence $S$ of length $n$, a letter-duplicated subsequence is a subsequence of $S$ in the form of $x_1^{d_1}x_2^{d_2}\cdots x_k^{d_k}$ with $x_i\inΣ$, $x_j\neq x_{j+1}$ and $d_i\geq 2$ for all $i$ in $[k]$ and $j$ in $[k-1]$. A linear time algorithm for computing the longest letter-duplicated subsequence (LLDS) of $S$ can be easily obtained. In this paper, we focus on two variants of this problem. We first consider the constrained version when $Σ$ is unbounded, each letter appears in $S$ at least 6 times and all the letters in $Σ$ must appear in the solution. We show that the problem is NP-hard (a further twist indicates that the problem does not admit any polynomial time approximation). The reduction is from possibly the simplest version of SAT that is NP-complete, $(\leq 2,1,\leq 3)$-SAT, where each variable appears at most twice positively and exact once negatively, and each clause contains at most three literals and some clauses must contain exactly two literals. (We hope that this technique will serve as a general tool to help us proving the NP-hardness for some more tricky sequence problems involving only one sequence -- much harder than with at least two input sequences, which we apply successfully at the end of the paper on some extra variations of the LLDS problem.) We then show that when each letter appears in $S$ at most 3 times, then the problem admits a factor $1.5-O(\frac{1}{n})$ approximation. Finally, we consider the weighted version, where the weight of a block $x_i^{d_i} (d_i\geq 2)$ could be any positive function which might not grow with $d_i$. We give a non-trivial $O(n^2)$ time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of $S$ whose weight is maximized.