Coding for DNA-based Storage Systems

Abstract

DNA-basert lagring, eller lagring av brukerdata i deoksyribonukleinsyre (DNA) tråder, kan teoretisk gi dramatisk høyere lagringskapasitet og lagringsrobusthet sammenlignet med dagens lagringsteknologier. Flere småskalaeksperimenter indikerer at DNA-basert lagring kan være mulig å implementere i praksis, og internasjonalt foregår det intens forskning rundt dette temaet. I tillegg til de biologisk aspektene, er det også viktig å studere DNA-lagringskanalen fra et informasjonsteoretisk ståsted. I DNA-basert lagring blir informasjon lagret som sekvenser av nitrogenbaser (adenin (A), tymin (T), guanin (G) og cytosin (C)). Lagringsprosessen er sårbar for såkalte IDS-feil, det vil si feil som følge av tilfeldig innsetting, sletting eller substitusjoner av nitrogenbaser i sekvensene.

Fokus for denne avhandlingen er utvikling og optimalisering av kodeløsninger som kan motvirke effekten av IDS-feil og derfor gi en pålitelig lagring. I tillegg introduserer vi algoritmer for å dekode de foreslåtte kodeløsningene som er skreddersydd for en DNA-basert lagringskanal. I fire artikler studerer vi tre forskjellige kanalmodeller. Den første kanalmodellen er en forenklet modell som introduserer uavhengige og identisk distribuerte IDS-feil. Ved å studere denne forenklete modellen fikk vi grunnleggende innsikt i virkningen av IDS-feil på kodeytelse. Den andre og tredje kanalmodellen er mer realistiske utvidelser av den første modellen, der den andre modellen inkluderer trådslettinger og tap av rekkefølge på lagrede data, mens den tredje modellen introduserer korrelerte IDS-feil. Design og optimalisering av kodeløsningene for hvert enkelt tilfelle ble gjort ved hjelp av asymptotisk oppnåelige informasjonsrater, grenser for endelig lengde og analyse av dekodingsalgoritmer.

Storing user data in deoxyribonucleic acid (DNA) strands, referred to as DNAbased storage, has become a hot topic during the last decade and has gained the interest of several research communities due to the success of several small-scale experiments that demonstrated the viability of DNA-based storage. This increased interest is warranted due to the theoretical superiority of DNA-based storage technology compared to traditional storage methods, as storing data in DNA can potentially provide both higher storage capacity and longevity. This success also inspired the study of the DNA storage channel from an information-theoretic point of view. In turn, this paved the way for the research problem of “Reliable communication over the DNA storage channel,” the most relevant problem for this thesis, or, more precisely, reliable communication over channels that introduce insertion, deletion, and substitution (IDS) errors.

In this thesis, we design and optimize concatenated coding schemes that can combat errors that arise from the DNA storage channel and hence guarantee reliable communication. In addition, we introduce decoding algorithms for the proposed concatenated coding schemes that are tailored to the DNA storage channel. The proposed coding schemes have the form of an inner synchronization block code concatenated with an outer low-density parity-check code (or a polar code). Over the course of four papers, we study three different channel models. The first channel model is a simplistic model that introduces independent and identically distributed IDS errors. Studying this simplistic channel model gave us fundamental insight into the impact of IDS errors on code performance. The second and third channel models are more realistic extensions of the first model, where the second model includes strand erasures and the loss of ordering of the stored data, while the third model introduces correlated IDS errors. The design and optimization of the coding schemes for each case was done with the aid of asymptotic achievable information rates, finite-length bounds, extrinsic information transfer chart analysis, and density evolution.