CCP-DP: Cross-cluster context-guided phase dynamic programming for DNA storage sequence reconstruction

Zixin Zhang, Guanjin Qu, Huaming WuarXiv 2026 · arXiv

TL;DR

CCP-DP is a novel framework for DNA data storage reconstruction that breaks the "one cluster at a time" mold. By leveraging shared sequence patterns across an entire dataset (cross-cluster context), it significantly improves reconstruction accuracy in high-noise, low-coverage scenarios where traditional local-only methods fail.

What Problem Does This Paper Address?

DNA data storage is a promising frontier for long-term, high-density archiving, but it’s a noisy business. The process of synthesizing, storing, and sequencing DNA introduces insertions, deletions, and substitutions (IDS errors). To recover the original data, researchers typically group similar reads into "clusters" and try to find a consensus sequence for each.

The challenge arises when sequencing coverage is low (e.g., only 5 reads per original sequence) or when errors are so frequent that they cause "phase shifts"—where the sequence alignment gets completely out of sync. Most existing tools look only at the evidence within a single cluster. If that cluster is small or particularly messy, there simply isn't enough local information to reconstruct the original sequence accurately.

Methods

The authors propose Cross-Cluster Context-Guided Phase Dynamic Programming (CCP-DP). The core philosophy is that clusters within the same dataset often share similar sequence contexts and undergo the same error-prone processes.

The framework operates in three main stages, as illustrated in the overview below:

Overview of the CCP-DP framework, showing provisional consensus construction, cross-cluster estimation, and selective decoding.
  1. Provisional Consensus Construction: It first builds a "rough draft" for every cluster. It uses two different strategies depending on coverage: a k-mer phase chain for high-coverage clusters and a banded-evidence DP for lower-coverage ones.
  2. Cross-Cluster Context & IDS Estimation: This is the "aha!" moment. CCP-DP analyzes all the provisional drafts to build a global model of which DNA patterns (k-mers) are common across the dataset. It also performs "blind" estimation of the error channel (the rates of insertions, deletions, and substitutions) without needing the ground-truth sequences.
  3. Selective Structured Decoding: Instead of brute-forcing every sequence, the system identifies "anomalous" clusters that likely contain errors. These difficult cases are then refined using a Phase-Aware Trellis DP. This trellis integrates three sources of evidence: local read data, the global cross-cluster context, and the estimated error profile.

Datasets

The authors evaluated CCP-DP on four widely used public DNA storage datasets that represent different lengths and error characteristics:

  • Erlich-152 (152 bp)
  • Srinivas-110 (110 bp)
  • Chandak-108 (108 bp)
  • Chandak-150 (150 bp)

They also used synthetic datasets to stress-test the algorithm across various coverage levels (5× to 20×) and indel rates (2% to 10%).

Key Insights and Ideas

  • The "Wisdom of the Dataset": Even if a single cluster is too noisy to resolve, the statistical patterns found in the other thousands of clusters in the same experiment can act as a powerful prior to guide reconstruction.
  • Phase-Awareness is Crucial: Indels are the most damaging errors because they shift the "phase" of the sequence. By using a trellis that explicitly represents these shifts, CCP-DP can "re-sync" sequences that other methods would give up on.
  • Efficiency through Routing: By only applying the computationally expensive trellis DP to clusters flagged as "anomalous," the method maintains a low computational overhead, often running faster than simpler methods that process every cluster identically.
  • Training-Free Portability: Unlike recent deep-learning approaches that require training on specific datasets, CCP-DP estimates its parameters on-the-fly from the input data itself.

Key Results

CCP-DP consistently outperformed state-of-the-art baselines like BBS, CPL, and ITR.

  • Low-Coverage Dominance: The most significant gains were seen at 5× coverage, where CCP-DP improved exact reconstruction rates by 6.2 to 17.5 percentage points over the next best method.
  • High Accuracy: Across the main benchmarks, it achieved exact reconstruction rates between 95.36% and 99.98%.
  • Beating Deep Learning: In direct comparisons, CCP-DP achieved higher accuracy than DNAFormer and TReconLM on the Srinivas-110 and Chandak-108 datasets, despite being a training-free algorithmic approach.

As shown in Figure 2, the performance gap is most pronounced when data is scarce:

Exact reconstruction performance across sequencing coverages, showing CCP-DP's lead in low-coverage regimes.

Limitations and Future Work

While CCP-DP is robust, the authors note a few areas for improvement:

  • Context Dependency: The benefit of the cross-cluster model depends on the existence of shared sequence patterns. If a dataset consists of entirely unique, random sequences with no overlap in local context, the gains from this specific feature might diminish.
  • Extreme Noise: Under very high indel rates (e.g., 10%), the provisional guides themselves can become so corrupted that the global context model starts to degrade, leading to "negative gains" in some specific intermediate coverage levels.
  • Future Directions: The authors suggest exploring more flexible cross-cluster models and improving the confidence estimation used for the adaptive routing to further boost efficiency and accuracy.

Summary updated

Abstract

Motivation: DNA data storage offers high information density and long-term stability, but accurate sequence reconstruction remains challenging under limited sequencing coverage and strong insertion, deletion, and substitution (IDS) noise. Existing reconstruction methods mainly rely on local evidence within individual read clusters. When sequencing coverage is low or indel-induced phase shifts become pronounced, such local evidence may be insufficient to distinguish closely competing candidate sequences. Results: We present Cross-Cluster Context-Guided Phase Dynamic Programming (CCP-DP), which uses dataset-level cross-cluster information to complement cluster-local evidence and selectively refines ambiguous provisional consensuses. Under the main benchmark settings, CCP-DP achieved exact reconstruction rates of 95.36%-99.98% and outperformed existing methods on multiple datasets. At $5\times$ coverage, CCP-DP improved exact reconstruction by 6.2-17.5 percentage points over the stronger of BBS and CPL across the tested IDS conditions, while maintaining low reconstruction error and computational overhead. Overall, CCP-DP introduces cross-cluster shared information as a complementary source of evidence for DNA sequence reconstruction under challenging conditions. Availability: Source code is available at https://github.com/ZixinZ3899/CCP-DP.
BibTeX
@misc{zhang2026ccp,
  author = {Zixin Zhang and Guanjin Qu and Huaming Wu},
  title = {{CCP-DP: Cross-cluster context-guided phase dynamic programming for DNA storage sequence reconstruction}},
  year = {2026},
  eprint = {2610.36559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36559},
}
Figure