PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zixin Zhang, Guanjin Qu, Huaming Wu

arXiv:2610.36559v1cs.IR

TL;DR

DNA sequence reconstruction remains challenging under limited coverage and IDS noise, while cluster-local evidence may not distinguish similar candidates. CCP-DP adds cross-cluster context and IDS information to selectively refine ambiguous consensuses. Across multiple real DNA storage datasets and sequencing conditions, it achieves consistently high exact reconstruction accuracy while maintaining low residual error and computational cost.

  • Problem

    Low coverage and IDS-induced misalignment can leave cluster-local evidence insufficient to distinguish similar candidate sequences.

    Source: §1 · pp. 1, 3

  • Method

    CCP-DP combines dataset-level cross-cluster context and IDS statistics with cluster-local reconstruction, selectively refining uncertain provisional consensuses.

    Source: §1 · p. 3, §2 · p. 3

  • Results

    Across multiple real DNA storage datasets and diverse sequencing conditions, CCP-DP achieves consistently high exact reconstruction accuracy while maintaining low residual error and computational cost.

    Source: §4 · p. 10

  • Takeaways & Limitations

    Reusable sequence context across clusters can provide complementary evidence when cluster-local observations are insufficient for DNA trace reconstruction.

    Source: §4 · p. 10

    CCP-DP’s statistical and computational advantages may be reduced when reusable cross-cluster patterns are weak or difficult clusters are widespread.

    Source: §4 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

DNA storage reconstruction must contend with IDS errors and limited coverage, while existing methods rely mainly on evidence within each read cluster. CCP-DP adds dataset-level cross-cluster context and IDS statistics to help reconstruct difficult clusters.

1 Introduction

  • Low coverage and complex insertion, deletion, and substitution errors make accurate and efficient DNA sequence reconstruction challenging.Nanopore sequencing is described as having higher IDS error rates and more complex error patterns, particularly insertions and deletions.Source: §1 · p. 1
  • Existing methods rely mainly on target-cluster evidence, which may not distinguish similar candidates when local observations are limited or reads are misaligned.Clusters in the same dataset can share channel error mechanisms and recurring sequence contexts, providing additional evidence that existing methods have not fully exploited.Source: §1 · pp. 2–3
  • CCP-DP uses dataset-level cross-cluster contextual information and IDS statistics as additional evidence for reconstructing difficult clusters.The introduction situates this approach among alignment, trellis, iterative, graph-search, and deep-learning reconstruction methods.Source: §1 · pp. 1–3

2 Materials and methods

CCP-DP builds target-length provisional consensuses from cluster-local reads, estimates reusable context and IDS statistics across the dataset, then selectively refines uncertain clusters with structured correction or phase-aware dynamic programming.

2.1 Provisional Consensus Construction

  • Each cluster first receives a target-length provisional consensus from local reads, using a representative read and a reliable subset to limit anomalous-read influence.High-coverage clusters use neighborhood-supported overlapping k-mers; lower-coverage clusters use band-aligned read events and length-constrained decoding.Source: §2.1 · p. 3

2.2 Cross-Cluster Context and IDS Estimation

  • CCP-DP estimates shared sequence context and dataset-level IDS channel statistics from the current dataset to provide complementary evidence for refinement.The shared context and error profile are estimated after provisional consensus construction.Source: §2.2 · p. 3, §2.2.2 · pp. 4–5

2.2.1 Cross-Cluster Context Model

  • The context model measures k-mer reuse across provisional consensuses and uses leave-one-cluster-out probabilities, with calibrated trust controlling how much context influences decoding.Cross-LOO probabilities exclude the target cluster, and context contribution is suppressed if internal validation finds no consistent predictive gain.Source: §2.2.1 · p. 4

2.2.2 Blind IDS Channel Model

  • The blind IDS model estimates substitution, insertion, and deletion rates from aligned reads and summarizes indel burden with a phase-load proxy for routing.The estimated rates are effective dataset-specific rates rather than ground-truth channel parameters.Source: §2.2.2 · pp. 4–5

2.3 Evidence-Guided Phase Dynamic Programming

  • CCP-DP selectively retains provisional consensuses or routes uncertain clusters to boundary correction for localized shifts or Phase-DP for broader phase ambiguity.Boundary corrections are accepted only when the reduction in read-edit energy plus restored terminal-anchor support is positive; a Phase-DP candidate replaces the provisional consensus only if its objective score is higher.Source: §2.3 · pp. 5–6
  • For phase-ambiguous clusters, Phase-DP finds a target-length path through a phase-aware trellis, scoring read, cross-cluster context, and estimated IDS evidence.Its state tracks reference position, generated length, recent context, and insertion state; only paths in a bounded phase band that terminate at the target length are valid.Source: §2.3 · p. 5

3 Experiments and Results

CCP-DP was evaluated on four public DNA-storage datasets against representative reconstruction baselines, with exact reconstruction as the primary metric. It achieved high accuracy across datasets and conditions, with its strongest gains at low coverage and selective refinement focused on difficult clusters.

3.1 Experimental Setup

  • Experiments used four public datasets with differing coverage and IDS characteristics, compared CCP-DP with representative baselines, and assessed exact reconstruction, mean edit distance, and runtime.Reconstruction used clustered noisy reads and target strand length; reference sequences were reserved for evaluation.Source: §3.1 · p. 6

3.2 Overall Reconstruction Performance

  • 99.98% exact reconstruction on Erlich-152 tied BBS, while CCP-DP led on Srinivas-110, Chandak-108, and Chandak-150 at 98.01%, 95.36%, and 98.25%.On Srinivas-110, it improved exact reconstruction from 95.82% to 98.01% in 1.782 s; it also outperformed DNAFormer and TReconLM on Srinivas-110 and Chandak-108 without dataset-specific training or fine-tuning.Source: Table 1 · p. 7, §3.2 · p. 7

3.4 Performance Across Coverage and IDS Conditions

  • At 5× coverage, CCP-DP improved exact reconstruction by 6.2–17.5 percentage points over the stronger of BBS and CPL; at 6% indels, the gain was 17.5 ± 0.1 points.At 10% indels, gains were negative at several intermediate coverage levels, indicating remaining limitations under severe IDS corruption.Source: Figure 3 · p. 8, §3.4 · pp. 8–9

3.5 Difficult-Cluster Identification and Error Correction

  • Guide failures concentrated in the highest anomaly-score deciles, with ROC-AUCs of 0.996 on Srinivas-110 and 0.920 on Chandak-108.Structured decoding substantially reduced the corresponding failure rates, supporting anomaly-guided selective refinement.Source: Figure 4 · p. 8, §3.5 · p. 9
  • Paired indels accounted for 61.0% of guide failures on Srinivas-110 and 77.3% on Chandak-108; structured decoding exactly rescued 76.5% and 67.3% of these errors, respectively.It also reduced edit distance for substitution, paired-indel, and mixed-error categories.Source: Figure 4 · p. 8, §3.5 · p. 9

3.6 Cross-Cluster Context and Selective Decoding

  • Correct Cross-LOO raised exact reconstruction over No Cross-LOO, decode-all, from 94.14% to 98.01% on Srinivas-110 and from 91.41% to 95.36% on Chandak-108.Permuted or mismatched context degraded performance, supporting the value of reusable within-dataset contextual structure.Source: Figure 5 · p. 9, §3.6 · pp. 9–10
  • Selective routing reduced runtime by approximately 66–74% on Erlich-152, Srinivas-110, and Chandak-150, while Chandak-108 routed all clusters and offered little additional saving.The routed fraction varied with provisional-guide reliability and dataset-level error conditions.Source: Figure 5 · p. 9, §3.6 · p. 10

3.7 Ablation Study

  • On Srinivas-110, removing Cross-LOO reduced exact reconstruction from 98.01% to 94.14%, while removing blind IDS likelihood yielded 97.94%.Full decode-all retained 98.01% accuracy but increased runtime from 1.782 s to 6.824 s.Source: §3.7 · p. 10

4 Conclusion

The conclusion presents cross-cluster sequence context as complementary evidence for DNA trace reconstruction when cluster-local observations are insufficient. CCP-DP combines that context with selective, phase-aware refinement, while its benefits depend on reusable cross-cluster structure and the prevalence of clusters needing decoding.

4 Conclusion

  • CCP-DP combines cluster-local reconstruction, calibrated cross-cluster context, and selective phase-aware refinement for ambiguous provisional consensuses.The paper reports high exact reconstruction accuracy with low residual error and computational cost across multiple real DNA-storage datasets and diverse sequencing conditions.Source: §4 · p. 10
  • Mechanism and ablation analyses attribute the observed gains primarily to informative cross-cluster context, while selective decoding concentrates refinement on clusters with greater residual uncertainty.Source: §4 · p. 10
  • The statistical and computational advantages may be reduced when reusable cross-cluster patterns are weak or difficult clusters are widespread.Source: §4 · p. 10

Data and Code Availability

The analyzed datasets are publicly available from their original publications. The implementation and scripts for reproducing the main experiments are available from the CCP-DP repository, and the study generated no new sequencing data.

Data and Code Availability

S1 Supplementary Methods

The supplementary methods detail how CCP-DP constructs target-length provisional consensuses, calibrates cross-cluster evidence, routes uncertain clusters for refinement, and evaluates the reconstruction procedure. Structured decoding combines local, cross-cluster, and channel evidence while applying dataset-dependent controls to its scope and influence.

S1.1 Implementation details of provisional consensus construction

  • For high coverage, CCP-DP aggregates neighborhood-weighted k-mer support and uses overlap-constrained dynamic programming to select a maximum-support path of target length.For low coverage, selected reads are band-aligned to a representative seed; base/deletion and insertion evidence is decoded jointly under the target-length constraint.Source: S1.1 Implementation details of… · pp. 13–15

S1.2 Cross-LOO trust calibration

  • Cross-LOO trust τ is selected from candidate values using calibration and validation subsets, and set to zero when validation does not support retaining it.The calibration uses provisional guides and current-input statistics, without ground-truth sequences.Source: S1.2 Cross-LOO trust calibration · pp. 15–16

S1.3 Adaptive routing of structured decoding

  • Adaptive routing concentrates structured decoding on difficult clusters while avoiding unnecessary inference for well-supported consensuses.Routing depends on cross-cluster reuse, phase load, and cluster anomaly; under low reuse and moderate phase load, rejection of the Cross-LOO prior expands decoding to all clusters.Source: S1.3 Adaptive routing of structured… · pp. 16–17

S1.4 Complete Evidence-Guided Reconstruction Procedure

  • For active clusters, Phase-DP searches a phase-banded trellis for a target-length path scored with local reads, Cross-LOO context, and blind IDS-channel evidence.A Phase-DP candidate replaces the provisional consensus only if it scores higher under the same objective.Source: S1.4 Complete Evidence-Guided… · p. 17

S1.5 Cross-LOO counterfactual controls

  • Counterfactual controls vary the Cross-LOO context supplied to the decoder while keeping other decoder components fixed, including calibrated τ.The conditions include no context, permuted context, context from another dataset, and correctly matched context; all clusters are decoded.Source: S1.5 Cross-LOO counterfactual controls · p. 17, Table S1 · p. 19

S1.6 Experimental protocols and computational settings

  • Evaluation measures exact reconstruction and mean Levenshtein edit distance, using shared sampled clusters across methods in coverage experiments.CCP-DP re-estimates its guides, dataset statistics, IDS profile, and routing for each sampled input; runtime includes reconstruction stages but excludes post hoc evaluation.Source: S1.6 Experimental protocols and… · pp. 18–19

S2 Supplementary Results

CCP-DP outperformed deep-learning baselines on both evaluated datasets, while ablations indicate distinct contributions from structured decoding, Cross-LOO context, and adaptive routing. Fixed-weight context effects varied by dataset; reconstruction quality was stable across broad parameter ranges, and mean edit distance generally declined with coverage.

S2.1 Comparison with deep-learning-based baselines

  • 98.01% (CCP-DP) versus 90.68% (DNAFormer) and 92.07% (TReconLM) on Srinivas-110; on Chandak-108, 95.36% versus 34.56% and 48.19%.CCP-DP also achieved the lowest mean edit distance on both evaluated datasets.Source: S2.1 Comparison with… · p. 19, Table S2 · p. 20

S2.2 Multi-dataset ablation analysis

  • 92.86% and 86.49% exact reconstruction from provisional guides rose to 98.01% and 95.36% with full CCP-DP on Srinivas-110 and Chandak-108, respectively.The local-trellis, decode-all variant improved over provisional guides but remained below the full method.Source: S2.2 Multi-dataset ablation analysis · p. 20, Table S3 · p. 21
  • Removing Cross-LOO reduced exact reconstruction from 98.01% to 94.14% on Srinivas-110 and from 95.36% to 91.41% on Chandak-108.The reported gains were smaller on Bar-Lev-140, where provisional guides were already highly accurate.Source: S2.2 Multi-dataset ablation analysis · p. 20
  • Blind IDS likelihood produced comparatively modest exact-reconstruction changes while modeling dataset-adaptive substitution, insertion, and deletion tendencies alongside Cross-LOO.Source: S2.2 Multi-dataset ablation analysis · pp. 20–21
  • 6.824 s versus 1.782 s on Srinivas-110 was the runtime for decode-all versus adaptive routing, with both retaining 98.01% exact reconstruction.On Bar-Lev-140, runtime rose from 2.893 s to 4.453 s with little change in reconstruction accuracy.Source: S2.2 Multi-dataset ablation analysis · p. 21

S2.3 Diagnostic fixed-weight analysis of Cross-LOO context

  • At fixed Cross-LOO weight 0.50, exact reconstruction changed by −0.610, +0.020, and −7.570 percentage points versus No Cross-LOO on Bar-Lev-140, Grass-117, and Welter-110 subset (file 2).Correct Cross-LOO outperformed table-permuted and wrong-dataset context; the dataset-dependent results support trust calibration.Source: S2.3 Diagnostic fixed-weight analysis… · p. 21, Table S4 · p. 22

S2.4 Parameter sensitivity analysis

  • Reconstruction quality remained stable across broad parameter ranges, while runtime was more sensitive to several routing-related settings.Performance degraded when the coverage switch fell substantially below its default of 40 reads; the default Cross-LOO weight scale of 1.0 was near the best-performing region.Source: S2.4 Parameter sensitivity analysis · p. 22, Figure S3 · p. 23

S2.5 Mean edit-distance robustness across sequencing coverages

Loading 2610.36559v1…