PaperlayerView exact revision on arXiv

Source-linked AI summary

Codes for DNA Sequence Profiles

Han Mao Kiah, Gregory J. Puleo, Olgica Milenkovic

arXiv:1502.00517v1cs.ITmath.COmath.IT

TL;DR

The paper studies how to reconstruct DNA sequences from noisy collections of substrings, a problem relevant to synthetic DNA storage. It models readout with substring profiles and develops asymmetric coding and enumeration techniques; its coding framework characterizes correction of synthesis, coverage, and sequencing errors.

  • Problem

    The paper addresses how to design DNA sequences that can be reconstructed from noisy substring observations in synthetic DNA storage.

    Source: §1 · p. 1

  • Method

    The authors model readout with substring profile vectors and use constrained profile enumeration, Ehrhart theory, and asymmetric coding techniques for code design.

    Source: §1 · p. 2

  • Results

    The paper characterizes profile-based codes for synthesis, coverage, and sequencing errors and uses Ehrhart theory to estimate code sizes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Profile constraints can be selected to lower substitution-error probability and improve error-correcting capability.

    Source: §2 · p. 3

    Treatment of specialized sets of forbidden ℓ-grams is beyond the paper’s scope and deferred to future work.

    Source: §2 · p. 3

Abstract

from arXiv · show

We consider the problem of storing and retrieving information from synthetic DNA media. The mathematical basis of the problem is the construction and design of sequences that may be discriminated based on their collection of substrings observed through a noisy channel. This problem of reconstructing sequences from traces was first investigated in the noiseless setting under the name of "Markov type" analysis. Here, we explain the connection between the reconstruction problem and the problem of DNA synthesis and sequencing, and introduce the notion of a DNA storage channel. We analyze the number of sequence equivalence classes under the channel mapping and propose new asymmetric coding techniques to combat the effects of synthesis and sequencing noise. In our analysis, we make use of restricted de Bruijn graphs and Ehrhart theory for rational polytopes.

1. INTRODUCTION

The paper models DNA storage readout through substring profiles and develops profile-based codes to address synthesis, coverage, and sequencing errors. It uses restricted profile sets and Ehrhart theory to support enumeration and code design.

1. INTRODUCTION

  • The paper models DNA storage as synthesis followed by sequencing that returns all or a subset of ℓ-substrings, with possible substitution errors at both stages.Non-uniform fragmentation can leave some substrings unavailable for sequencing.Source: §1 · p. 1

2. PROFILE VECTORS AND A METRIC SPACE

  • Profile vectors represent substring counts and form a pseudometric space for coding-theoretic analysis of DNA readout.The channel output is a vector enumerating observed substrings and their counts.Source: §1 · p. 2

1. INTRODUCTION

  • The proposed code design combines distinct or sufficiently distant profile vectors with ℓ-substrings selected for biochemical stability and error resilience.The considered codeword constraints include a balanced content constraint.Source: §1 · p. 2
  • The authors cast constrained profile enumeration and code design as integer-point counting in rational polytopes, using Ehrhart theory to estimate code sizes.The approach addresses settings beyond arbitrary ℓ-substrings, including specific substring constraints and profiles separated by distance.Source: §1 · p. 2

A. Error-Correcting Codes for the DNA Storage Channel

  • An (n, d; S)-GRC corrects s_syn synthesis substitutions, s_seq sequencing substitutions, and t undersampling errors when d > 2s_synℓ + 2s_seq + t.Synthesis errors contribute ℓ times as strongly in the bound because they affect multiple ℓ-grams.Source: A. Error-Correcting Codes for the DNA… · p. 4

3. RESTRICTED DE BRUIJN GRAPHS AND ENUMERATION OF PROFILE VECTORS

The section defines restricted de Bruijn graphs from allowed ℓ-grams and uses their structure in profile enumeration. For the stated weight-restricted sets, the graph is Eulerian, while the full de Bruijn graph is Hamiltonian.

3. RESTRICTED DE BRUIJN GRAPHS AND ENUMERATION OF PROFILE VECTORS

  • The restricted graph D(S) uses allowed ℓ-grams as arcs and the appearing (ℓ−1)-grams as nodes.An arc connects two nodes when the suffix of length ℓ−1 of the first matches the prefix of the second.Source: §3 · p. 5
  • The paper extends earlier restricted-graph results beyond binary alphabets and narrow weight ranges to general q, q* and weight intervals.The cited prior result covered a binary alphabet and a specific family of weight restrictions.Source: §3 · p. 5
  • D(q, ℓ; q*, [w1, w2]) is Eulerian for the stated weight ranges, and the full graph D(q, ℓ) is Hamiltonian.These structural properties are established for the restricted and full graphs, respectively.Source: §3 · p. 5

A. Enumerating Q(n; S)

The section counts profile vectors through integer-point and graph formulations, deriving quasipolynomial counts for strongly connected digraphs and growth rates for general digraphs. For general digraphs, the growth of unrestricted profiles is governed by a longest path through their strongly connected components.

A. Enumerating Q(n; S)

  • The sets E(n; S) and F(n; S) encode integer vectors satisfying flow constraints, with strictly positive and nonnegative entries, respectively.When D(S) is strongly connected, every vector in E(n; S) is the profile vector of a closed word.Source: A. Enumerating Q(n; S) · pp. 6–7
  • |E(n; S)| and |F(n; S)| are quasipolynomials of degree |S| − |V (S)|, sharing a period that divides the least common multiple of cycle lengths in D(S).The section states this under the assumption that D(S) is strongly connected.Source: A. Enumerating Q(n; S) · p. 7
  • For strongly connected D(S), profile-vector counts for unrestricted words and specified start or end vertices have the same Θ′ growth as closed-profile counts.The section extends the estimate to profiles with prescribed endpoints and to profiles with only a specified start or end.Source: A. Enumerating Q(n; S) · p. 7
  • For non-strongly-connected D(S), the number of closed-profile vectors is Θ′(n^Δ̄), where Δ̄ is the maximum |S_i| − |V_i| across strongly connected components.The component partition is into induced strongly connected subgraphs.Source: A. Enumerating Q(n; S) · p. 8

ONML HIJK

  • When D(S) is not strongly connected, closed and unrestricted profile-vector counts need not differ by only a constant factor.The section separately characterizes unrestricted-profile growth using the weighted component graph.Source: ONML HIJK · p. 9
  • For general D(S), |pQ(n; S)| = Θ′(n^Δ), with Δ the longest weighted source-to-sink path in the auxiliary digraph of components.The auxiliary graph assigns component-based weights to its arcs and can be used to find the longest path in linear time.Source: ONML HIJK · p. 9

4. EHRHART THEORY AND PROOF OF THEOREM 3.3

The paper uses Ehrhart theory to enumerate profile vectors, extending the analysis to more general digraphs and profiles at prescribed distances. The detailed proof of Theorem 3.3 is presented under a strong-connectivity assumption.

4. EHRHART THEORY AND PROOF OF THEOREM 3.3

  • Ehrhart theory provides a framework for enumerating profile vectors and can simplify techniques used for a more general family of digraphs.The section introduces the theory while assuming D(S) is strongly connected to prove Theorem 3.3.Source: §4 · p. 10
  • The Ehrhart-based enumeration procedure also extends to profiles at a prescribed distance.Source: §4 · p. 10
  • The section provides a detailed proof of Theorem 3.3 under the assumption that D(S) is strongly connected.Source: §4 · p. 10

A. Ehrhart Theory

The section uses Ehrhart theory to count profile vectors through lattice points in rational polytopes, deriving quasipolynomial counts and their periods from the restricted de Bruijn graph.

A. Ehrhart Theory

  • When D(S) is strongly connected, P(S) has dimension |S| − |V(S)|, and its relative interior consists of the positive solutions to A(S)u = b.The lattice-point enumerators of P(S) and its relative interior give |F(n; S)| and |E(n; S)|, respectively.Source: B. Proof of Theorem 3.3 · pp. 11–12
  • The vertices of P(S) are normalized cycle-indicator vectors χ(C)/|C|, so the least common multiple of cycle lengths bounds the period of its lattice-point enumerator.The period of LP(S)(n − ℓ + 1) divides λS.Source: B. Proof of Theorem 3.3 · p. 12
  • For strongly connected D(S), |E(n; S)| and |F(n; S)| are quasipolynomials of degree |S| − |V(S)| with a shared period dividing the least common multiple of cycle lengths.When D(S) contains a loop, the leading coefficients of |E(n; JqKℓ)| and |F(n; JqKℓ)| are equal and constant.Source: B. Proof of Theorem 3.3 · p. 12
  • With a loop, |E(n; S)|, |Q̄(n; S)|, and |F(n; S)| are asymptotic to c(S)n^{|S|−|V(S)|}.The result applies under the strongly connected digraph condition.Source: B. Proof of Theorem 3.3 · p. 13

5. CONSTRUCTIVE LOWER BOUNDS

The section constructs reconstruction codes from asymmetric-error-correcting codes (AECCs), using profile-vector intersections or extensions; its intersection construction gives the optimal polynomial order under stated conditions.

5. CONSTRUCTIVE LOWER BOUNDS

  • Intersecting an AECC with pQ(n; S) produces a reconstruction code, while extending AECC words to profile vectors can preserve the original code size when the extension is possible.The paper notes that arbitrary words cannot always be extended to profile vectors.Source: §5 · p. 13

A. Intersection with pQ(n; S)

  • For Varshamov AECCs, a pigeonhole argument guarantees some β with |C(H, β) ∩ pQ(n; S)| at least |pQ(n; S)|/p^d, but does not identify that β.Source: A. Intersection with pQ(n; S) · p. 13
  • A polytope built from the AECC constraints counts the closed-profile-vector intersection, providing a lower bound on the full profile-vector intersection.The count is a lattice-point count in the polytope’s dilated relative interior.Source: A. Intersection with pQ(n; S) · p. 14
  • For fixed d, the intersection construction yields C(n, d; S) = Θ′(n^{|S|−|V(S)|}) when D(S) is strongly connected and the stated AECC feasibility conditions hold.The theorem guarantees this lower bound when λGRC divides n − ℓ + 1; the upper bound follows from |C(n, d; S)| ≤ |Q(n; S)|.Source: A. Intersection with pQ(n; S) · pp. 13–15

B. Systematic Encoding of Profile Vectors

The section gives a systematic way to extend messages into profile vectors and use asymmetric-error codes to build reconstruction codes; a small example illustrates the rate trade-off and a possible application.

B. Systematic Encoding of Profile Vectors

  • Under the Hamiltonian-cycle and loop conditions, any input of length |S| − |V(S)| − 1 extends to a profile vector, and the encoder runs in O(|V(S)|) time.The systematic coordinates preserve the asymmetric distance of the input code, yielding a reconstruction code.Source: B. Systematic Encoding of Profile… · p. 15

GFED @ABC

  • For S = J2K3, messages of length 3 can be systematically encoded into pQ(10; 2, 3); in general, the construction encodes JmK3 into pQ(4m + 2; 2, 3).The message set is approximately n^3/8, compared with approximately n^4/288 closed profile vectors [9].Source: GFED @ABC · p. 17
  • Although the Section 5-A construction gives larger codes in the discussed comparison, the systematic encoder is simpler and can integrate rank-modulation codes for hybridization-based decoding.Source: GFED @ABC · p. 17

6. NUMERICAL COMPUTATIONS FOR S = S(q, ℓ; q∗, [w1, w2])

The section computes asymptotic coefficients for constrained profile counts, distinguishing cases with and without loops, and uses LattE to obtain coefficients for moderate parameter values.

6. NUMERICAL COMPUTATIONS FOR S = S(q, ℓ; q∗, [w1, w2])

  • The section tabulates computed values of c(q, ℓ) for the unconstrained case S = JqKℓ.Source: Table I · p. 18, §6 · p. 18
  • For w2 = ℓ, |Q(n; S)| has a constant leading coefficient for all n; for w2 < ℓ, the stated asymptotic holds when λS divides n − ℓ + 1.The degree is D = |S| − |V(S)|; in the no-loop case the leading coefficient is periodic in n.Source: §6 · pp. 17–18
  • LattE computes the coefficients for some moderate parameters despite the exact evaluation being prohibitively complex; for example, c(2, 4) = 283/9754214400 took less than a minute.The algorithm enumerates lattice points in polynomial time when the polytope dimension is fixed.Source: §6 · p. 18

A. Lower Bounds on Code Sizes

The section gives lower bounds for reconstruction-code sizes, including a construction that outperforms the systematic encoder in one example. It also conjectures an asymptotic relation between the constructed code sizes and a pigeonhole bound.

A. Lower Bounds on Code Sizes

  • 11,036 codewords are guaranteed for a (158, 3; 2, 3)-GRC, versus 2,368 from the systematic encoder at the same parameters.The first size is a lower bound; the second is the size of the constructed systematic code.Source: A. Lower Bounds on Code Sizes · p. 19
  • Lattice-point computations determine c(H, S) for moderate parameter values and are summarized in Table III.The section also presents a conjecture relating c(H, S) to c(q, ℓ).Source: A. Lower Bounds on Code Sizes · p. 19, Table III · p. 20
  • The conjecture states that |C(H, 0) ∩ E(n; q, ℓ)| is asymptotically at least |Q̄(n; q, ℓ)|/p^d, matching the pigeonhole-principle code-size guarantee.For S = J2K3, c(2, 3) = 1/288.Source: A. Lower Bounds on Code Sizes · pp. 19–20

7. DECODING OF PROFILE VECTORS

Profile vectors can be decoded to representative codewords in linear time. The section also examines presence-or-absence observations, relating the resulting reconstruction codes to graph path packings and decompositions.

7. DECODING OF PROFILE VECTORS

  • The EULER algorithm recovers a representative codeword from a profile vector in linear time.It constructs a connected Eulerian multidigraph from the profile counts and finds an Eulerian walk; the representative choice is independent of the sequence used to obtain the profile.Source: §7 · p. 20

A. Detecting presence or absence of ℓ-grams

  • A set of n − ℓ + 1 − ⌊(d − 1)/2⌋ observed ℓ-grams suffices to identify a codeword in an (n, d; q, ℓ)-∗-GRC.For d = 1, the maximum code size is the number of possible sets of ℓ-grams; for the other extreme, graph decompositions characterize optimal codes.Source: A. Detecting presence or absence of… · pp. 21–22
  • An edge-disjoint path decomposition of D(q, ℓ) into paths of length n − ℓ + 1 yields an optimal (n, 2(n − ℓ + 1); q, ℓ)-∗-GRC of size q^ℓ/(n − ℓ + 1).At the extreme distance 2(n − ℓ + 1), the code problem is equivalent to edge-disjoint path packing in D(q, ℓ).Source: A. Detecting presence or absence of… · p. 22

B. Detecting the relative order of ℓ-grams

Because hybridization can reveal relative ℓ-gram counts more reliably than exact counts, the section encodes information in orderings. A systematic extension connects these orderings to rank-modulation codes while reducing the required probe set.

B. Detecting the relative order of ℓ-grams

  • Hybridization can determine whether one ℓ-gram count exceeds another more accurately than it can infer exact counts, motivating codes that use count orderings.The proposed approach uses a permutation metric to account for ordering errors.Source: B. Detecting the relative order of… · p. 23
  • Only m = q^ℓ − q^(ℓ−1) − 1 probes are needed to obtain an ordering on selected ℓ-grams, rather than probes for all q^ℓ grams.A systematic encoder extends any permutation of length m into a profile vector.Source: B. Detecting the relative order of… · p. 23
  • Messages are encoded as permutations, extended to profile vectors, and mapped by EULER to codewords, allowing rank-modulation codes to be used for DNA storage.The section illustrates the procedure with a length-3 permutation and a 14-symbol binary codeword.Source: B. Detecting the relative order of… · p. 23

APPENDIX A EULERIAN PROPERTY OF CERTAIN RESTRICTED DE BRUIJN DIGRAPHS

The appendix establishes that a family of restricted de Bruijn digraphs is Eulerian and proves a constant-leading-coefficient result for lattice-point enumerators under connectivity and loop assumptions.

APPENDIX A EULERIAN PROPERTY OF CERTAIN RESTRICTED DE BRUIJN DIGRAPHS

  • The restricted digraph is Eulerian: every node has equal incoming and outgoing degree, and the graph is strongly connected.The connectivity argument shows a path exists between nodes differing in one coordinate, then extends this to arbitrary node pairs.Source: Appendix A · pp. 24–25

APPENDIX B PROOF OF COROLLARY 4.6

  • When D(S) is strongly connected and contains loops, the leading coefficient of the lattice-point enumerator LP(S)(t) is constant.A loop gives an injection from F(n; S) to F(n + 1; S), making the enumerator monotonically increasing; this supports the constant-coefficient conclusion.Source: Appendix B · p. 25

APPENDIX C PROPERTIES OF THE POLYTOPE PGRC(H, S)

Under the stated connectivity and nonemptiness assumptions, the appendix characterizes the dimension, interior, and cycle-based vertices of PGRC(H, S).

APPENDIX C PROPERTIES OF THE POLYTOPE PGRC(H, S)

  • For a vertex v=(v1,v2) of PGRC(H,S), v2=1, and the proof concludes that v1=χ(C)/|C| for some cycle C in D(S), giving the stated vertex form.Source: Appendix C · p. 26
  • The dimension of PGRC(H, S) is |S| − |V(S)|.The proof uses the rank |V(S)| + d of A(H, S) and constructs affinely independent points from a strictly positive feasible point.Source: Appendix C · p. 26
  • The interior of PGRC(H, S) consists of vectors u satisfying A(H, S)u = b and u > 0.The proof shows that strictly positive feasible vectors are interior points and that a feasible vector with a zero coordinate is not interior.Source: Appendix C · p. 26
Loading 1502.00517v1…