1 Introduction↩︎

Assume a codeword \(\boldsymbol{x}\) from a given code \(\mathcal{C}\) is transmitted via several identical channels, where each channel produces a noisy read of \(\boldsymbol{x}\). The sequence reconstruction problem, first proposed in 2001 by Levenshtein [2], asks for how to uniquely reconstruct \(\boldsymbol{x}\) in the worst case based on these multiple noisy reads. In particular, when the number of reads is only one, then unique reconstruction can be guaranteed if and only if \(\mathcal{C}\) is chosen as an classical error-correcting code for this channel. Recently, the sequence reconstruction problem gained renewed interest, mostly due to the development of DNA storage [3]–[10]. In current DNA storage techniques, each DNA string is amplified into a large number of copies via PCR, and then multiple noisy copies of the same string, after sequencing and clustering, could be read. Using these reads to reconstruct the original DNA string is exactly the sequence reconstruction problem.

In his seminal work [2], Levenshtein provided a proof of the fact that the minimum number of distinct reads which guarantees unique reconstruction is \(N+1\), where \(N\) is the maximum size of the intersection of any two error balls centered at two distinct codewords from \(\mathcal{C}\). Here, the error ball centered at a codeword \(\boldsymbol{x}\) refers to the set of all possible outputs of the channel when transmitting \(\boldsymbol{x}\). The value \(N\) is usually referred to as the unique reconstruction threshold. Levenshtein calculated this value for various channels with a single type of error, such as substitutions, transpositions, asymmetric errors, deletions, insertions, etc. [2]. Following Levenshtein, most works on sequence reconstruction are devoted to the combinatorial problem of calculating \(N\), for given channels and codes \(\mathcal{C}\), and then design corresponding efficient reconstruction algorithms when the number of reads exceeds the unique reconstruction threshold [11]–[21].

While studying the unique reconstruction threshold is of its own combinatorial interest, the aim of this paper is to seek new sufficient (and even necessary, if possible) conditions other than Levenshtein’s threshold, for unique reconstruction. There are at least three motivations. First, the threshold value \(N\) is usually at least a polynomial of the codeword length \(n\), and thus becomes impractically large as \(n\) grows. Second, Levenshtein’s threshold is indeed a worst-case analysis for the reconstruction problem (in the sense that we must collect enough reads for reconstruction), and it is natural to consider the following problem: When the number of reads is less than the threshold, is there any way to answer efficiently whether unique reconstruction is possible? And if so, what are the additional desired properties which could guarantee unique reconstruction? Finally, the number of reads for a given string is not a mechanism we can completely control in current DNA sequencing technology (It is possible to control how many reads in total are going to be sampled, but not how many reads we will collect for each strand [22]), and thus we should analyze whether unique reconstruction is possible when we read less than the threshold for some strands.

In this paper, we focus on the binary substitution channel and propose a new sufficient condition for unique reconstruction, which takes both the number of reads and the distances among the reads into consideration. Informally, our framework is based on the following observation: If a set of reads lie in the intersection of two error balls centered at two distinct codewords, then the distribution of these reads should be relatively concentrated. Our main contributions and some highlights are summarized as follows:

• For two codewords \(\boldsymbol{x}\) and \(\boldsymbol{y}\) of length \(n\) with minimum distance \(d\), and the substitution channel with at most \(t\geq \lceil \frac{d}{2} \rceil\) errors, we propose the concept of \(D(n,m,t,d)\) to be the maximum value of the sum of the pairwise distances among \(m\) distinct sequences in \(B_t(\boldsymbol{x})\cap B_t(\boldsymbol{y})\). Detailed theoretical analysis on \(D(n,m,t,d)\) is given.

• We propose a new sufficient condition for unique reconstruction: The summation of pairwise distances among a given set of \(m\) reads exceeds the value \(D(n,m,t,d)\). In other words, such a set of reads cannot lie in the intersection of two error balls centered at two distinct codewords, and thus unique reconstruction is theoretically guaranteed. Note that compared with Levenshtein’s reconstruction threshold, our condition is a function of the actual reads and could work even if the number of reads is way less than Levenshtein’s threshold.

• We also provide reconstruction algorithms corresponding to our new condition. In the algorithms we discuss how to reconstruct the original sequence based on a set of reads triggering the condition (referred to as a triggering set), as well as how to find such a triggering set among a large set of reads. For the latter there are two interesting cases: either we may find a triggering subset among a large non-triggering set of reads, or we may transform a non-triggering set into a triggering multi-set.

It is worth mentioning some related works. One related parallel work [23] assumes that the noisy reads are received sequentially and the decoder applies the majority decoding algorithm, and then the expected number of reads until successful reconstruction is studied. Several papers have considered the list reconstruction problem [17], [24]–[26], in which the decoder only needs to generate a list with a predetermined size containing the correct transmitted codeword. In particular, in  [25], [26] the authors also considered the distance between the reads, and analyzed how to use two distinct reads with large distance to obtain a (short) list of candidate codewords. Meanwhile, the sequence reconstruction problem has also been considered in slightly different settings. The trace reconstruction problem is a variant which considers probabilistic channels (where each bit is erroneous with a certain probability) instead of combinatorial channels (where there is an upper bound on the number of errors) [27]–[32]. Another related line of work studies reconstruction from multiple noisy views, in which the same underlying sequence is observed through several independent stochastic channels, and the goal is to characterize how these views jointly reduce uncertainty and improve recoverability (see [33]–[37]).

The rest of the paper is organized as follows. Section 2 introduces the relevant notations and the general framework of our new sufficient condition for unique reconstruction. In Section 3 we present the theoretical analysis for the parameters in our sufficient condition, and the corresponding reconstruction algorithm is presented in Section 4. Section 5 contains more discussions about the difficulty to characterize equivalent conditions for unique reconstruction. Finally Section 6 concludes the paper with a list of open problems.

2 Preliminaries and Basic Results↩︎

For integers \(m < n\), let \([m, n] = \{m, m+1, \ldots, n\}\) and denote \([1, n]\) as \([n]\) for short. For any set \(A\), let \(|A|\) be the size of \(A\), and for any \(a\in [0, |A|]\), let \(\binom{A}{a}\) be the family of all subsets of \(A\) of size \(a\). We use \(\{\{\cdot\}\}\) to denote a multiset. Let \(\Sigma_2 = \{0, 1\}\) be the binary alphabet and \(\Sigma_2^n\) be the set of sequences of length \(n\) over \(\Sigma_2\). For two sequences \(\boldsymbol{x}\) and \(\boldsymbol{y}\), let \(\boldsymbol{x}\boldsymbol{y}\) be the concatenation of \(\boldsymbol{x}\) and \(\boldsymbol{y}\), and let \(\boldsymbol{x}^n\) be the concatenation of \(n\) copies of \(\boldsymbol{x}\) itself. Specifically, \(\boldsymbol{x}^0\) is the empty string \(\boldsymbol{\epsilon}\). For two sequences \(\boldsymbol{x}= (x_1, x_2, \ldots, x_n)\) and \(\boldsymbol{y}= (y_1, y_2, \ldots, y_n)\), let \(d_H(\boldsymbol{x}, \boldsymbol{y})\) be the Hamming distance between \(\boldsymbol{x}\) and \(\boldsymbol{y}\), i.e., \(d_H(\boldsymbol{x}, \boldsymbol{y}) = |\{i\in [n]:x_i\neq y_i\}|\). Let \(B_t(\boldsymbol{x})\) be the Hamming ball of radius \(t\) centered at \(\boldsymbol{x}\), i.e., \(B_t(\boldsymbol{x}) = \{\boldsymbol{y}\in\Sigma_2^n: d_H(\boldsymbol{x}, \boldsymbol{y})\leq t\}\). A code \(\mathcal{C}\) is a subset of \(\Sigma_2^n\), and the minimum Hamming distance of a code \(\mathcal{C}\) is the minimum Hamming distance between any two distinct codewords in \(\mathcal{C}\). For \(\boldsymbol{x}= (x_1, x_2, \ldots, x_n)\in\Sigma_2^n\) and \(S\subseteq[n]\), let \(\boldsymbol{x}_S\) be the projection of \(\boldsymbol{x}\) onto the coordinates \(S\).

The sequence reconstruction problem for substitution errors was first proposed by Levenshtein [2]. Let \(\mathcal{C}\) be a code in \(\Sigma_2^n\) with minimum Hamming distance \(d\). Assume that a codeword \(\boldsymbol{x}\in\mathcal{C}\) is transmitted through several substitution channels, where each channel can cause at most \(t\) substitution errors, i.e., the output set of the noisy reads is a subset of \(B_t(\boldsymbol{x})\). When \(t<\left\lceil \frac{d}{2} \right\rceil\), by the property of error-correcting codes one can decode \(\boldsymbol{x}\) from any single output in \(B_t(\boldsymbol{x})\). Thus, in the reconstruction problem, we always focus on the case \(t\geq \left\lceil \frac{d}{2} \right\rceil\). Furthermore, in Levenshtein’s reconstruction problem, it is assumed that the channels produce distinct outputs. In this paper, we adhere to these two assumptions unless otherwise stated. The goal is to reconstruct \(\boldsymbol{x}\) by multiple distinct noisy copies. In [2], it was shown that if the number of outputs is at least \(N(n, t, d) + 1\), where \[N\left(n, t, d\right) \triangleq \max_{\boldsymbol{x}\neq\boldsymbol{y}\in\Sigma_2^n, d_H\left(\boldsymbol{x}, \boldsymbol{y}\right) = d}\left\{|B_t\left(\boldsymbol{x}\right)\cap B_t\left(\boldsymbol{y}\right)|\right\},\] then unique reconstruction of the original sequence is guaranteed. It has been proved by Levenshtein in [2] that \[N\left(n, t, d\right)=\sum_{i=0}^{t-\left\lceil\frac{d}{2}\right\rceil}\binom{n-d}{i} \sum_{h=d-t+i}^{t-i}\binom{d}{h},\] and we refer to this value as the unique reconstruction threshold.

A common reconstruction algorithm in the sequence reconstruction problem for the substitution channel is the majority decoding algorithm, defined as follows.

It can be easily checked that when \(\mathcal{C}\) is the whole space \(\Sigma_2^n\) (then \(d = 1\)), given a set of reads \(\{\boldsymbol{z}_1,\dots,\boldsymbol{z}_m\}\subseteq B_t(\boldsymbol{x})\) with \(m=N(n, t, 1) + 1\), the reconstruction of \(\boldsymbol{x}\) can be simply done by the majority decoding algorithm, since for each coordinate the majority decoding algorithm produces the correct value. The majority decoding algorithm and its variations have been widely used in the reconstruction of substitution errors [16], [24], [26].

Reading \(N(n, t, d) + 1\) distinct noisy copies is one sufficient condition for unique reconstruction in the worst case. However, the value \(N(n, t, d)\) becomes impractically large as \(n\) grows. When the number of reads is less than the unique reconstruction threshold, is it possible to characterize some other sufficient (and even necessary, if possible) conditions for unique reconstruction? Say we transmit a codeword \(\boldsymbol{x}\in \mathcal{C}\) and have a set of reads \(\{\boldsymbol{z}_1,\dots,\boldsymbol{z}_m\}\subseteq B_t(\boldsymbol{x})\). A straightforward way is to check whether \(\bigcap_{i = 1}^{m}B_t(\boldsymbol{z}_i)\cap \mathcal{C}\) contains exactly one codeword. However, this method is highly inefficient as the size of each Hamming ball is a polynomial of \(n\). It is desirable to have simpler conditions for unique reconstruction. To the best of our knowledge, this type of problem is rarely considered and seems rather non-trivial. In this paper, we initiate the research on this problem, by proposing a sufficient condition which takes both the number of reads and the distances among the reads into consideration. The key idea originates from the observation of the following extreme case, when three reads are already enough for unique reconstruction.

Although this special case may seem trivial, it can be easily shown that when \(t\) is a fixed constant, \(n\) is large enough, and the three reads are uniformly distributed in the ball \(B_t(\boldsymbol{x})\), the condition of Lemma 1 holds with high probability.

The proof of this lemma, as well as some other probabilistic arguments of the paper, are left in the appendices. Inspired by Lemma 1, we propose the following problem.

The trivial condition that solves Problem 1 is that the set of words \(\{ \boldsymbol{z}_1, \ldots, \boldsymbol{z}_m \}\) belongs to the radius-\(t\) ball of exactly one codeword. However, complexity wise this is not a feasible solution. Hence, we seek for a sufficient (and even necessary, if possible) condition that will be complexity-wise efficient, and the first thought that comes into mind is a characterization of the pairwise distance among the reads. Here we propose a sufficient condition, which is based on the summation of the pairwise distance among the reads. The following definition plays a key role in our framework.

With the help of the notation \(D(n, m, t, d)\), our reconstruction condition is of the following form.

Theorem 1 provides a sufficient condition to Problem 1 and indicates that once we have \(m\) distinct reads and the sum of their pairwise distance is strictly larger than \(D(n,m,t,d')\) for every \(d'\geq d\), then these reads cannot lie in the intersection of two error balls centered at two distinct codewords from a code with minimum Hamming distance \(d\). Therefore, unique reconstruction is guaranteed. Note that for now we need to check Inequality (?? ) for every \(d'\geq d\), since we are still unaware of the monotonicity of the values \(\{D(n,m,t,d')\}_{d'\geq d}\) yet. After the theoretical analysis of these values in the next section, for a certain range of parameters we can modify Theorem 1 and only need to check the inequality once, for either \(d\) or \(d+1\).

3 Theoretical Analysis of the Value \(D(n, m, t, d)\)↩︎

In this section, we analyze the value \(D(n, m, t, d)\). Throughout the rest of the paper, we set \(\boldsymbol{x}=(x_1,\dots,x_n)\) to be the transmitted codeword, \(\boldsymbol{y}=(y_1,\dots,y_n)\) to be the other codeword with \(d_H(\boldsymbol{x},\boldsymbol{y})=d\), and \(\{\boldsymbol{z}_1,\ldots,\boldsymbol{z}_m\}\subseteq B_t(x)\) to be the reads where \(\boldsymbol{z}_i=(z_{i,1},\ldots,z_{i,n})\) for \(i\in[m]\). Let \(S_i\) be the coordinates where \(\boldsymbol{z}_i\) and \(\boldsymbol{x}\) differ, i.e. \(S_i = \{k\in[n]: z_{i, k}\neq x_k\}\). For each coordinate \(k\in[n]\), let \(c_k\) be the number of sequences among \(\{\boldsymbol{z}_1,\dots,\boldsymbol{z}_m\}\) which are different from \(\boldsymbol{x}\) at the coordinate \(k\). The following Lemma 3, which essentially follows a double counting argument, plays a crucial role in the subsequent analysis.

Lemma 4 is useful when analyzing the value \(D(n, m, t, d)\).

3.1 Exact value of \(D(n, m, t, d)\) when \(n\geq m\left(t-\left\lceil\frac{d}{2}\right\rceil\right)+d\)↩︎

With Lemmas 3 and 4, the value of \(D(n, m, t, d)\) can be exactly determined when \(n\geq m\left(t-\left\lceil\frac{d}{2}\right\rceil\right)+d\) as follows.

With Theorem 2, we are ready to determine the value \(\max_{d'\geq d}\{D(n, m, t, d')\}\) for the case \(t\geq \left\lceil \frac{d}{2} \right\rceil\) and \(n\geq m\left(t-\left\lceil\frac{d}{2}\right\rceil\right)+d\).

Now we are ready to revisit the general framework of our reconstruction condition, Theorem 1, into the following simpler form, which means that it suffices to check only one inequality to decide whether unique reconstruction is possible.

Similar as Lemma 2, in fact the unique reconstruction condition holds with high probability. The proof of the next lemma is also left in the appendix.

3.2 A general upper bound of \(D(n, m, t, d)\)↩︎

In the previous subsection, we determined the value of \(D(n, m, t, d)\) when \(n\geq m\left(t-\left\lceil\frac{d}{2}\right\rceil\right)+d\), or equivalently, when \(m\leq \frac{n-d}{t-\left\lceil \frac{d}{2} \right\rceil}\). As \(m\) grows larger, the upper bound in Inequality (1 ) cannot be achieved anymore, since the sets \(\{S''_i:1\leq i\leq m\}\) cannot be pairwise disjoint. Therefore, the upper bound in Inequality (1 ) could be further reduced. In this subsection, we present a general upper bound of \(D(n, m, t, d)\) for arbitrary \(n\) and \(m\). While the upper bound follows a similar approach as the previous subsection, analyzing whether the upper bound can be achieved turns out to be more complicated.

Establishing the tightness of the general upper bound in Theorem 4 requires us to, similarly as in the proof of Theorem 2, find an example consisting of \(m\) distinct reads, such that

• For each \(k\in [d]\), \(c_k = \left\lceil\frac{m}{2}\right\rceil\) or \(c_k=\left\lfloor \frac{m}{2}\right\rfloor\).

• For each \(k\in [d+1, n]\), \(c_k\) are almost equal and \(\sum_{k=d + 1}^{n} c_k = m\left(t-\left\lceil\frac{d}{2}\right\rceil\right).\)

This construction turns out to be nontrivial in general, where the distinctness of the reads is the main difficulty. Nevertheless, we can show the tightness under an additional divisibility condition \((t-\lceil\frac{d}{2}\rceil)\mid (n-d)\). We need the famous Baranyai’s Theorem [38] from combinatorial design theory. In design theory, a parallel class refers to a set of \(N/K\) \(K\)-subsets which form a partition of an \(N\)-set, when \(K\) divides \(N\). The Baranyai’s Theorem is as follows.

By Baranyai’s Theorem we have the following result.

4 Explicit Reconstruction Algorithms↩︎

In this section, we introduce the explicit reconstruction algorithms corresponding to our reconstruction condition. This section is further divided into three subsections. The first subsection introduces the reconstruction algorithm when a set of reads triggering our unique reconstruction condition, abbreviated as a triggering set, is given. The second subsection discusses how to find such a triggering set among a large number of reads. The third subsection considers the case when repeated reads are allowed and thus a triggering multi-set can also be used for reconstruction.

4.1 The reconstruction algorithm with a triggering set↩︎

For a code \(\mathcal{C}\subseteq\Sigma_2^n\) with minimum Hamming distance \(d\), let \(\mathcal{D}_{\mathcal{C}}\) be the minimum distance decoder corresponding to \(\mathcal{C}\), i.e., for any \(\boldsymbol{x}\in \mathcal{C}\) and \(\boldsymbol{y}\in B_{\left\lfloor\frac{d-1}{2}\right\rfloor}(\boldsymbol{x})\), \(\mathcal{D}_{\mathcal{C}}(\boldsymbol{y}) = \boldsymbol{x}\). Algorithm 1 works when we have a set of reads which have triggered the unique reconstruction condition presented in Theorem 3.

Algorithm 1 first applies a majority voting method, with a pre-set parameter \(\tau\), to determine each coordinate as \(0\), \(1\), or an undetermined value denoted by a question-mark. Here, a coordinate will be determined as a question-mark if the number of appearances of 0 and 1 at this coordinate among the reads do not differ too much, with respect to the parameter \(\tau\). After Step \(20\), a sequence \(\boldsymbol{z}\in\{0,1,?\}^n\) is generated. Then a brute-force search is run over all possible values on the undetermined coordinates of \(\boldsymbol{z}\), and the decoder of \(\mathcal{C}\) is applied to get many candidates. For each candidate \(\widehat{\boldsymbol{x}}\), in Step \(24\) Algorithm 1 checks if all the reads belong to the error ball centered at \(\widehat{\boldsymbol{x}}\). When the unique reconstruction condition is satisfied, we can prove that by selecting the appropriate parameter \(\tau\), exactly one candidate \(\widehat{\boldsymbol{x}}\) reveals and it is exactly the desired \(\boldsymbol{x}\). It should be noted that the majority voting method with a pre-set parameter \(\tau\) is not new. It first appeared in [24] and later in other papers about sequence reconstruction such as [16].

Since there is a brute-force search module in the algorithm, its complexity highly depends on the size of \(F\), which is upper bounded as follows.

With the two lemmas above, the following theorem holds for our reconstruction algorithm.

Furthermore, if the reads have better properties, in the sense that \(\sum_{i<j}d_H(\boldsymbol{z}_i, \boldsymbol{z}_j)\) is even larger, then we may discard the parameter \(\tau\) and simply run a majority-vote (in the event of a tie on any coordinate, set it as \(0\) or \(1\) arbitrarily) to get a sequence \(\boldsymbol{z}\in\{0,1\}^n\). Apply the decoder \(\mathcal{D}_\mathcal{C}\) on \(\boldsymbol{z}\) will directly lead to the desired \(\boldsymbol{x}\). This process is formalized in the next theorem.

4.2 Finding a triggering set from a larger number of reads↩︎

In the previous subsection we assume that a triggering set is given. When we obtain a set of \(M\) reads \(\{\boldsymbol{z}_1, \ldots, \boldsymbol{z}_M\} \subseteq B_t(\boldsymbol{x})\), how do we find such a triggering set among these reads? One may suggest to simply check the summation of the pairwise distance of all the \(M\) reads. However, this is not always the best strategy. We offer an example as follows.

Motivated by this example, in this subsection we discuss how to find a subset of \(m\) reads among the \(M\) available reads which can be used to uniquely reconstruct \(\boldsymbol{x}\). We describe the general problem in a weighted graph model as follows.

• The weighted clique problem: Consider a complete graph \(K_M\) where each edge is assigned a nonnegative weight. Given \(D\) and \(m\), with \(m\leq M\), find a clique of size \(m\) in which the summation of all edge-weights is larger than \(D\).

• The Hamming weighted clique problem: Consider a set of \(M\) sequences from \(\Sigma_2^n\) and let them be the vertex set of a complete graph \(K_M\). Assign each edge \(\{\boldsymbol{x},\boldsymbol{y}\}\) with weight \(d_H(\boldsymbol{x},\boldsymbol{y})\). Given \(m\leq M\), find a clique of size \(m\) in which the summation of all edge-weights is larger than \(D(n,m,t,d)\).

By the following simple reduction to the Clique problem of graphs, it can be shown that the weighted clique problem is an NP-hard problem.

Given the analysis above, to find a triggering set among a large set of reads is a nontrivial task. We close this subsection by introducing a pruning strategy to find triggering sets.

Following the similar idea, it is routine to show that for any \(m\) sequences with the summation of their pairwise distance being at least \(\frac{m(m-1)}{M(M-1)}D(n,M, t, 2\left\lceil\frac{d}{2}\right\rceil)\), there exists a subset of \(m-1\) sequences with the summation of their pairwise distance being at least \(\frac{(m-1)(m-2)}{M(M-1)}D(n,M, t, 2\left\lceil\frac{d}{2}\right\rceil)\). By Lemma 10, given a set of \(M\) reads, we proceed as follows.

• If \(\sum_{1\leq i < j\leq M} d_H(\mathbf{z}_i, \mathbf{z}_j) > D\left(n, M, t, 2\left\lceil \tfrac{d}{2} \right\rceil\right)\), Algorithm 1 is applied to reconstruct \(\boldsymbol{x}\). Otherwise, \(M\) is decremented by one and the procedure continues to the subsequent steps to seek for a triggering subset.

• Let \(S_3 = \varnothing\). Check all triples of reads \(\{\boldsymbol{z}_i,\boldsymbol{z}_j,z_k\}\). If the summation of their pairwise distance is strictly larger than \(D(n,3,t,2\left\lceil\frac{d}{2}\right\rceil)\), then a triggering set of size 3 has been found. Otherwise, if the summation of their pairwise distance is strictly larger than \(\frac{6 D\left(n,M, t, 2\left\lceil\frac{d}{2}\right\rceil\right)}{M(M-1)}\), then let \(S_3=S_3\cup \{\{i,j,k\}\}\).

• Recursively perform the following steps. For every \(4\leq m\leq M\), set \(S_m=\varnothing\). For all sets \(A\in S_{m-1}\) and \(i\notin A\), consider the union \(A\cup\{i\}\). If the summation of the pairwise distance among the reads indexed by \(A\cup\{i\}\) is strictly larger than \(D(n,m,t,2\left\lceil\frac{d}{2}\right\rceil)\), then a triggering set of size \(m\) has been found. Otherwise, if the summation of their pairwise distance is strictly larger than \(\frac{m\left(m - 1\right)D\left(n,M, t, 2\left\lceil\frac{d}{2}\right\rceil\right)}{M(M-1)}\), then let \(S_m=S_m\cup \{A\cup \{i\}\}\).

While many branches have been pruned during the search for triggering sets, Lemma 10 assures that if there is indeed a triggering set \(A\) of size \(m\), then for any \(3\leq m' <m\), there is a at least one subset of \(A\) in \(S_{m'}\). Thus, the search process will output the triggering set as desired. Moreover, if there is no such triggering set, then at some step the set \(S_{m'}\) becomes empty and the search process stops. Once a triggering set is found, Algorithm 1 in the previous subsection will be applied for unique reconstruction.

4.3 Reconstruction with repeated reads↩︎

In Levenshtein’s seminal work [2], it is assumed that the reads from all channels are distinct. This assumption makes sense for the study of the unique reconstruction threshold. Up to this point in the paper we have also adhered to this assumption. However, looking back on all the proofs in the previous sections, we do not need this assumption at all! In other words, our general framework and algorithms also work when we are given a set of reads with repetitions. In fact, by allowing repeated reads, the only thing that could be affected (in a good way) is the upper bound in Theorem 4, in the sense that the upper bound can be easier to achieve.

What is more unexpected is that we can artificially make repeated reads, to change a non-triggering set of reads into a triggering multi-set. Here is an example.

As the example suggests, in our unique reconstruction framework, repeated reads are allowed and we can even artificially make repeated reads to trigger unique reconstruction conditions. Our general framework can be adapted to the following version.

Look back on Example 7. While we have interpreted it as an example that repeated reads could constitute a triggering multi-set, one may have observed that another explanation is that the first three reads already constitute a triggering set of size three. Given a set of \(M\) distinct reads which is not a triggering set itself, either we may try to find a smaller triggering set as in Subsection 4.2, or we may try to artificially repeat some of the reads to find a triggering multi-set. It is not obvious which way performs better, and we conjecture that if one way works then the other way will also work.

5 Further discussions on equivalent conditions of unique reconstruction↩︎

Levenshtein’s reconstruction threshold and our framework in this paper are two sufficient conditions for unique reconstruction. It is natural to ask if we can characterize a both sufficient and necessary condition, i.e., an equivalent condition, for unique reconstruction.

Consider the case when \(\mathcal{C}=\Sigma_2^n\). Suppose there are only two reads \(\{\boldsymbol{z}_1,\boldsymbol{z}_2\}\subseteq B_t(\boldsymbol{x})\). One can find many candidates \(\boldsymbol{y}\) as follows. For all the coordinates that \(\boldsymbol{z}_1\) and \(\boldsymbol{z}_2\) agree, let \(\boldsymbol{y}\) also have the same symbol. For all the coordinates that \(\boldsymbol{z}_1\) and \(\boldsymbol{z}_2\) differ, let \(\boldsymbol{y}\) have the same symbols as \(\boldsymbol{z}_1\) on a random subset of half of the coordinates and let \(\boldsymbol{y}\) have the same symbols as \(\boldsymbol{z}_2\) on the other half. Then it is routine to check that \(\{\boldsymbol{z}_1,\boldsymbol{z}_2\}\subseteq B_t(\boldsymbol{y})\). Therefore, with only two reads \(\{\boldsymbol{z}_1,\boldsymbol{z}_2\}\), one can never guarantee unique reconstruction.

For \(m=3\) and \(\mathcal{C}=\Sigma_2^n\), recall that we have discussed this case earlier in Lemma 1 as a toy example. Next we present an equivalent condition for unique reconstruction for \(m=3\) and \(\mathcal{C}=\Sigma_2^n\).

What about the next case \(m=4\) for \(\mathcal{C}=\Sigma_2^n\)? We have the following facts:

• Fact 1: Our reconstruction condition in Theorem 3 states that for four reads, a sufficient condition for unique reconstruction is that the summation of their pairwise distance is at least \(D(n,4,t,2)+1=12t-3\).

• Fact 2: When the summation is \(12t-4\), we can construct a case which does not guarantee unique reconstruction. Consider \(\boldsymbol{x}=0^n\) and four reads \(\{\boldsymbol{z}_1,\boldsymbol{z}_2,\boldsymbol{z}_3,\boldsymbol{z}_4\}\subseteq B_t(\boldsymbol{x})\) with support sets \(S_1,S_2,S_3,S_4\), all of size exactly \(t\). Let \(|S_1\cap S_2|=1\), \(|S_3\cap S_4|=1\), and \(S_1\cup S_2\) be disjoint from \(S_3\cup S_4\). In this case the summation of the pairwise distance is \(12t-4\). Pick the coordinate \(i\in S_1\cap S_2\) and \(j\in S_3\cap S_4\), and let \(\boldsymbol{y}\) be the sequence with support set \(\{i,j\}\). Then it holds that \(\{\boldsymbol{z}_1,\boldsymbol{z}_2,\boldsymbol{z}_3,\boldsymbol{z}_4\}\subseteq B_t(\boldsymbol{y})\) and thus unique reconstruction is not possible.

• Fact 3: A uniquely reconstructible case could have a distance summation as small as \(10t\). \(S_1,S_2,S_3\) are of size \(t\) and mutually disjoint (and thus these three reads already guarantees unique reconstruction), and \(S_4\) has a \(t/3\)-intersection with all the other three.

Considering these facts, it seems very difficult to characterize the equivalent condition for unique reconstruction, even for the case \(m=4\). In particular, when the summation of pairwise distance among the four reads is in the range \([10t,12t-4]\), determining whether unique reconstruction is possible may require a complicated case-by-case analysis.

6 Conclusion↩︎

In this paper, we prose a new framework for unique sequence reconstruction for the substitution channel. Our new sufficient condition takes both the number of reads and the summation of pairwise distance among the reads into consideration. We discuss how to find a set of reads from all available reads which can trigger our sufficient condition, and offer an efficient corresponding reconstruction algorithm when a triggering set is given. The following problems are considered for future research:

• Determine the exact value of \(D(n,m,t,d)\) when \(n\) is less than \(m\left(t-\left\lceil\frac{d}{2}\right\rceil\right)+d\).

• Find a more efficient way to identify a triggering set from a large set of reads.

• Analyze more sufficient conditions for unique reconstruction. In particular, analyze equivalent conditions for unique reconstruction starting from the case \(m=4\) and \(\mathcal{C}=\Sigma_2^n\).

• Analyze sufficient conditions for unique reconstruction in other channels such as deletion and insertion channels.

7 Probability for triggering the unique reconstruction conditions↩︎

In the appendices we present the proofs of the probabilistic arguments throughout the paper.

References↩︎

---

1. Chen Wang and Yiwei Zhang were supported in part by National Key Research and Development Program of China under Grant Nos. 2022YFA1004900 and 2021YFA1001000, in part by National Natural Science Foundation of China under Grant No. 12231014, and in part by Taishan Scholars Program. The research of Chen Wang was also supported in part at the Technion by a fellowship from the Lady Davis Foundation. The work of Eitan Yaakobi was Funded by the European Union (ERC, DNAStorage, 101045114 and EIC, DiDAX 101115134). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Part of this paper [1] has been presented in ITW2024. Corresponding author: Yiwei Zhang.↩︎

2. Chen Wang and Yiwei Zhang are with State Key Laboratory of Cryptography and Digital Economy Security, Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, 266237, China (e-mail: cwang2021@mail.sdu.edu.cn, ywzhang@sdu.edu.cn).↩︎

3. Eitan Yaakobi is with the Department of Computer Science, Technion — Israel Institute of Technology, Haifa 3200003, Israel (e-mail: yaakobi@cs.technion.ac.il)↩︎

4. BIBD is short for balanced incomplete block designs. A \((v,k,\lambda)\)-BIBD is a family of \(k\)-subsets (called blocks) of a \(v\)-set, such that every two elements appear together in exactly \(\lambda\) blocks.↩︎