DupLeTh: DNA Depolama Sistemlerinde LT Kodları Kullanıldığında Kısmi Kapsama Derinliği Problemi

Öz

Bu çalışmada, depolanan verinin kısmi geriçatması kabul edilen DNA depolama sistemlerinde kapsama derinliği sorununu incelemekteyiz. Kapsama derinliği sorunu DNA depolama sistemlerinde, her DNA ipliği tipinden en az t kopyanın elde edilmesi için gerekli olan dizileme (sequencing) boyutunu ifade etmektedir. Bu kapsamda, kısmi geriçatılması kabul edilebilen video gibi veri türlerini depolayan bir DNA depolama sisteminde LT kodlarının kullanımı, kapsama derinliği boyutu performansı açısından analiz edilmektedir. Başka bir deyişle, bir DNA depolama sisteminde, orijinal sembollerin yalnızca bir kısmının geriçatılabileceği kabul edildiğinde, LT kodlarının kapsama derinliği analiz edilmektedir. Bu noktada, LT kodları tarafından kodlanan DNA ipliklerinin t kopyasını elde etmek için Çift Fazlı LT Kapsama Derinliği (DupLeTh) olarak adlandırılan yeni bir algoritma önerilmektedir. Ek olarak, verinin hem bütününün hem de bir kısmının (kısmi) geriçatılmasının kabul edildiği bir sistemde, lüteratürde kullanılması önerilen MDS (Maximum Distance Separable) kodlarının da kapsama derinliği açısından performansı incelenmiştir. Ayrıca, LT kodlarının kullanıldığı önerilen DupLeTh algoritmasının kapsama derinliği performansını değerlendirmek için bu algoritma hem kısmi ve hem de geleneksel (bütünsel) MDS derinliği yaklaşımları kullanılarak Monte Carlo simülasyonları ile kıyaslanmıştır. Sonuçlara göre, DupLeTh tabanlı LT kodları, kısmi ve geleneksel MDS kapsama derinliği yaklaşımlarına göre çok daha düşük boyutta dizileme (sequencing) gerektirmektedir.

Anahtar Kelimeler

• DNA depolama
• Çeşme kodları
• LT kodları
• Kapsama derinliği problemi

DupLeTh: The Partial Coverage Depth Problem in DNA Storage Systems using LT Codes

Öz

In this paper, we study the coverage depth problem in DNA storage systems with partial reconstruction. The coverage depth problem refers to the sequencing depth of DNA storage, ensuring that at least t copies of each type of DNA strand are obtained. In this context, the use of LT codes in a DNA storage system that stores video-like data whose partial reconstruction is acceptable is analysed with respect to coverage depth performance in a partial-recovery setting. In other words, in a DNA storage system when it is accepted that only a fraction of the original symbols can be reconstructed, the coverage depth of LT codes is analysed. At this point, we propose a new algorithm named Double phase LT Coverege DepTh (DupLeTh), to obtain t copies of DNA strands encoded by LT codes. In addition, when both entire and partial reconstruction are enabled in a system, the performance of MDS codes with respect to coverage depth is also investigated. Furthermore, Monte Carlo simulations were conducted to assess the results for the coverage depth size in both traditional (entire) and partial MDS as well as the partial LT coverage depth problems using the DupLeTh algorithm. According to the results, LT codes based on DupLeTh requires fewer sequencing size than those in the partial and traditional MDS coverage depth approaches.

Anahtar Kelimeler

• DNA storage
• Fountain codes
• LT codes
• Coverage depth problem

Kaynakça

1. Bar-Lev D., Sabary O., Gabrys R., Yaakobi E. Cover your bases: How to minimize the sequencing coverage in DNA storage systems. IEEE Transactions on Information Theory 2024; 71(1): 192-217
2. Bertuzzo M., Ravagnani A., Yaakobi E. The coverage depth problem in DNA storage over small alphabets. Arxiv 2025; Available from: https://arxiv.org/abs/2507.20639
3. Boruchovsky A., Bar Lev D., Yaakobi E. DNA correcting codes: End to end correction in DNA storage systems. IEEE Transactions on Information Theory. 2025; 71(6): 4214–4227.
4. Cao B., Zhang X., Cui S., Zhang Q. Adaptive coding for DNA storage with high storage density and low coverage. NPJ Systems Biology and Applications 2022; 8(1): 1-12.
5. Ceze L., Nivala J., Strauss K. Molecular digital data storage using DNA. Nature Reviews Genetics 2019; 20(8): 456–466.
6. Chandak S., Tatwawadi K., Lau B., Mardia J., Kubit M., Neu J., Griffin P., Wootters M., Weissman T., Ji H. Improved read/write cost tradeoff in DNA-based data storage using LDPC Codes. 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), October 2019; Monticello, IL, USA.
7. Church GM., Gao Y., Kosuri S. Next-generation digital information storage in DNA. Science 2012; 337(6102): 1628.
8. Clarke J., Wu H-C., Jayasinghe L., Patel A., Reid S., Bayley H. Continuous base identification for single-molecule nanopore DNA sequencing. Nature Nanotechnology 2009; 4(4): 265–270.

9. Elerath JG., Shah S. Server class disk drives: how reliable are they? Annual Symposium Reliability and Maintainability 29 January 2004, Los Angeles, CA, USA.
10. Erdős P., Rényi A. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutató Int. Közl. 1961; 6(1–2) :215–20.
11. Feynman RP. There’s plenty of room at the bottom. Journal of Microelectromechanical Systems, IEEE 1992; 1(1): 60–66.
12. Flajolet P., Gardy D., Thimonier L. Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Applied Mathematics Elsevier 1992; 39(3): 207–229.
13. Gibson DG., Glass JI., Lartigue C., Noskov VN., Chuang RY., Algire MA., Benders GA., Montague MG., Ma L., Moodie MM., Merryman C, Vashee S., Krishnakumar R., Assad-Garcia N., Andrews-Pfannkoch C., Denisova EA., Young L., Qi Z., Segall-Shapiro TH., Calvey CH., Parmar PP., Hutchison CA, Smith HO., Venter JG. Creation of a bacterial cell controlled by a chemically synthesized genome. Science 2010; 329(5987): 52–56.
14. Goldman N., Bertone P., Chen S., Dessimoz C., LeProust EM., Sipos B., Ewan Birney. Towards practical, high-capacity, low-maintenance information storage in synthesized DNA. Nature. 2013; 494(7435): 77–80.
15. Grass RN., Heckel R., Puddu M., Paunescu D., Stark W.J. Robust chemical preservation of digital information on DNA in silica with error-correcting codes. Angewandte Chemie International Edition 2015; 54(8): 2552–2555.
16. Gruica A., Bar-Lev D., Ravagnani A., Yaakobi EA. Combinatorial perspective on random access efficiency for DNA storage. IEEE International Symposium on Information Theory (ISIT), 07-12 July 2024, Athens, Greece.
17. Herman J., Usher W., SALib: An open-source Python library for sensitivity analysis. Journal of Open Source Software 2017; 2(9)
18. Jo S., Shin H., Joe SY., Baek D., Park C., Chun H. Recent progress in DNA data storage based on high-throughput DNA synthesis. Biomed. Eng. Lett. 2024; 14: 993–1009.
19. Lee HH., Kalhor R., Goela N., Bolot J., Church GM. Terminator-free template-independent enzymatic DNA synthesis for digital information storage. Nature Communications 2019; 10(1): 2383.
20. Luby M. LT Codes. 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada.
21. Luby M.., Mitzenmacher M., Shokrollahi MA., Spielman DA. Efficient erasure correcting codes. IEEE Transactions on Information Theory 2001; 47(2): 569–584.
22. Madadelahi M., Agarwal R., Martinez-Chapa SO., Madou MJ. A roadmap to high-speed polymerase chain reaction (PCR): COVID-19 as a technology accelerator. Biosensors and Bioelectronics 2024; 246:115830.
23. Organick L., Ang SD., Chen YJ., Lopez R., Yekhanin S., Makarychev K., Racz MZ., Kamath G., Gopalan P., Nguyen B., Takahashi CN., Newman S., Parker HY., Rashtchian C., Stewart K., Gupta G., Carlson R., Mulligan J., Carmean D., Seelig G., Ceze L., Strauss K. Random access in large-scale DNA data storage. Nature Biotechnology 2018; 36(3): 242–248.
24. Preuss I., Galili B., Yakhini Z., Anavy L. Sequencing Coverage Analysis for Combinatorial DNA-Based Storage Systems. IEEE Transactions on Molecular, Biological, and Multi-Scale Communications 2024; 10(2): 297–316.
25. Reed IS., Solomon G. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics 1960; 8(2): 300–304.
26. Sandahl AF., Nguyen TJD., Hansen RA., Johansen MB., Skrydstrup T., Gothelf KV. On-demand synthesis of phosphoramidites. Nature Communications 2021; 12(2760): 1-7.
27. Schwarz PM., Freisleben B. NOREC4DNA: using near-optimal rateless erasure codes for DNA storage. BMC Bioinformatics 2021; 22(1): 406.
28. Schwarz PM., Freisleben B. Data recovery methods for DNA storage based on fountain codes. Computational and Structural Biotechnology 2024; 23: 1808–1823.
29. Shokrollahi A., Stockhammer T., Luby M., Watson M. Raptor forward error correction scheme for object delivery. RFC Editor 2007; 5053: 1-46. Available from: https://www.rfc-editor.org/info/rfc5053
30. Sokolovskii R., Agarwal P., Alberto CL., Zhou Z., Heinis T. Coding over coupon collector channels for combinatorial motif-based DNA storage. IEEE Transactions on Communications 2025; 73(6): 3750–3760.
31. Sobol IM. Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Mathematics and Computers in Simulation 2001; 55(1-3): 271-280
32. Stanley PM., Strittmatter LM., Vickers AM., Lee KCK. Decoding DNA data storage for investment. Biotechnology Advances 2020; 45: 107639-107646.
33. Tabatabaei SK., Wang B., Athreya NBM., Enghiad B., Hernandez AG., Fields CJ., Leburton JP., Soloveichik D., Zhao H., Milenkovic O. DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nature Communications 2020; 11(1): 1742.
34. Tang N., Chen C., Han YS. Fast error and erasure decoding algorithm for Reed–Solomon codes, IEEE Communication Letters 2024; 28(4): 759–762.
35. Watson JD., Crick FHC. Molecular structure of nucleic acids: a structure for deoxyribose nucleic acid. Nature 1953; 171(4356): 737–738.
36. Yan Z., Zhang H., Lu B., Han T., Tong X. Yuan Y. DNA palette code for time-series archival data storage. National Science Review 2024; 12(1): 1-9 .