Title: Rank modulation codes for DNA storage,
Abstract: Synthesis of DNA molecules offers unprecedented advances in storage
technology. Yet, the microscopic world in which these molecules reside induces
error patterns that are fundamentally different from their digital
counterparts. Hence, to maintain reliability in reading and writing, new coding
schemes must be developed. In a reading technique called shotgun sequencing, a
long DNA string is read in a sliding window fashion, and a profile vector is
produced. It was recently suggested by Kiah et al. that such a vector can
represent the permutation which is induced by its entries, and hence a
rank-modulation scheme arises. Although this interpretation suggests high error
tolerance, it is unclear which permutations are feasible, and how to produce a
DNA string whose profile vector induces a given permutation. In this paper, by
observing some necessary conditions, an upper bound for the number of feasible
permutations is given. Further, a technique for deciding the feasibility of a
permutation is devised. By using insights from this technique, an algorithm for
producing a considerable number of feasible permutations is given, which
applies to any alphabet size and any window length.