Methods for Constraint Satisfaction, Error Handling, and Data Recovery in DNA Data Storage
Loading...
Files
Date
Publisher
Philipps-Universität Marburg
Abstract
The ever-increasing generation of digital data has created unprecedented challenges for data storage and preservation. Since current data storage technologies do not provide means for adequate long-term retention, storage density, resource efficiency, and cost if used for very long time periods, novel solutions are required. Deoxyribonucleic acid (DNA) with its various beneficial properties has emerged as a promising medium for long-term data storage. Due to its superior density, durability, and stability compared to conventional storage technologies, as well as its inherent relevance for humanity, DNA is an interesting medium for long-term data storage. However, the biological nature of DNA introduces unique constraints and error characteristics that must be addressed through computational methods tailored to DNA data storage. Additionally, since research in the field of synthetic biology and DNA sequencing is progressing rapidly, technologies currently deemed error-prone, expensive, or generally infeasible may be attractive in the future. This thesis presents novel contributions to improve the effectiveness and reliability of DNA data storage systems, especially those based on fountain coding schemes. The research in the thesis encompasses three key areas in which significant improvements are presented: simulation of DNA data storage, data encoding/decoding, and postprocessing using various sequence repair and data recovery methods. Since performing in-vitro experiments is still expensive and time-consuming, the use of computer simulations is a feasible approach to accelerate research while allowing comparability and reproducibility. Thus, the first research area presented in this thesis includes a versatile simulation framework for the simulation of each step involved in a typical DNA data storage process. To increase usability, this approach does not only include predefined methods, but supports the simulation of user-defined scenarios. The second research area covered in this thesis involves contributions towards efficient, constraint-adhering, and error-resilient data coding schemes for DNA data storage. This involves the creation of novel coding schemes based on fountain codes, as well as the optimization of fountain codes for DNA data storage. Furthermore, since state-of-the-art DNA data storage systems are error-prone and the presence of errors in such a biological medium can never be fully avoided, various methods for postprocessing, sequence repair, and recovery of corrupted data are introduced in the third research area of this thesis. The methods presented in this work thus represent key building blocks for realizing practical, large-scale DNA data storage systems.
Die ständig wachsende Erzeugung digitaler Daten stellt die Datenspeicherung und -aufbewahrung vor nie dagewesene Herausforderungen. Da die derzeitigen Technologien zur Speicherung von Daten keine Mittel für eine angemessene langfristige Aufbewahrung, Speicherdichte, Ressourceneffizienz und Kosten bei sehr langer Nutzung bieten, sind neue Lösungen erforderlich. Die Desoxyribonukleinsäure (DNS – eng.: DNA) mit ihren verschiedenen vorteilhaften Eigenschaften hat sich als vielversprechendes Medium für die langfristige Datenspeicherung erwiesen. Aufgrund ihrer im Vergleich zu herkömmlichen Speichertechnologien überlegenen Dichte, Haltbarkeit und Stabilität sowie ihrer inhärenten Bedeutung für die Menschheit ist die DNA ein interessantes Medium für die langfristige Datenspeicherung. Die biologische Natur der DNA bringt jedoch einzigartige Einschränkungen und Fehlereigenschaften mit sich, die von auf die DNA-Datenspeicherung zugeschnittenen Kodierungsmethoden berücksichtigt werden müssen. Da die Forschung auf dem Gebiet der synthetischen Biologie und der DNASequenzierung sehr schnell voranschreitet, könnten Technologien, die derzeit als fehleranfällig, teuer oder generell nicht praktikabel gelten, in Zukunft attraktiv sein. In dieser Arbeit werden neue Beiträge zur Verbesserung der Effektivität und Zuverlässigkeit von DNA-Datenspeichersystemen vorgestellt, insbesondere von solchen, die Fountain Codes verwenden. Die Forschung in dieser Arbeit konzentriert sich auf drei Schlüsselbereiche, in denen signifikante Verbesserungen vorgestellt werden: Simulation der DNA-Datenspeicherung, Kodierung/Dekodierung von Daten und Nachbearbeitung mit verschiedenen Sequenzreparaturund Datenwiederherstellungsmethoden. Da die Durchführung von In-vitro-Experimenten nach wie vor teuer und zeitaufwändig ist, ist der Einsatz von Computersimulationen ein geeigneter Ansatz, um die Forschung zu beschleunigen und gleichzeitig Vergleichbarkeit und Reproduzierbarkeit zu gewährleisten. Der erste Forschungsbereich, der in dieser Arbeit vorgestellt wird, umfasst daher einen flexiblen Ansatz für die Nachbildung der einzelnen Schritte eines typischen DNA-Speicherprozesses. Um die Benutzbarkeit zu erhöhen, enthält dieser Ansatz dabei nicht nur vordefinierte Methoden, sondern unterstützt auch die Simulation von benutzerdefinierten Szenarien. Der zweite in dieser Arbeit behandelte Forschungsbereich umfasst Beiträge zur Erforschung effizienter, Bedingungen einhaltender und fehlerresistenter Kodierungsverfahren für die Speicherung von Daten in DNA. Dies beinhaltet die Entwicklung neuartiger auf Fountain Codes basierender Kodierungsschemata sowie die Optimierung dieser Kodierungen für DNADatenspeicher. Da moderne DNA-Speichersysteme fehleranfällig sind und das Vorhandensein von Fehlern in einem solchen biologischen Medium nie vollständig vermieden werden kann, werden außerdem verschiedene Methoden zur Nachbearbeitung, Sequenzreparatur und Wiederherstellung von beschädigten Daten im dritten Forschungsbereich dieser Dissertation vorgestellt. Die in dieser Arbeit vorgestellten Methoden stellen somit wichtige Bausteine für die Realisierung von in der Praxis nutzbaren DNA-Speichersysteme für große Datenmengen dar.