ACOR: incremental evidence accumulation towards real-time DNA storage reconstruction

Linxuan Han, Huaming Wu, Shi Jia, Guanjin QuarXiv 2026 · arXiv

TL;DR

ACOR is a streaming reconstruction method for DNA data storage that processes noisy sequencing reads as they arrive, rather than waiting for a run to finish. By combining incremental $k$-mer evidence accumulation with a length-constrained beam search, it achieves reconstruction speedups of up to 1,330x over traditional methods while maintaining near-perfect recovery accuracy.

What Problem Does This Paper Address?

Retrieving digital data from DNA is a multi-step process: synthesis, storage, and sequencing. The sequencing step is notoriously noisy, producing "reads" riddled with substitutions, insertions, and deletions. To recover the original data, researchers use sequence reconstruction—combining multiple noisy copies of the same DNA strand into a single, high-accuracy "consensus" sequence.

Traditionally, this is an offline, batch-process bottleneck. You wait for the sequencer to finish, cluster the millions of reads, and then run heavy algorithms to reconstruct each strand. This creates a significant delay between the end of sequencing and the actual availability of data. The authors of ACOR aim to turn this into a streaming process, overlapping the heavy lifting of reconstruction with the ongoing sequencing run to enable real-time data readout.

Methods

ACOR (incremental evidence accumulation) breaks the reconstruction pipeline into three distinct stages, as illustrated in the workflow below:

ACOR reconstruction workflow showing evidence accumulation, decoding, and priority selection.
  1. Incremental Evidence Accumulation: As each read arrives, ACOR updates a "persistent ledger." It uses a sliding window of length $k$ to record $k$-mer transitions (how one sequence of bases leads to the next), start/end positions, and length statistics. Crucially, it doesn't need to re-scan old reads; it just updates the counts in the ledger.
  2. Evidence-Guided Beam Search: Once a cluster of reads is "closed" (no more reads expected for that strand), ACOR performs a beam search to find the most likely original sequence. It uses the ledger to guide the search, keeping only the top $B$ (beam width) most promising candidates at each step to keep computation manageable.
  3. Priority-Based Selection: Instead of just picking the highest-scoring path, ACOR uses a fixed hierarchy to select the final output. It prioritizes sequences that match the expected design length, then looks at empirical read lengths, and finally falls back to raw reads if the search fails.

To make this practical for large-scale data, the authors implemented sparse storage for the $k$-mer counters, preventing the exponential memory growth that usually plagues high-context ($k > 10$) sequence analysis.

Datasets

The authors evaluated ACOR against a comprehensive suite of benchmarks:

  • 8 Public Benchmarks: Including real-world data from Illumina and Nanopore platforms (e.g., oligo0, Microsoft CNR, DNAFormer) and simulated datasets (Trellis BMA).
  • New NGS Wet-Lab Library: A newly introduced dataset consisting of 96,055 distinct 100-nt designs and a massive 17.7 million reads. This dataset provides a high-depth look at reconstruction performance in a modern next-generation sequencing (NGS) environment.

Key Insights and Ideas

  • Streaming is Efficient: The "aha moment" here is that you don't need the full consensus to start processing. By building the $k$-mer graph incrementally, the computational cost is spread out, leaving only a small "decoding" step for the end of the run.
  • Context Matters: Increasing the $k$-mer size (context) significantly improves accuracy. While $k=9$ is a good default, moving to $k=15$ on their NGS library reduced the number of non-exact reconstructions from 75 down to just 15 across nearly 100,000 designs.
  • Sparse Storage is the Enabler: Traditional dense $k$-mer tables for $k=12$ would require over 20 GB of RAM. ACOR’s sparse implementation handles the same data in just a few hundred MBs, making high-accuracy reconstruction possible on standard workstations.

Key Results

ACOR demonstrates that you don't have to sacrifice quality for speed:

  • Massive Speedups: Parallel ACOR achieved speedups ranging from 28x to over 1,300x compared to serial baseline configurations.
  • Real-Time Performance: It processed the 17.7 million reads of the NGS library in just 9.01 seconds (using 40 workers), achieving 99.92% exact recovery.
  • Competitive Accuracy: In public benchmarks, ACOR’s accuracy was within 0.14 percentage points of the best-tested (but much slower) offline methods. In some high-error scenarios (like the oligo0 dataset), it actually outperformed the baselines in recovering exact sequences.

Limitations and Future Work

While ACOR excels at short-read reconstruction (100–150 nt), it struggles as sequences get longer. Tests on kilobase-scale nanopore windows showed that while ACOR is faster, its error rate increases significantly compared to specialized (but slower) tools like SPOA or abPOA.

The authors also noted that their current method for choosing the optimal $k$ value relies on knowing the reference sequence (retrospective selection). A major priority for future work is developing a "reads-only" selector that can automatically determine the best parameters for a given sequencing run without knowing the answer in advance. Finally, integrating ACOR with upstream real-time clustering tools would complete the path to a truly end-to-end real-time DNA data drive.

Summary updated

Abstract

DNA offers high-density, durable storage by encoding digital information into synthetic strands and retrieving it through sequencing. Sequence reconstruction combines noisy copies of each strand before downstream decoding. Conventional offline methods typically reconstruct completed read clusters, separating reconstruction from ongoing read collection. Streaming reconstruction offers a way to overlap evidence processing with sequencing and reduce the computation remaining before downstream decoding. We present ACOR, a streaming consensus reconstruction method that records $k$-mer transitions and boundary support in a persistent ledger, then decodes through length-constrained beam search and priority-based selection at cluster closure. Evaluation on real and simulated DNA-storage datasets showed competitive recovery. On our own short-read next-generation sequencing (NGS) wet-lab library, ACOR combined near-complete recovery with second-scale reconstruction of more than ten million reads. A smaller public benchmark was completed in a fraction of a second. Parallel ACOR achieved speedups of tens to over a thousand-fold relative to the tested serial baseline configurations. Sparse storage reduced high-context memory requirements, while parallel execution accelerated reconstruction computation. ACOR is designed for streaming readout pipelines that process assigned reads while sequencing continues.
BibTeX
@misc{han2026acor,
  author = {Linxuan Han and Huaming Wu and Shi Jia and Guanjin Qu},
  title = {{ACOR: incremental evidence accumulation towards real-time DNA storage reconstruction}},
  year = {2026},
  eprint = {2610.36500},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36500},
}
Figure