2021/01/15 by Niv Beeri, Beeri, Niv, Moshe Schwartz +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.2101.06033
arxiv created 2021/01/15 · openalex publication_date 2021/01/15 · arxiv updated 2021/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study permutations over the set of ℓ-grams, that are feasible in the sense that there is a sequence whose ℓ-gram frequency has the same ranking as the permutation. Codes, which are sets of feasible permutations, protect information stored in DNA molecules using the rank-modulation scheme, and read using the shotgun sequencing technique. We construct systematic codes with an efficient encoding algorithm, and show that they are optimal in size. The length of the DNA sequences that correspond to the codewords is shown to be polynomial in the code parameters. Non-systematic with larger size are also constructed.