Algorithms for reconstruction over single and multiple deletion channels

Sundara Rajan Srinivasavaradhan, Michelle Du, Suhas N. Diggavi, Christina Fragouli

Abstract

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically:

  1. We show that solving for the ML estimate over the single deletion channel is equivalent to solving its relaxation, a continuous optimization problem;
  2. We exactly compute the symbolwise posterior distributions for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.

Problem Formulation

Reconstructing an original sequence from fragments with missing pieces (deletions) is a notoriously difficult combinatorial problem. A deletion channel randomly deletes bits from a binary message $X$ of length $n$, resulting in a shorter surviving sequence $Y$ of length $m$. Because the receiver does not know which bits were deleted, the channel possesses "memory," as a single deletion shifts the positions of all subsequent bits.

Single deletion channel model

In many practical scenarios, such as DNA data storage, the same message $X$ is sent multiple times, resulting in $t$ different surviving subsequences, or traces ($Y^1, Y^2, \dots, Y^t$). The challenge of estimating the original sequence from these traces is known as the trace reconstruction problem.

Multiple deletion channel model for trace reconstruction

While theoretical computer science often focuses on the asymptotic regime requiring thousands of traces for perfect reconstruction, this work addresses the practical case of a fixed, small number of traces. The authors focus on computing the Maximum Likelihood (ML) estimate—the sequence most likely to have produced the observed traces—and the Symbolwise Maximum A Posteriori (MAP) estimate—the most likely value for each individual bit.

Methodology

To overcome the combinatorial complexity of deletion channels, the authors introduce several mathematical innovations:

  • Relaxed Binomial Coefficient: The standard binomial coefficient counts subsequence occurrences. The authors develop a continuous, real-valued "relaxed" version that operates on bit probabilities rather than hard binary values.
  • Continuous Optimization for ML: They prove that the discrete ML problem is equivalent to its continuous relaxation. This allows the use of Projected Gradient Ascent to find high-quality ML estimates, bridging combinatorial sequence problems with continuous machine learning techniques.
  • Edit Graphs & Infiltration Products: Borrowing from algebraic combinatorics, the authors use edit graphs to map all possible alignments of multiple traces into a common supersequence.
  • Dynamic Programming for MAP: By traversing these edit graphs, they develop a dynamic programming algorithm to compute exact symbolwise MAP probabilities in polynomial time relative to sequence length.

Results and Insights

The authors evaluated their algorithms using simulated binary sequences of length $n=20$ and $n=100$ across varying deletion probabilities ($\delta$).

  • Computational Efficiency: The exact Symbolwise MAP algorithm achieves $O(n^2)$ time complexity for a single trace. For $t$ traces, the complexity is $O(2^t n^{t+2})$.
  • Accuracy and Optimality: The Symbolwise MAP estimate was proven to be mathematically optimal for minimizing the Hamming error rate. In simulations, the proposed methods (Exact MAP, Gradient Ascent, and a Sequential MAP heuristic) consistently outperformed existing baselines like Bitwise Majority Alignment.
  • Metric-Specific Performance: While Exact MAP excelled at minimizing Hamming errors, the continuous Gradient Ascent heuristic (designed for ML) surprisingly proved most effective at minimizing edit distance errors.

Conclusion and Future Work

This work provides a significant theoretical step forward for applications like nanopore sequencing. However, challenges remain. The exact Symbolwise MAP algorithm scales exponentially with the number of traces ($O(2^t)$), becoming computationally intractable beyond a few traces. Additionally, while the ML problem is mapped to a continuous domain, it remains a "signomial optimization" problem, which is generally NP-hard. Future research will focus on extending these algorithms to handle non-uniform input priors and improving scalability for larger trace sets.

Summary updated

Abstract

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels.
BibTeX
@article{srinivasavaradhan2021algorithms,
  author = {Sundara Rajan Srinivasavaradhan and Michelle Du and Suhas N. Diggavi and Christina Fragouli},
  title = {{Algorithms for reconstruction over single and multiple deletion channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=wVdUe3F2Wa},
}
Figure