Efficient File Random Access Method Based on Primer Index Matrix in DNA Storage Scenarios

ZHANG Shufang; LI Yuhui; LI Bingzhi

doi:10.11999/JEIT230717

Volume 46 Issue 6

Jun. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(6): 2568-2577

ZHANG Shufang, LI Yuhui, LI Bingzhi. Efficient File Random Access Method Based on Primer Index Matrix in DNA Storage Scenarios[J]. Journal of Electronics & Information Technology, 2024, 46(6): 2568-2577. doi: 10.11999/JEIT230717

Citation:

ZHANG Shufang, LI Yuhui, LI Bingzhi. Efficient File Random Access Method Based on Primer Index Matrix in DNA Storage Scenarios[J]. Journal of Electronics & Information Technology, 2024, 46(6): 2568-2577. doi: 10.11999/JEIT230717

Citation:

PDF( 3424 KB)

Efficient File Random Access Method Based on Primer Index Matrix in DNA Storage Scenarios

doi: 10.11999/JEIT230717

1.
School of Electrical and Information Engineering, Tianjin University, Tianjin 300072, China
2.
Frontiers Science Center for Synthetic Biology and Key Laboratory of Systems Bioengineering (Ministry of Education), School of Chemical Engineering and Technology, Tianjin University, Tianjin 300072, China
3.
Frontiers Research Institute for Synthetic Biology, Tianjin University, Tianjin 300072,China

Funds: Tianjin Science and Technology Plan Project (22JCYBJC01390)

Received Date: 2023-07-18
Rev Recd Date: 2024-03-17

Available Online: 2024-04-09

Publish Date: 2024-06-30

Abstract

Abstract

DNA molecules have the advantages of high density and stability, and are expected to become the medium for the next generation of massive data storage needs, which has received widespread attention in recent years. Currently, primers are used as the unique identifier for files, and random retrieval of DNA pool storage files can be achieved based on polymerase chain reaction (PCR) amplification technology. However, the allocation and mapping relationship between primers and files have not been thoroughly studied, and random allocation is still used to associate primers and files. This will lead to a decrease in the search efficiency of the target primer sequence, and saving the mapping relationship table between primers and files will cause a lot of data redundancy. In order to provide an efficient connection bridge between silicon-based computing devices and carbon-based storage systems, and effectively reduce the data redundancy caused by storing primer-file mapping relationships, a random retrieval method for DNA storage based on the primer index matrix is proposed in this paper. This method constructs a primer index matrix by dividing the stored file set according to different attributes of the file, and converts the primers in the primer library into an ordered primer library according to conversion rules. Finally, the mapping relationship between primers and files is optimized to achieve efficient and multi-dimensional retrieval during file random retrieval. The experimental results show that when storing file sets of different sizes, the efficiency of primer retrieval is improved to a constant level of time complexity by establishing the corresponding primer index matrix using the proposed algorithm in this paper, and the extra storage space required to store the mapping relationship between primers and files is optimized from linear growth to logarithmic growth.
- DNA storage,
- Random search,
- Primer index matrix

FullText(HTML)

References(23)

References

[1]	WIENER N. Machines smarter than men? Interview with Dr. Norbert wiener, noted scientist[R]. 1964: 84–86.
[2]	WELTER L, MAAROUF I, LENZ A, et al. Index-based concatenated codes for the multi-draw DNA storage channel[C]. Proceedings of 2023 IEEE Information Theory Workshop. Saint-Malo, France, 2023: 383–388. doi: 10.1109/ITW55543.2023.10161631.
[3]	CAO Ben, ZHANG Xiaokang, CUI Shuang, et al. Adaptive coding for DNA storage with high storage density and low coverage[J]. npj Systems Biology and Applications, 2022, 8(1): 23. doi: 10.1038/s41540-022-00233-w.
[4]	MEISER L C, NGUYEN B H, CHEN Y J, et al. Synthetic DNA applications in information technology[J]. Nature Communications, 2022, 13(1): 352. doi: 10.1038/s41467-021-27846-9.
[5]	DORICCHI A, PLATNICH C M, GIMPEL A, et al. Emerging approaches to DNA data storage: Challenges and prospects[J]. ACS Nano, 2022, 16(11): 17552–17571. doi: 10.1021/acsnano.2c06748.
[6]	TOMEK K J, VOLKEL K, INDERMAUR E W, et al. Promiscuous molecules for smarter file operations in DNA-based data storage[J]. Nature Communications, 2021, 12(1): 3518. doi: 10.1038/s41467-021-23669-w.
[7]	EL-SHAIKH A, WELZEL M, HEIDER D, et al. High-scale random access on DNA storage systems[J]. NAR Genomics and Bioinformatics, 2022, 4(1): lqab126. doi: 10.1093/nargab/lqab126.
[8]	LUO Yuan, WANG Shuchen, FENG Zhuowei, et al. Integrated microfluidic DNA storage platform with automated sample handling and physical data partitioning[J]. Analytical Chemistry, 2022, 94(38): 13153–13162. doi: 10.1021/acs.analchem.2c02667.
[9]	TABATABAEI YAZDI S M, YUAN Yongbo, MA Jian, et al. A rewritable, random-access DNA-based storage system[J]. Scientific Reports, 2015, 5: 14138. doi: 10.1038/srep14138.
[10]	ORGANICK L, ANG S D, CHEN Y J, et al. Random access in large-scale DNA data storage[J]. Nature Biotechnology, 2018, 36(3): 242–248. doi: 10.1038/nbt.4079.
[11]	CHURCH G M, GAO Yuan, and KOSURI S. Next-generation digital information storage in DNA[J]. Science, 2012, 337(6102): 1628. doi: 10.1126/science.1226355.
[12]	BORNHOLT J, LOPEZ R, CARMEAN D M, et al. A DNA-based archival storage system[C]. Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, New York, USA, 2016: 637–649. doi: 10.1145/2872362.2872397.
[13]	GRASS R N, HECKEL R, PUDDU M, et al. Robust chemical preservation of digital information on DNA in silica with error-correcting codes[J]. Angewandte Chemie International Edition, 2015, 54(8): 2552–2555. doi: 10.1002/anie.201411378.
[14]	BLAWAT M, GAEDKE K, HÜTTER I, et al. Forward error correction for DNA data storage[J]. Procedia Computer Science, 2016, 80: 1011–1022. doi: 10.1016/j.procs.2016.05.398.
[15]	ERLICH Y and ZIELINSKI D. DNA Fountain enables a robust and efficient storage architecture[J]. Science, 2017, 355(6328): 950–954. doi: 10.1126/science.aaj2038.
[16]	GOLDMAN N, BERTONE P, CHEN Siyuan, et al. Towards practical, high-capacity, low-maintenance information storage in synthesized DNA[J]. Nature, 2013, 494(7435): 77–80. doi: 10.1038/nature11875.
[17]	SONG Xin, SHAH Shalin, and REIF J. Multidimensional data organization and random access in large-scale DNA storage systems[J]. Theoretical Computer Science, 2021, 894: 190–202. doi: 10.1016/j.tcs.2021.09.021.
[18]	NEWMAN S, STEPHENSON A P, WILLSEY M, et al. High density DNA data storage library via dehydration with digital microfluidic retrieval[J]. Nature Communications, 2019, 10(1): 1706. doi: 10.1038/s41467-019-09517-y.
[19]	CHOI Y, BAE H J, LEE A C, et al. DNA micro-disks for the management of DNA-based data storage with index and write-once–read-many (WORM) memory features[J]. Advanced Materials, 2020, 32(37): 2001249. doi: 10.1002/adma.202001249.
[20]	LAU B, CHANDAK S, ROY S, et al. Magnetic DNA random access memory with nanopore readouts and exponentially-scaled combinatorial addressing[J]. Scientific Reports, 2023, 13(1): 8514. doi: 10.1038/s41598-023-29575-z.
[21]	HEID C A, STEVENS J, LIVAK K J, et al. Real time quantitative PCR[J]. Genome Research, 1996, 6(10): 986–994. doi: 10.1101/gr.6.10.986.
[22]	BANCROFT C, BOWLER T, BLOOM B, et al. Long-term storage of information in DNA[J]. Science, 2001, 293(5536): 1763–1765. doi: 10.1126/science.293.5536.1763c.
[23]	SECILMIS L, TESTOLINA M, LAZZAROTTO D, et al. Towards effective visual information storage on DNA support[C]//Proceedings of SPIE 12226, Applications of Digital Image Processing XLV, San Diego, USA, 2022: 1222605. doi: 10.1117/12.2636678.