Improved limits on sequence patterns identified from short DNA reads
Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
Information Theory
Summary
When storing data in synthetic DNA, the information is read back as short snippets rather than the full sequence. The authors studied how many different patterns of these short snippets—called k-decks—can exist for sequences of a certain length and alphabet size. They improved the known upper bound on this number by using a detailed counting method involving Lyndon words, which are special types of sequences. Their results help understand how much information is retained in these short reads and include matching lower bounds in some key cases.
What this means in practice
- •For dna data storage engineers: Improve decoding algorithms by understanding the limits on distinguishable data patterns from short DNA readouts.
- •For error correction code designers: Use refined bounds on sequence distinguishability to design codes optimized for sequencing data retrieval.
A theory result. No direct application yet.
Authors
Arman Nilforoushan, Farzad Parvaresh
Abstract
Data stored in synthetic DNA is retrieved by shotgun sequencing, which returns short subsequences rather than the stored word itself. A natural abstraction of this readout is the $k$-deck of a word: the vector recording how often each word of length $k$ occurs as a subsequence. Two stored words are distinguishable from their readouts exactly when their $k$-decks differ, so the number $D_{q,k}(n)$ of distinct $k$-decks of words of length $n$ over an alphabet of size $q$ measures what a length-$k$ readout retains. We analyse the degrees of freedom remaining in a $k$-deck once all shorter decks are fixed. Within each class of words having prescribed letter multiplicities, the length-$k$ entries are confined to an affine subspace whose dimension is exactly the number of Lyndon words with the same multiplicities, which we give in closed form as a Möbius sum. Writing $L_q(j)$ for the number of Lyndon words of length $j$ over an alphabet of size $q$, we deduce the improved upper bound \[ D_{q,k}(n)=O\!\left(n^{E_q(k)}\right),\qquad E_q(k)=\sum_{j=1}^{k}j\,L_q(j)-1 . \] In the case of a binary alphabet this bound satisfies $D_{2,k}(n)=O\!\left(n^{4\cdot 2^{k-1}}\right)$. We then prove matching lower bounds in the first two nontrivial cases: $D_{q,2}(n)=Θ\!\left(n^{q^2-1}\right)$ for every alphabet size $q$, and $D_{2,3}(n)=Θ(n^{9})$ for the binary alphabet. The latter confirms, for $q=2$ and $k=3$, our conjecture that the upper bound has the correct degree for every $q$ and $k$.