Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
En palabras de los autores
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 -deck of a word: the vector recording how often each word of length occurs as a subsequence. Two stored words are distinguishable from their readouts exactly when their -decks differ, so the number of distinct -decks of words of length over an alphabet of size measures what a length- readout retains. We analyse the degrees of freedom remaining in a -deck once all shorter decks are fixed. Within each class of words having prescribed letter multiplicities, the length- 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\"obius sum. Writing for the number of Lyndon words of length over an alphabet of size , 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 . We then prove matching lower bounds in the first two nontrivial cases: for every alphabet size , and for the binary alphabet. The latter confirms, for and , our conjecture that the upper bound has the correct degree for every and .
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.