A Caltech Library Service

Rank-Modulation Codes for DNA Storage With Shotgun Sequencing

Raviv, Netanel and Schwartz, Moshe and Yaakobi, Eitan (2019) Rank-Modulation Codes for DNA Storage With Shotgun Sequencing. IEEE Transactions on Information Theory, 65 (1). pp. 50-64. ISSN 0018-9448.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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. Furthermore, 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Raviv, Netanel0000-0002-1686-1994
Schwartz, Moshe0000-0002-1449-0026
Yaakobi, Eitan0000-0002-9851-5234
Alternate Title:Rank modulation codes for DNA storage
Additional Information:© 2018 IEEE. Manuscript received August 7, 2017; revised January 22, 2018; accepted April 12, 2018. Date of publication April 25, 2018; date of current version December 19, 2018. This work was supported by the Israel Science Foundation under Grant 130/14 and Grant 1624/14. This paper was presented in part at the 2017 IEEE International Symposium on Information Theory.
Funding AgencyGrant Number
Israel Science Foundation130/14
Israel Science Foundation1624/14
Subject Keywords:DNA storage, permutations codes, DeBruijn graphs
Record Number:CaltechAUTHORS:20190109-160746487
Persistent URL:
Official Citation:N. Raviv, M. Schwartz and E. Yaakobi, "Rank-Modulation Codes for DNA Storage With Shotgun Sequencing," in IEEE Transactions on Information Theory, vol. 65, no. 1, pp. 50-64, Jan. 2019. doi: 10.1109/TIT.2018.2829876
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92185
Deposited By: Tony Diaz
Deposited On:10 Jan 2019 12:34
Last Modified:10 Jan 2019 12:34

Repository Staff Only: item control page