PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Linxuan Han, Huaming Wu, Shi Jia, Guanjin Qu

arXiv:2610.36500v1cs.IRq-bio.GN

TL;DR

DNA-storage reconstruction must recover designed strands from noisy reads, while streaming creates a trade-off between repeated recomputation and premature commitment. ACOR accumulates k-mer evidence as reads arrive and decodes at cluster closure; it achieved competitive recovery with seconds-scale processing of million-read inputs, including over ten million NGS reads within seconds.

  • Problem

    Streaming reconstruction must accumulate evidence as reads arrive without repeatedly revisiting earlier reads or committing before later-supported alternatives appear.

    Source: §1 · p. 2

  • Method

    ACOR updates a persistent ledger of k-mer transitions, boundary support, and length statistics, then uses length-constrained beam search and candidate selection at cluster closure.

    Source: §1 · p. 2

  • Results

    Across evaluated benchmarks, ACOR achieved competitive reconstruction quality; on the NGS wet-lab library it processed over ten million reads within seconds, with speedups from tens to over a thousand-fold versus tested serial configurations.

    Source: §1 · p. 3, §4 · p. 12

  • Takeaways & Limitations

    Incremental evidence accumulation lets reconstruction overlap read collection without rescanning earlier reads, reducing computation remaining before downstream decoding.

    Source: §1 · p. 2

    Evaluations use assigned clusters, known design lengths, and externally determined closure; integrating online read assignment and closure remains future work.

    Source: §4 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

Streaming DNA-storage reconstruction must recover designed strands from noisy reads while avoiding repeated recomputation and premature commitment. ACOR accumulates evidence as reads arrive and decodes at cluster closure, combining competitive recovery with fast processing on the NGS wet-lab library.

  • Streaming reconstruction must accumulate evidence as reads arrive without repeatedly revisiting earlier reads or committing before later-supported alternatives appear.This allows reconstruction to overlap read collection while retaining alternatives until cluster closure.Source: §1 · p. 2
  • ACOR updates a persistent ledger of k-mer transitions, boundary support, and length statistics, then uses length-constrained beam search and priority-based selection at cluster closure.It is designed for readout pipelines that incrementally supply strand-assigned reads.Source: §1 · p. 2
  • Sparse storage reserves counters for observed contexts and transitions, avoiding exponential allocation for dense high-k counters; parallel cluster processing accelerates computation when overhead remains acceptable.Source: §1 · pp. 2–3
  • Over ten million reads were processed within seconds on the NGS wet-lab library, with recovery close to the best tested methods and speedups from tens to over a thousand-fold versus tested serial configurations.Source: §1 · p. 3

2 Methods

ACOR processes assigned reads into a persistent, cluster-level evidence ledger, then reconstructs one sequence after cluster closure. Its decoding uses length constraints, bounded search over observed transitions, and a fixed candidate-selection hierarchy.

2.1 Algorithm overview

  • ACOR updates a cluster ledger once per assigned read and decodes only after cluster closure, using design length supplied by the upstream protocol.Read assignment and the closure signal are external inputs.Source: §2.1 · p. 3, §2.2 · p. 5

2.2 Incremental accumulation of sequence evidence

  • Each normalized read contributes context and transition counts, boundary support, length statistics, and normalized-read frequencies to the ledger.The implicit graph stores observed contexts and single-base extensions through accumulated counts rather than materializing a separate graph for each read.Source: §2.2 · pp. 3–4

2.3 Evidence-guided beam search

  • After closure, ACOR derives admissible lengths from design length and observed read lengths, ranks supported starting contexts, and grows at most B active prefixes per depth along observed transitions.Candidate caches retain up to B strings; the active beam is ranked by P, while complete candidates are scored by S using path support, length plausibility, and terminal evidence.Source: §2.3 · pp. 5–6

2.4 Priority-based consensus selection

  • ACOR checks design-length, neighboring-length, empirical-length, and raw-read candidate families in a fixed order, returning the top-ranked candidate from the first non-empty family.Candidates at neighboring lengths are ranked jointly at each offset; later families are not compared after selection.Source: Figure 1 · p. 4, §2.4 · p. 6

2.5 Computational complexity

  • The stated cluster-time accounting includes read accumulation, length statistics, root ranking, and bounded search; fixed B and M remove explicit read-count dependence from search, not accumulation or root ranking.Sparse storage allocates counters for observed evidence; the analysis distinguishes it from dense direct-indexed storage.Source: §2.5 · p. 7

3 Results

Across public DNA-storage benchmarks and a full NGS library, ACOR achieved competitive exact-sequence recovery. The results also report second-scale library processing, reduced memory use with hybrid storage, and workload-dependent parallel scaling.

3.1 Datasets

  • The evaluation covered approximately 8.8 million reads from 341,867 non-empty public clusters and an NGS library of 96,055 distinct 100-nt payloads.The NGS library retained 17,701,449 assigned read observations across all designs.Source: §3.1 · p. 8

3.2 Comparison settings

  • ACOR used k = 9 and B = 16 unless stated otherwise, while P20 denotes 20 workers; baseline resource allocations differed from ACOR's.The compared methods received identical normalized clusters and design lengths.Source: §3.2 · pp. 8–9

3.3 Evaluation metrics

  • Exact and Accuracy were reported as percentages, while evaluation compared each reconstructed sequence with its reference using Levenshtein distance.ACOR engine time included loading, reconstruction, and prediction writing, but excluded external preparation and evaluation.Source: §3.3 · p. 9

3.5 Fast reconstruction of complete libraries

  • 17,701,449 assigned NGS read observations were processed in 9.01 s at k = 9/P40, with 99.9219% Exact and approximately 28–1,330-fold acceleration over seven tested serial configurations.The higher-recovery P16 configuration completed the library in 20.53 s.Source: §3.5 · p. 10

3.4 Reconstruction fidelity across sequencing datasets

  • Public-benchmark Exact ranged from 92.16% to 99.92%; four datasets were within 0.14 percentage points of the best baseline, and ACOR achieved 99.9844% Exact on the NGS library.On oligo0, ACOR recovered the largest fraction of exact sequences despite 13.56% read-level error, while CPL had higher Accuracy and lower Mean ED.Source: §3.4 · p. 10, Figure 3 · p. 11

3.6 Memory efficiency and workload-dependent scalability

  • At k = 12, hybrid storage used 41.84–658.97 MiB peak RSS versus 22.53–23.14 GiB for historical dense storage; on 20 million reads, compute time fell from 47.2 s to 1.30 s.The memory comparisons used different worker allocations; the compute result corresponds to 36.4× speed-up and 91.0% parallel efficiency, while predictions remained identical.Source: §3.6 · pp. 10–12, Figure 3 · p. 11, Figure 4 · p. 12

3.7 Ablation, context sensitivity and extended reconstruction

  • Removing start support reduced mean Exact by 9.1 percentage points, while removing terminal support or using flat selection reduced it by 5.5 points.Reference-guided ONT windows reached 76.56% Exact at 2 kb and 52.34% at 4 kb; at 4 kb, ACOR had higher Mean ED and lower Accuracy across the full window set.Source: §3.7 · p. 12, Figure 4 · p. 12

4 Discussion and conclusion

ACOR accumulates evidence as reads arrive and decodes once at cluster closure, targeting streaming readout while retaining competitive reconstruction quality. The evaluation highlights throughput and memory efficiency, while noting that current evaluations rely on assigned clusters, known lengths, and externally determined closure.

4 Discussion and conclusion

  • ACOR combines incremental evidence accumulation with a single decoding step at cluster closure for streaming consensus reconstruction.This avoids repeatedly reconstructing the consensus as reads arrive.Source: §4 · pp. 12–13
  • Sparse storage avoids exponential allocation for dense high-k counters, while coordinated parallel execution reduces reconstruction-compute time.Workload size and input loading set different limits on overall performance.Source: §4 · p. 13
  • Reference-guided nanopore experiments extend evaluation to kilobase-length sequences, but failed reconstructions have more severe errors.Source: §4 · p. 13
  • The evaluation spans short-read NGS contexts and reports that longer contexts improved Exact and reduced maximum residual errors.The short-read wet-lab library complements public benchmarks and simulations.Source: §4 · p. 13
  • Current evaluations use assigned clusters, known design lengths, and externally determined closure; integrating online assignment and closure remains future work.The retrospective k-selection rule also uses references.Source: §4 · p. 13

5 Data availability

The paper identifies benchmark sources and records the scope of its Source Data archive, including exclusions.

5 Data availability

  • Source Data include the own-NGS assigned-cluster bank, design references, retained results, protocols, and a figure/table index.Source: §5 · p. 13
  • The archive excludes raw paired-end NGS files and third-party raw reads and reference sequences.Source: §5 · pp. 13–14
  • Named benchmark sources include Chandak nanopore, UW MISL 365-dishes, Microsoft CNR, and Trellis BMA.DNAFormer and end-to-end storage data are identified by Zenodo records 13896773 and 10943282.Source: §5 · p. 13

Supplementary information

The supplement collects experiments supporting ACOR and provides associated settings, measurement scopes, and Source Data.

Supplementary information

S1 Experimental settings and measurement

The supplementary experiments specify datasets, reconstruction and measurement settings, and measured implementations. They also test structural components and parameter sensitivity, including beam width and support weight.

S1.1 Datasets, defaults and execution environments

  • Experiments covered eight public DNA-storage benchmarks, the assigned-cluster NGS library, synthetic workloads, and reference-guided ONT windows.The original benchmark used k = 9 and beam width B = 16 unless otherwise stated; execution environments and worker scans are specified.Source: S1.1 Datasets, defaults and execution… · p. 17

S1.2 Reconstruction settings used in the experiments

  • Runs processed assigned reads and decoded once at externally signalled cluster closure using a fixed target length per cluster.Root and candidate ranking used specified support, occurrence, length, precision, and lexical tie-break rules.Source: S1.2 Reconstruction settings used in… · p. 17

S1.3 Quality, timing and memory summaries

  • Quality was evaluated per assigned cluster or genomic window, while timing summaries distinguish runner wall time from reconstruction-compute time.Runner wall time includes input/order loading, reconstruction, and prediction writing; reconstruction-compute time excludes loading and writing but retains initialization and scheduling.Source: S1.3 Quality, timing and memory… · pp. 17–18

S1.4 Measured builds and baseline adapters

  • The reported comparisons retain measured build identities and describe baseline implementations and adapters, including alignment-plus-consensus pipelines.The hybrid compatibility guard passed the ledger-reduction test and all 12 Python tests, while the complete matrices predate that guard.Source: S1.4 Measured builds and baseline… · p. 18

S2.1 Structural comparisons and output completeness

  • Removing start support reduced mean Exact by 9.1 percentage points; removing terminal support or using flat selection reduced it by approximately 5.5 points.Permitting unobserved transitions reduced mean Exact by approximately one point and had a median runtime ratio of 2.34; removing raw-read alternatives left clusters without predictions.Source: S2.1 Structural comparisons and output… · p. 19

S2.2 Beam-width and support-weight diagnostics

  • Beam widths 2, 4, 8, 16, 24, 32, 48, and 64 were tested across eight datasets at fixed k = 9 and 20 workers, using B = 16 as the reference.Figure S1 encodes Exact and Accuracy differences, wall-time ratios, and peak RSS; its points are single-run observations.Source: S2.2 Beam-width and support-weight… · p. 19, Figure S1 · p. 19
  • The B = 4 diagnostic reduced mean Exact by 1.8 points and had a median runtime ratio of 0.74 relative to B = 16.Support-weight curves report median within-seed Exact differences from α = 0.15 and the observed three-seed range.Source: S2.2 Beam-width and support-weight… · pp. 19–20

S2.3 Benchmark sensitivity to k and measured memory

Across the benchmark and synthetic sweeps, reconstruction quality and memory varied with context size and workload. A reference-informed context rule stayed close to the best tested Exact, while the own-NGS comparison showed near-complete recovery and faster reconstruction than tested serial configurations.

S2.3 Benchmark sensitivity to k and measured memory

S2.4 Synthetic length, read-count and error-budget sweep

  • At Exact ≥0.90, acceptable conditions fell from 18/18 at 500 and 1,000 nt to 0/18 at 8,000 nt across the synthetic sweep.Each condition contained eight strands, so the threshold required all eight to be exact; at 8,000 nt, N = 320, η = 0.025 and k = 12 recovered 0.750 and 0.875 exactly across the two seeds.Source: Figure S3 · p. 21, S2.4 Synthetic length, read-count and… · p. 21

S2.5 Retrospective context-selection experiment

  • The reference-informed rule selected contexts within 0.2 percentage points of each dataset’s best-tested Exact, with a maximum shortfall of 0.1438 points.Selection used supplied references, reference-based error profiles and measured grid RSS, rather than reads alone.Source: Figure S4 · p. 22, S2.5 Retrospective context-selection… · p. 22

S3 Detailed quality evaluation on public DNA-storage benchmarks

S4 Full-library validation on our short-read NGS data

  • 9.013 s runner time and 27.73×–1,332.73× duration ratios were recorded for ACOR versus seven single-worker configurations on the complete own-NGS library.The comparison used their respective loading boundaries; the ratios ranged from 27.73× for BMALA (249.910 s) to 1,332.73× for POASTA-based reconstruction (12,011.994 s).Source: S4 Full-library validation on our… · p. 25

S4.1 Context-length comparison on the complete design pool

On the complete own-NGS pool, higher context improved recovery while preserving output coverage. The high-context storage and worker tests also preserved predictions while measuring compute scaling.

S4.1 Context-length comparison on the complete design pool

S5 Prediction preservation, storage and computational scalability

  • The high-context implementation uses observed-key sparse storage and, for split large clusters, private worker ledgers with deterministic tree merging.The supported sparse path preserves search scores, candidate priority and tie-breaking while rejecting incompatible dense shared-write routes.Source: S5.1 Prediction-preserving… · p. 25

S5.1 Prediction-preserving high-context storage

  • At k = 12, reconstruction-compute time fell from 293.743603936 s at P1 to 8.567062081 s at P40, a 34.29× speed-up.These were single timing observations at the P1 and P40 endpoints; all 32 tested configurations matched their historical dense prediction hashes.Source: S5.1 Prediction-preserving… · pp. 25–26

S5.2 Memory comparison

The memory, execution, and scaling measurements distinguish high-context storage from worker allocation and input-loading costs. Controlled workloads preserved predictions, while compute scaling depended on workload size and saturated in the SMT region.

S5.2 Memory comparison

  • At k = 12, hybrid P40 peak RSS was 41.84–658.97 MiB, compared with 22.53–23.14 GiB for historical dense P20.The comparison includes different worker allocations as well as different representations, and all predictions matched the dense reference.Source: S5.2 Memory comparison · p. 26, Table S3 · p. 26

S5.3 Execution route for the controlled scaling workloads

  • The scaling workloads tested inter-cluster scheduling on a 40-physical-core, 80-logical-CPU machine, with 1,000 reads per cluster.The 5M and 20M workloads tested inter-cluster pooling rather than single-cluster or beam-search parallelism.Source: S5.3 Execution route for the… · p. 26

S5.4 Controlled inputs, repetitions and quality gates

  • All 27 5M runs and 36 20M runs consumed every read, achieved Exact and Accuracy of 1.0, and had identical prediction-file hashes within each workload.The controlled workloads replicated a fixed input for the 20M series, increasing computational volume without adding independent sequence diversity.Source: S5.4 Controlled inputs, repetitions… · p. 27

S5.5 Timing definitions and summaries

  • Reconstruction-compute time includes worker start-up, state initialization, dispatch and reconstruction, but excludes input/order loading and prediction writing.Runner wall time includes loading and prediction writing, so the two timing measures have different boundaries.Source: S5.5 Timing definitions and summaries · p. 27

S5.6 Measured scaling and input cost

  • On 20M reads, median compute time fell from 47.203 s at P1 to 1.296 s at P40, yielding 36.41× speed-up and 91.0% efficiency.The 5M workload reached 28.90× and 72.2% at P40; above P40, scaling saturated in the SMT region as RSS rose from about 3.42 GiB at P40 to 4.11 GiB at P79.Source: S5.6 Measured scaling and input cost · p. 28
  • At P40 on 20M reads, median input time was 7.099 s and runner wall time was 8.414 s; runner wall time improved 6.46× from P1.Input time and runner wall time are separately calculated medians, and input loading accounted for most of the remaining time.Source: S5.6 Measured scaling and input cost · p. 28

S6 Long-sequence stress tests and failure boundaries

Long-sequence tests used reference-guided ONT windows and a separate dense-storage pilot. Results show competitive exact recovery at some window lengths, but also substantial errors and limits in the tested longer-window settings.

S6.1 Expanded comparison: assigned inputs and window construction

  • Expanded comparisons used 256, 256 and 128 windows at 1, 2 and 4 kb, respectively, drawn from one isolate and sequencing run.Each consensus method received assigned reads without truth sequences; ACOR used k = 13, 15 and 15 at the three lengths.Source: S6.1 Expanded comparison: assigned… · p. 29

S6.2 Repetitions, timing scopes and stopping states

  • ACOR timings were single observations, while baseline repetitions and elapsed-time scopes differed by method; two settings were stopped at the predeclared 600-s limit.The incomplete MUSCLE 2-kb/P16 and POASTA 2-kb/P1 runs received no quality values.Source: S6.2 Repetitions, timing scopes and… · pp. 29–30

S6.3 Complete expanded quality and runtime comparison

  • At 2 kb, ACOR recovered 196/256 windows exactly, versus 165/256 for BBS, 142/256 for SPOA, 136/256 for abPOA and 10/256 for POASTA.At 4 kb, ACOR recovered 67/128 exactly, versus 38/128 for SPOA and 27/128 for abPOA; at 1 kb, ACOR recovered 224/256, below BBS’s 226/256.Source: Table S4 · p. 30, S6.3 Complete expanded quality and… · p. 30

S6.4 Worker dependence and prediction preservation

  • For the 128–256-window workloads, P40 reduced 1-kb reconstruction-compute time relative to P16 but increased it at 2 and 4 kb.The configurations consumed their full inputs, and these workloads gained less from additional workers than the controlled 20M workload.Source: Table S5 · p. 31, S6.4 Worker dependence and prediction… · p. 32

S6.5 Error severity in failed expanded-window reconstructions

  • At 4 kb, ACOR Accuracy was 0.962299 versus 0.999549 for SPOA and 0.999520 for abPOA, while ACOR recovered more windows exactly.ACOR’s Mean ED at 1/2/4 kb was 12.742/36.145/150.805, with maximum ED of 424/887/2926.Source: S6.5 Error severity in failed… · p. 32

S6.6.1 Pilot window construction and sampling

  • The pilot retained 12 windows each at 1, 2, 4 and 8 kb, ten at 16 kb and eight at 32 kb, with median read counts declining from 20 to 3.5.Different lengths reused centres and could contain nested regions, while coverage and sequence content also changed.Source: S6.6.1 Pilot window construction and… · p. 32

S6.6.2 Completed grid and observed limits

S7 Additional benchmark and scoring experiments

The supplement documents historical benchmark records, worker and scoring experiments, and source conventions. Its default-k release comparison reports identical predictions but worker- and timing-scope-dependent speed differences.

S7.1 Historical quality and timing records

S7.2 Historical worker scan and component tests

  • The historical worker scan covered ten settings and three seeds per dataset; sparse range merging did not improve some small-cluster timings.The scan figure reports median runner wall times with observed minimum–maximum bands; runner time includes loading and prediction writing.Source: S7.2 Historical worker scan and… · p. 36, Figure S9 · p. 36

S7.3 Additional scoring configurations

  • Three additional scoring variants were assessed across 72 observations, but the comparison had no matched default arm.The variants removed terminal scoring, removed length scoring, or used median-band scoring; the main figure contains the structural ablations.Source: Figure S10 · p. 37, S7.3 Additional scoring configurations · p. 37

S7.4 Parameter-grid source conventions

  • The parameter-grid source conventions distinguish synthetic error rate η from normalized mean_ed, while the main manuscript reports unnormalized Mean ED.The source files include 56 real-k records, 450 synthetic-k runs, 90 best-tested-k records, 25 synthetic cells, and 64 beam observations.Source: S7.4 Parameter-grid source conventions · p. 37

S8 Release compatibility at the default context length

  • At P20, the median runner wall-time ratio across datasets favored v0.2.0 by approximately 1.17×, although all P1 observations and Oligo0 at P40 were slower in v0.2.0.All 24 matched version–dataset–worker pairs had identical predictions and quality metrics; reconstruction-compute time was also higher in v0.2.0 at the tested worker counts.Source: S8 Release compatibility at the… · pp. 37–38, Figure S11 · p. 39

Source Data index

The source-data index maps benchmark, parameter, component, storage, scaling, long-sequence, and release records to their archive locations and provenance information.

  • Experimental records are supplied in ACOR_Source_Data.zip, with archive checksums and navigation maps identifying the source files.Measured-build and executable identifiers are listed separately in the provenance index.Source: Source Data index · p. 40
  • Parameter and component records include synthetic and real k grids, beam observations, scoring variants, and separate paired support-weight and structural-ablation data.The index also identifies files for reference-informed selection and dataset profiles.Source: Source Data index · p. 40
  • The index covers public benchmark records and an own-NGS library archive with assigned reads, within-cluster order, design references, and coverage.The assigned-read archive excludes raw paired FASTQ files; references were used for assignment and evaluation, not reconstruction.Source: Source Data index · p. 40
  • Separate source files document storage and CPU scaling, long-sequence experiments, and default-k release compatibility.The index distinguishes reconstruction-compute timing and records completed method–length cells alongside one recorded timeout.Source: Source Data index · p. 40

Related papers

Loading 2610.36500v1…