Error-Correcting Codes for Nanopore Sequencing

Anisha Banerjee, Yonatan Yehezkeally, Antonia Wachter-Zeh, Eitan Yaakobi

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Nanopore sequencing, superior to other sequencing technologies for DNA storage in multiple aspects, has recently attracted considerable attention. Its high error rates, however, demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Mao <italic>et al</italic>., incorporating intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of length <italic>l</italic> over a <italic>q</italic>-ary input sequence that outputs the <italic>composition</italic> of the enclosed <italic>l</italic> bits, and shifts by &#x03B4; positions with each time step. In this context, the composition of a <italic>q</italic>-ary vector <italic>x</italic> specifies the number of occurrences in <italic>x</italic> of each symbol in &#x007B;0,1,..., <italic>q</italic> - 1&#x007D;. The resulting compositions vector, termed the <italic>read vector</italic>, may also be corrupted by <italic>t</italic> substitution errors. By employing graph-theoretic techniques, we deduce that for &#x03B4; = 1, at least log log <italic>n</italic> symbols of redundancy are required to correct a single (<italic>t</italic> = 1) substitution. Finally, for <italic>l</italic> &#x2265; 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is of optimal redundancy up to a (small) additive constant for this setting. This construction is also found to be optimal for the case of reconstruction from two noisy read vectors.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Information Theory
DOIs
StateAccepted/In press - 2024

Keywords

  • DNA
  • DNA sequences
  • Error correction codes
  • Europe
  • Noise measurement
  • Sequence reconstruction
  • Sequential analysis
  • Symbols
  • Vectors
  • composition errors
  • error-correction codes
  • nanopore sequencing

Fingerprint

Dive into the research topics of 'Error-Correcting Codes for Nanopore Sequencing'. Together they form a unique fingerprint.

Cite this