{"id":"a316dfea-f0e2-434f-b70c-d18762deab5a","arxiv_id":"2501.02917","paper_version":5,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the noisy nanopore channel, the paper proves upper and lower capacity bounds and shows that near-noise-free rates are achievable with large tau-mer lengths under erasures or with high sampling rates.","lead":"This paper derives capacity bounds and two near-capacity achievability schemes for a mathematical model of nanopore DNA sequencing, the noisy nanopore channel. It shows that erasure-prone long reads or high sampling rates allow simple encoders and decoders to approach the noise-free information limit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition V.1's entropy bound misapplies Fano's inequality: the alphabet size of S^m is |X|^(τ m), not |X|^τ, so the O(τ ε^τ) gap in Theorem V.1 does not follow as written; a per-burst repair appears possible.","rationale":"The reader's weakest-assumption pick, the exact-reconstruction property in Lemma V.3, is related but not the most load-bearing issue. Even granting Lemma V.3, Proposition V.1 does not follow because the entropy bound in Eq. (60) is dimensionally wrong: Fano's inequality for the whole block S^m carries a factor m that is missing. With Lemma V.3's union bound Pr(E) ≤ m E[K] ε^τ, the corrected Fano bound makes the per-symbol gap O(m ε^τ), which diverges, so the claimed O(τ ε^τ) loss is not established. Since the block-error event E has probability tending to 1 for fixed τ and ε>0, the block-error form of Fano is fundamentally the wrong tool here; what is needed is a per-symbol or per-burst analysis counting the expected number of ambiguous bursts. Such a repair appears feasible and would preserve Theorem V.1, so this is a patchable proof gap rather than a sign that the theorem is false. The change-point decoder in Section VI also has an underspecification issue (the Shiryaev algorithm requires known pre- and post-change distributions, which the decoder does not possess at run time), but I regard the Proposition V.1 Fano misapplication as the single most load-bearing concern because it directly undermines the main erasure-regime theorem as written. The noiseless bound, the general Section IV bounds, and the overall framing are sound, and the paper deserves conditional acceptance pending a corrected entropy argument.","tokens_in":24201,"tokens_out":22781,"duration_ms":241754,"concrete_test":"Independently recompute Proposition V.1: apply Fano's inequality with alphabet size M = |X|^(τ m) to H(S^m|Y^{T_m}), then substitute Pr(E) ≤ m E[K] ε^τ and check whether (1/m)I remains at least C_τ^{no-noise,no-loop} − O(τ ε^τ) as m→∞. Then redo the calculation with N (number of erasure bursts of length at least τ) in place of the event E, bounding each burst's entropy contribution by O(τ log|X|); if the corrected gap is O(m ε^τ) or worse, Theorem V.1's proof fails, and if the N-based bound works, the theorem is saved but Section V-B must be rewritten.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central proof step is Proposition V.1, which claims lim (1/m) I_{P★}(S^m;Y^{T_m}) ≥ C_τ^{no-noise,no-loop} − E[K] ε^τ τ log|X|. The proof upper-bounds H(S^m|Y^{T_m}) via the block error event E = {S^m ≠ f(Y^{T_m})}. In Eq. (60) it states H(S^m|Y^{T_m}) ≤ 1 + Pr(E)·τ log|X|. Fano's inequality for a random variable taking values in (X^τ)^m gives H(S^m|Y) ≤ 1 + Pr(E)·m τ log|X|, with an extra factor m. Lemma V.3 only bounds Pr(E) ≤ m E[K] ε^τ, so the corrected Fano bound yields H/m ≤ 1/m + m E[K] ε^τ τ log|X|, which diverges with m instead of giving the claimed O(τ ε^τ). Moreover E is the event that at least one burst of erasures of length ≥ τ occurs; for fixed τ and ε>0 its probability tends to 1 as m→∞, so any block-error Fano bound is useless. A repair is available: replace the indicator E by N, the number of length-≥τ erasure bursts, and bound H(S^m|Y^{T_m}) ≤ 1 + E[N]·O(τ log|X|), with E[N] ≤ m E[K] ε^τ; this restores a per-symbol gap O(τ ε^τ). But as written, Eqs. (60)–(61) are internally inconsistent. A secondary boundary issue also affects Lemma V.3: a burst of erasures touching the start or end of the output has only one endpoint, so exact reconstruction can fail even for bursts shorter than τ; this is patchable by an o(1) term, not the source of the main gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the noisy nanopore channel (NNC), a duplication channel with structured de Bruijn Markov inputs followed by a memoryless channel. It gives a lower bound on the noiseless NNC capacity, general lower and upper bounds for noisy NNCs, and then analyzes two asymptotic regimes: long memory length τ with erasure noise, and high sampling rates. The main claimed results are Theorem V.1, stating that the erasure-NNC capacity is at least the no-self-loop noiseless capacity minus O(τ ε^τ) and hence tends to 1 as τ→∞, and Theorem VI.2/Corollary VI.1, stating that with a change-point-detection decoder and high sampling rates, error probability vanishes and rates up to the no-self-loop noiseless capacity are achievable. The proofs are built on entropy bounds, a reconstruction property of no-self-loop de Bruijn paths, and a Shiryaev change-point detector.","tokens_in":24452,"tokens_out":17703,"duration_ms":187699,"significance":"If the main claims hold, the paper gives substantial progress on a difficult channel model of practical relevance for nanopore DNA storage. The idea of using no-self-loop de Bruijn inputs to make erasure bursts of length less than τ uniquely reconstructible is elegant, and the change-point-detection decoder is a concrete, practically motivated algorithm. The paper also provides explicit computable bounds and clean examples for the noiseless and general noisy cases, which are useful contributions in themselves. However, the central proof of Section V currently contains a Fano-inequality error, and the Appendix proof of the key monotonicity lemma appears incorrect as written; these issues are load-bearing for Theorem V.1 and Theorem V.2. The high-sampling-rate section also needs a more careful formalization of the channel sequence. The results are plausible and likely repairable, but the current manuscript is not yet technically sound.","major_comments":[{"comment":"In the proof of Proposition V.1, Eq. (60) bounds H(S^m|Y^{T_m}) by 1 + Pr(E)·τ log|X|. Since S^m takes values in (X^τ)^m, Fano's inequality gives H(S^m|Y^{T_m}) ≤ 1 + Pr(E)·m τ log|X|. Using Pr(E) ≤ m E[K] ε^τ from Lemma V.3, the per-symbol bound becomes 1/m + m E[K] ε^τ τ log|X|, which diverges with m. Thus Proposition V.1 and Theorem V.1 do not follow as written. A repair is likely available by counting the number of ambiguous input symbols rather than using a block error event, but the current proof is internally inconsistent and needs to be rewritten.","section":"V-B, Eq. (60)"},{"comment":"The assertion that absence of an output erasure burst of length at least τ makes S^m exactly reconstructible ignores bursts that touch the first or last position of Y^{T_m}: such a burst has only one endpoint, so Lemma V.1 cannot be applied. A fully erased prefix block of length r < τ occurs with probability on the order of (E[ε^K])^r, which for r=1 is O(ε), not O(ε^τ). This contributes only O(1) bits of block uncertainty and is patchable by an o(1) per-symbol term, but the statement 'exactly reconstructible' is false as written.","section":"V-B, Lemma V.3"},{"comment":"Eq. (66) requires P_K(ℓ_m ≤ K ≤ h_m) ≥ 1 − 1/m^{1+η} with ℓ_m = m^2 (ln m)^3, while P_K was fixed in Section II-B. For any fixed distribution on the positive integers, P_K(K ≥ ℓ_m) tends to 0 as m→∞ because the threshold tends to infinity, so (66) cannot hold for a fixed channel. The high-sampling-rate regime must be formalized as a sequence of channels W_nn^{(m)} whose duplication distribution depends on m, and the statements of Theorem VI.2 and Corollary VI.1 should be rephrased accordingly; as written, the limiting operation is not over a well-defined single channel.","section":"VI, Eq. (66)"},{"comment":"The proof of Lemma V.2 asserts A_Gno-loop_{τ−1} = Σ_i A_i and λ(A) ≥ λ(A_Gno-loop_{τ−1}). For q=2 and τ=2, the block-diagonal matrix A has spectral radius 0 because its diagonal blocks are nilpotent, whereas λ(A_Gno-loop_1) = 1. Thus the claimed inequality λ(A) ≥ λ(A_Gno-loop_{τ−1}) is false in this example. The lemma may still be true, but this proof does not establish it; a different comparison argument is needed for the convergence C_no-noise,no-loop_τ → 1 used in Theorem V.2.","section":"Appendix A, Lemma V.2"}],"minor_comments":[{"comment":"In the line immediately after Eq. (72), the expression 'Pr[E^c_1 | E^c_0]' appears to be a typo; the event should be E^c_2 conditioned on E^c_1.","section":"VI, proof of Theorem VI.2"},{"comment":"The letter E is used both for the block error event {S^m ≠ f(Y^{T_m})} and for the erasure-burst event {some burst of erasures has length at least τ}; these should be renamed to avoid confusion.","section":"V-B, Eqs. (54)-(55)"},{"comment":"The upper bound in Theorem IV.3 can exceed 1 when the subtracted term E[K]H(Z|Y) − H(K) is negative; it should be stated explicitly that the bound is combined with the trivial upper bound of 1.","section":"IV, Theorem IV.3"},{"comment":"The remark after Theorem II.1 states a simplification for τ = o(m), but the capacity definition and all subsequent theorems fix τ as a constant; this asymptotic notation could confuse readers and should be clarified.","section":"II-C, Theorem II.1"}],"recommendation":"major_revision","confidential_remarks":"The paper contains several promising ideas and the main asymptotic claims are plausible, but the current proof of Proposition V.1 has a clear Fano-inequality error that removes a factor of m, and the Appendix proof of Lemma V.2 appears to be incorrect for small parameters. These are load-bearing for Theorem V.1. I do not think rejection is warranted because the errors seem repairable and the high-sampling-rate decoder is a valuable contribution, but the authors should be asked to supply a correct proof of the O(τ ε^τ) gap and to reformulate the high-sampling-rate regime as a well-defined sequence of channels."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nMy take: the paper has two genuinely interesting achievability results for noisy nanopore channels, but one of them—Theorem V.1 on erasure noise with large tau—rests on a proof step that is currently wrong in a concrete, correctable way. The stress-test note is accurate on this point.\n\nThe genuinely new content is in Sections V and VI. The change-point detection decoder is a nice idea, tied to a real practical subroutine, and the error analysis in Theorem VI.2 is coherent. The general bounds in Section IV are simple but useful as a first explicit handle on this channel. The noiseless lower bound is a clean exposition of Kirsch–Drinea, as the authors acknowledge. Credit where due: the results are plausible and the high-level intuition—long tau-mers and high sampling rates both mitigate noise—is appealing.\n\nThe soft spot is Proposition V.1. Equation (60) applies Fano's inequality to S^m, whose alphabet size is |X|^(τ m), not |X|^τ. The correct bound is H(S^m|Y) ≤ 1 + Pr(E)·τ m log|X|, so the per-symbol gap should be Pr(E)·τ log|X|, not (1/m)Pr(E)·τ log|X| as written. Even worse, E is the event that at least one erasure burst has length ≥ τ; for fixed τ and ε>0, Pr(E) → 1 as m→∞, so any block-error Fano bound is too weak. The repair is straightforward: count N, the number of long bursts, use E[N] ≤ m E[K] ε^τ, and bound the entropy contribution per burst by O(τ log|X|). That restores the claimed O(τ ε^τ) gap. But as written, Eqs. (60)–(61) are internally inconsistent. This is load-bearing for Theorem V.1.\n\nMinor issues: Lemma V.3's exact reconstructibility ignores bursts touching the start or end of the output, which is patchable with an o(1) term. There is an undefined E0 in Eq. (72). Section VI's use of the authors' own prior result [46] in Eq. (79) is acceptable since that result is independently published, though it should be cited more carefully.\n\nWho benefits: information theorists working on synchronization-error channels or DNA storage. The paper gives theoretical backing to oversampling and long t-mers as noise countermeasures, which is worth knowing.\n\nRecommendation: send to peer review, but require a corrected proof of Proposition V.1 before acceptance. The flaw is mechanical, not fatal, and the contribution is solid enough to justify the referee time.","headline":"Two interesting achievability results for noisy nanopore channels, but the erasure/large-tau proof has a Fano factor-of-m error that needs a per-burst repair before the paper is publishable.","tokens_in":25189,"tokens_out":4250,"would_cite":true,"duration_ms":40730,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A24","94A40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the noisy nanopore channel—a duplication channel with Markov inputs and memoryless noise—achieves rates arbitrarily close to the noiseless capacity in the long-memory erasure regime and in the high-sampling-rate…","keywords":["nanopore sequencing","noisy nanopore channel","duplication channels","channel capacity","erasure noise","change-point detection","de Bruijn Markov process","DNA storage"],"falsifier":"Take a small alphabet, enumerate the no-self-loop de Bruijn graph paths of length about $\\tau$, and look for two distinct paths with the same first and last $\\tau$-mers whose interiors fall inside an erasure burst of length less than $\\tau$; if such a pair exists, Lemma V.1 fails and the decoder $\\mathcal{D}_{\\mathrm{clean}}$ will mis-reconstruct that output. Alternatively, simulate the decoder on all erasure patterns of length $\\tau-1$ for a fixed no-self-loop codeword and check whether any pattern yields two valid reconstructions.","tokens_in":23797,"feed_emoji":"🧬","tokens_out":8263,"duration_ms":77200,"temperature":0.7,"pith_summary":"The noisy nanopore channel (NNC) models a nanopore sequencer as a duplication channel: an input sequence of overlapping $\\tau$-mers (length-$\\tau$ DNA words that slide by one base) is repeated a random number of times, and then each repeated symbol passes through a memoryless noise channel. This paper's central claim is that the NNC is much more informative than its noisy appearance suggests. In the erasure-noise regime with long memory, the achievable rate is within $O(\\tau\\epsilon^\\tau)$ of the no-self-loop noiseless capacity, which itself approaches $1$; in the high sampling-rate regime, a change-point detection decoder achieves rates up to that same noiseless capacity. The paper also supplies a tight lower bound for the noiseless channel and the first computable general lower and upper bounds for noisy nanopore channels. These results matter because nanopore sequencing is a leading candidate for DNA-based archival storage, and the regimes considered are the ones relevant to practical sequencers.","feed_headline":"Noisy nanopore channels approach noise-free capacity","feed_subtitle":"In two practical regimes, simple decoders recover nearly all information from noisy reads.","key_machinery":"The key structural fact is Lemma V.1 for a no-self-loop de Bruijn Markov input process—a first-order Markov chain whose states are length-$\\tau$ words over the base alphabet, with each next state obtained by shifting one symbol and appending a new symbol. The lemma says that any two $\\tau$-mers no more than $\\tau$ positions apart completely determine the intervening sequence of $\\tau$-mers. This makes the decoder $\\mathcal{D}_{\\mathrm{clean}}$ able to reconstruct the input from the output whenever no erasure burst has length $\\tau$ or more, because each short burst is pinned down by its endpoints; the error probability is then bounded by the probability that some burst has length at least $\\tau$, which is at most $m\\,\\mathbb{E}[K]\\,\\epsilon^\\tau$. In the high sampling-rate regime the machinery is a two-stage decoder: quickest change-point detection estimates the run boundaries in the output, a trimming step discards the uncertain tail of each estimated run, and a MAP decoder reads the remaining samples as repeated noisy views of a single $\\tau$-mer.","core_discovery":"For an NNC whose memoryless noise is an erasure channel over the $|\\mathcal{X}|^\\tau$-ary alphabet, the paper proves (Theorem V.1) that $C^{(\\tau)}(\\mathcal{W}_{\\mathrm{nn,EC}}) \\ge C_\\tau^{\\mathrm{no\\text{-}noise,no\\text{-}loop}} - O(\\tau\\epsilon^\\tau)$, and since $C_\\tau^{\\mathrm{no\\text{-}noise,no\\text{-}loop}} \\to 1$, the capacity of the erasure-noise nanopore channel tends to $1$ as the memory length $\\tau$ grows. In the high sampling-rate regime, it proves (Theorem VI.2 and Corollary VI.1) that a decoder built from a quickest change-point detection routine and MAP decoding of the detected repeat blocks has vanishing error probability, so rates up to $C_\\tau^{\\mathrm{no\\text{-}noise,no\\text{-}loop}}$ are achievable. The paper therefore establishes that, in both regimes, the noisy nanopore channel can carry information at rates essentially equal to the noiseless channel capacity.","pith_inferences":["The finite-$\\tau$ gap $O(\\tau\\epsilon^\\tau)$ suggests a concrete design rule for DNA storage: choose the memory parameter $\\tau$ so that $\\tau\\epsilon^\\tau$ is below the target rate loss, and the erasure bursts the decoder must tolerate scale accordingly.","The same two-stage decoder could be tested experimentally on raw nanopore current traces by treating the change-point estimates as run boundaries and then applying MAP decoding over the trimmed samples; the paper does not run such an experiment.","Extending the erasure-region argument to substitution or insertion-deletion noise would require a replacement for Lemma V.1's endpoint determinism; if such a property holds for other noise classes, the same near-capacity conclusion may follow, but that is not shown here.","The high sampling-rate analysis leaves a tradeoff between sampling cost and rate; optimizing the block-length-dependent parameters rather than the paper's specific choices could sharpen the finite-length performance."],"forward_implications":["With erasure noise and sufficiently large $\\tau$, information can be sent at rates arbitrarily close to $1$ bit per input symbol, using the standard no-self-loop de Bruijn Markov input distribution and the simple decoder $\\mathcal{D}_{\\mathrm{clean}}$.","At high sampling rates, the change-point detection decoder makes the block error probability go to $0$ as the input length grows, so the full no-self-loop noiseless rate $C_\\tau^{\\mathrm{no\\text{-}noise,no\\text{-}loop}}$ is achievable.","The noiseless capacity lower bound in Theorem III.1 is computable for duplication distributions such as the elementary i.i.d. duplication channel and the binomial duplication channel, and is tight according to the argument adapted from [28].","General lower bounds based on Bhattacharya parameters and upper bounds such as $\\mathbb{E}[K]\\,C(W)$ give explicit capacity estimates for arbitrary noisy nanopore channels, though they are most useful for short memory lengths.","In both regimes studied, the rate loss to noise vanishes asymptotically, so the noisy nanopore channel behaves like a noiseless constrained channel in the limits considered."],"supporting_citations":[{"why":"introduces the noisy nanopore channel model that the paper analyzes.","marker":"[17]"},{"why":"establishes that the ergodic capacity equals the multi-letter mutual information supremum used throughout.","marker":"[21]"},{"why":"supplies the tight lower-bound argument that makes the noiseless capacity expression in Theorem III.1 exact.","marker":"[28]"},{"why":"provides the constrained-systems theory used to define and compute the no-self-loop noiseless capacities.","marker":"[50]"},{"why":"gives the multi-view channel analysis used in the MAP decoding stage of the high-sampling-rate decoder.","marker":"[46]"},{"why":"supplies the Bhattacharya-parameter and entropy inequalities used in the general lower bound and in the MAP error analysis.","marker":"[47]"},{"why":"provides the quickest change-point detection framework and the false-alarm and delay guarantees used by the decoder's first stage.","marker":"[51]"},{"why":"supplies the specific change-point detection algorithm the decoder invokes.","marker":"[52]"}],"fun_headline_variants":["Nanopore noise barely dents channel capacity","Erasure noise fails to slow nanopore reads","Low-complexity decoders hit noise-free nanopore rates","Near-noiseless rates achieved on noisy nanopore channels","Nanopore channels: capacity nearly noise-free with simple coding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that in a no-self-loop de Bruijn Markov input, an erasure burst shorter than $\\tau$ is always uniquely determined by the surviving $\\tau$-mers on either side; if two different inputs could produce the same output after such a burst, the near-capacity achievability result for the erasure regime would have to be weakened.","fun_headline_variants_meta":{"raw":{"variants":["Nanopore noise barely dents channel capacity","Erasure noise fails to slow nanopore reads","Low-complexity decoders hit noise-free nanopore rates","Near-noiseless rates achieved on noisy nanopore channels","Nanopore channels: capacity nearly noise-free with simple coding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000548,"raw_usage":{"total_tokens":2624,"prompt_tokens":957,"completion_tokens":1667,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":1587}},"tokens_in":573,"tokens_out":1667,"duration_ms":12466,"temperature":1.0,"reasoning_tokens":1587,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:02:18.849603+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small alphabet, enumerate the no-self-loop de Bruijn graph paths of length about $\\tau$, and look for two distinct paths with the same first and last $\\tau$-mers whose interiors fall inside an erasure burst of length less than $\\tau$; if such a pair exists, Lemma V.1 fails and the decoder $\\mathcal{D}_{\\mathrm{clean}}$ will mis-reconstruct that output. Alternatively, simulate the decoder on all erasure patterns of length $\\tau-1$ for a fixed no-self-loop codeword and check whether any pattern yields two valid reconstructions.","supporting_citations":[{"cited_title":"Information rates of the noisy nanopore channel,","cited_arxiv_id":null,"evidence_quote":"introduces the noisy nanopore channel model that the paper analyzes."},{"cited_title":"On noisy duplication channels with Markov sources,","cited_arxiv_id":null,"evidence_quote":"establishes that the ergodic capacity equals the multi-letter mutual information supremum used throughout."},{"cited_title":"Directly lower bounding the information capacity for channels with i.i.d. deletions and duplications,","cited_arxiv_id":null,"evidence_quote":"supplies the tight lower-bound argument that makes the noiseless capacity expression in Theorem III.1 exact."},{"cited_title":"An introduction to coding for constrained systems,","cited_arxiv_id":null,"evidence_quote":"provides the constrained-systems theory used to define and compute the no-self-loop noiseless capacities."},{"cited_title":"Information rates over multi-view channels,","cited_arxiv_id":null,"evidence_quote":"gives the multi-view channel analysis used in the MAP decoding stage of the high-sampling-rate decoder."},{"cited_title":"Polarization and polar codes,","cited_arxiv_id":null,"evidence_quote":"supplies the Bhattacharya-parameter and entropy inequalities used in the general lower bound and in the MAP error analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the quickest change-point detection framework and the false-alarm and delay guarantees used by the decoder's first stage."},{"cited_title":"On optimum methods in quickest detection problems,","cited_arxiv_id":null,"evidence_quote":"supplies the specific change-point detection algorithm the decoder invokes."}],"review_version":1}