access icon free Encoding scheme for data storage and retrieval on DNA computers

There has been exponential growth in the amount of data being generated on a daily basis. Such a huge amount of data creates a need for efficient data storage techniques. Due to the limitations of existing storage media, new storage solutions have always been of interest. There have been recent developments in order to efficiently use synthetic deoxyribonucleic acid (DNA) for information storage. DNA storage has attracted researchers because of its extremely high data storage density, about 1 exabyte/mm3 and long life under easily achievable conditions. This work presents an encoding scheme for DNA-based data storage system with controllable redundancy and reliability, the authors have also talked about the feasibility of the proposed method. The authors have also analysed the proposed algorithm for time and space complexity. The proposed encoding scheme tries to minimise the bases per letter ratio while controlling the redundancy. They have experimented with three different types of data with a value of redundancy as 0.75. In the randomised simulation setup, it was observed that the proposed algorithm was able to correctly retrieve the stored data in our experiments about 94% of the time. In the situation, where redundancy was increased to 1, the authors were able to retrieve all the information correctly in the proposed experiments.

Inspec keywords: DNA; computational complexity; storage media; biocomputing; digital storage

Other keywords: exponential growth; DNA computers; DNA-based data storage system; storage media; controllable redundancy; stored data; encoding scheme; information storage; extremely high data storage density; synthetic deoxyribonucleic acid

Subjects: Digital storage; Other topics in statistics; File organisation; Biocomputing techniques

References

    1. 1)
      • 27. Goldman, N., Bertone, P., Chen, S., et al: ‘Towards practical, high-capacity, low-maintenance information storage in synthesized DNA’, Nature, 2013, 494, (7435), pp. 7780.
    2. 2)
      • 25. Bornholt, J., Lopez, R., Carmean, D.M., et al: ‘A DNA-based archival storage system’. Int. Conf. on Architectural Support for Programming Languages and Operating Systems - ASPLOS, Atlanta, USA., April 2016, pp. 637649.
    3. 3)
      • 1. Adleman, L.M.: ‘Molecular computation of solutions to combinatorial problems’, Science, 1994, 266, (5187), pp. 10211024.
    4. 4)
      • 16. Acharya, A.K.: ‘Image encryption using a new chaos based encryption algorithm’. ACM Int. Conf. Proceeding Series, Rourkela, India, 2011, pp. 577581.
    5. 5)
      • 21. Banal, J.L., Shepherd, T.R., Berleant, J., et al: ‘Random access DNA memory in a scalable, archival file storage system’. bioRxiv, 2020, pp. 129.
    6. 6)
      • 44. Macdonald, J., Stefanovic, D., Stojanovic, M.N.: ‘DNA computers for work and play’, Sci. Am., 2008, 299, (5), pp. 8491.
    7. 7)
      • 15. Lipton, R.J.: ‘DNA solution of hard computational problems’, Science, 1995, 268, (5210), pp. 542545.
    8. 8)
      • 33. Kim, J., Hopfield, J.J., Winfree, E.: ‘Neural network computation by in vitro transcriptional circuits’. Neural Information Processing Systems, Vancouver, Canada, Decemebr 2004, pp. 681688.
    9. 9)
      • 42. Wood, D.H.: ‘DNA computing capabilities for game theory’, Nat. Comput., 2003, 2, (1), pp. 85108.
    10. 10)
      • 48. Reddy, A.R., Kumar, P.S.: ‘Predictive big data analytics in healthcare’. Proc. 2nd Int. Conf. on Computational Intelligence and Communication Technology, Ghaziabad, India, 2016, pp. 623626.
    11. 11)
      • 6. Sakamoto, K., Kiga, D., Komiya, K., et al: ‘State transitions by molecules’, BioSystems, 1999, 52, (1–3), pp. 8191.
    12. 12)
      • 38. Li, Y., Fang, C., Ouyang, Q.: ‘Genetic algorithm in DNA computing: a solution to the maximal clique problem’, Chinese Sci. Bull., 2004, 49, (9), pp. 967971.
    13. 13)
      • 28. Shimanovsky, B., Feng, J., Potkonjak, M.: ‘Hiding data in DNA’. Int. Workshop on Information Hiding, Noordwijkerhout, The Netherlands, October 2002, pp. 373386.
    14. 14)
      • 24. Sabry, M., Hashem, M., Nazmy, T.: ‘Three reversible data encoding algorithms based on DNA and amino acids’ structure’, Int. J. Comput. Appl., 2012, 54, (8), pp. 2430.
    15. 15)
      • 29. Takahashi, C.N., Nguyen, B.H., Strauss, K., et al: ‘Demonstration of End-to-End automation of DNA data storage’, Sci. Rep., 2019, 9, (1), pp. 15.
    16. 16)
      • 2. Kari, L.: ‘DNA computing: arrival of biological mathematics’, Math. Intell., 1997, 19, (2), pp. 922.
    17. 17)
      • 20. Church, G.M., Gao, Y., Kosuri, S.: ‘Next-generation digital information storage in DNA’, Science, 2012, 337, (6102), p. 1628.
    18. 18)
      • 40. Ibrahim, Z., Kurniawan, T.B., Khalid, N.K., et al: ‘Implementation of an ant colony system for DNA sequence optimization’, Artif. Life Robot., 2009, 14, (2), pp. 293296.
    19. 19)
      • 45. Challagulla, N.V., Rohatgi, V., Sharma, D., et al: ‘Recent developments of nanomaterial applications in additive manufacturing: a brief review’, Curr. Opin. Chem. Eng., 2020, 28, pp. 7582.
    20. 20)
      • 3. Kari, L., Seki, S., Sosík, P.: ‘DNA computing-foundations and implications’, in Rozenberg, G. (Ed.): ‘Handbook of natural computing’ (Springer, Berlin Heidelberg, 2012), pp. 10731127.
    21. 21)
      • 46. Raghupathi, W., Raghupathi, V.: ‘Big data analytics in healthcare: promise and potential’, Heal. Inf. Sci. Syst., 2014, 2, (1), p. 3.
    22. 22)
      • 41. Dorigo, M., Gambardella, L.M.: ‘Ant colony system: A cooperative learning approach to the traveling salesman problem’, IEEE Trans. Evol. Comput., 1997, 1, (1), pp. 5366.
    23. 23)
      • 19. Ellaway, R.H., Pusic, M. V., Galbraith, R.M., et al: ‘Developing the role of big data and analytics in health professional education’, Med. Teach., 2014, 36, (3), pp. 216222.
    24. 24)
      • 39. Kuurniawan, T.B., Khalid, N.K., Ibrahim, Z., et al: ‘Sequence design for direct-proportional length-based DNA computing using population-based ant colony optimization’. Proc. ICCAS-SICE, Fukuoka, Japan, November 2009, pp. 14861491.
    25. 25)
      • 22. Selvaraj, S., Sundaravaradhan, S.: ‘Challenges and opportunities in Iot healthcare systems: a systematic review’, SN Appl. Sci., 2020, 2, (1), p. 139.
    26. 26)
      • 4. Pisanti, N.: ‘DNA computing: A survey’, Bulletin of the EATCS, 1998, 64, pp. 188216.
    27. 27)
      • 26. Bancroft, C.: ‘Long-term storage of information in DNA’, Science, 2001, 293, (5536), p. 1763.
    28. 28)
      • 35. Ren, L., Ding, Y., Ying, H., et al: ‘Emergence of self-learning fuzzy systems by a new virus DNA-based evolutionary algorithm’, Int. J. Intell. Syst., 2003, 18, (3), pp. 339354.
    29. 29)
      • 36. Yoshikawa, T., Furuhashi, T., Uchikawa, Y.: ‘Effects of combination of DNA coding method with pseudo-bacterial GA’. Proc. of the IEEE Conf. on Evolutionary Computation, ICEC, Indianapolis, USA., April 1997, pp. 285290.
    30. 30)
      • 14. Liu, Q., Wang, L., Frutos, A.G., et al: ‘DNA computing on surfaces’, Nature, 2000, 403, (6766), pp. 175179.
    31. 31)
      • 34. Chen, J., Antipov, E., Lemieux, B., et al: ‘DNA computing implementing genetic algorithms’. Evolution as Computation DIMACS Workshop, Princeton, USA., January 1999, pp. 3949.
    32. 32)
      • 37. Deaton, R., Murphy, R.C., Rose, J.A., et al: ‘DNA based implementation of an evolutionary search for good encodings for DNA computation’. Proc. IEEE Conf. on Evolutionary Computation, ICEC, Indianapolis, USA., April 1997, pp. 267271.
    33. 33)
      • 13. Ouyang, Q., Kaplan, P.D., Liu, S., et al: ‘DNA solution of the maximal clique problem’, Science, 1997, 278, (5337), pp. 446449.
    34. 34)
      • 49. Erlich, Y., Zielinski, D.: ‘DNA fountain enables a robust and efficient storage architecture’, Science, 2017, 355, (6328), pp. 950954.
    35. 35)
      • 5. Ezziane, Z.: ‘DNA computing: applications and challenges’, Nanotechnology, 2006, 17, (2), p. R27.
    36. 36)
      • 8. Winfree, E., Yang, X., Seeman, N.: ‘Universal computation via self-assembly of DNA: some theory and experiments’, in Landweber, L.F. (Ed.): ‘DNA based computers II’ (American Mathematical Society, USA., 1996), pp. 191213.
    37. 37)
      • 31. Qian, L., Winfree, E., Bruck, J.: ‘Neural network computation with DNA strand displacement cascades’, Nature, 2011, 475, (7356), pp. 368372.
    38. 38)
      • 10. Leete, T., Klein, J., Rubin, H.: ‘Bit operations using a DNA template’. Proc. of the Third DIMACS Workshop on DNA-based Computers, Philadelphia, USA., June 1997), pp. 159166.
    39. 39)
      • 47. Kayyali, B., Knott, D., Van, K.S.: ‘The big-data revolution in US health care: accelerating value and innovation’, McKinsey Co., 2013, 2, (8), pp. 113.
    40. 40)
      • 43. Cukras, A.R., Faulhammer, D., Lipton, R.J., et al: ‘Chess games: A model for RNA based computation’, Biosystems, 1999, 52, (1–3), pp. 3545.
    41. 41)
      • 11. Klein, J.P., Leete, T.H., Rubin, H.: ‘A biomolecular implementation of logically reversible computation with minimal energy dissipation’, Biosystems, 1999, 52, (1–3), pp. 1523.
    42. 42)
      • 9. Frank Guarnieri, C.B.: ‘Use of a horizontal chain reaction for DNA-based addition’, in Landweber, L.F. (Ed.): ‘DNA based computers II’ (American Mathematical Society, USA., 1996), pp. 105111.
    43. 43)
      • 30. Organick, L., Chen, Y.J., Dumas Ang, S., et al: ‘Probing the physical limits of reliable DNA data retrieval’, Nat. Commun., 2020, 11, (1), pp. 17.
    44. 44)
      • 17. Mondal, B., Mandal, T.: ‘A light weight secure image encryption scheme based on chaos & DNA computing’, J. King Saud Univ. - Comput. Inf. Sci., 2017, 29, (4), pp. 499504.
    45. 45)
      • 23. Dimitrov, D.V.: ‘Medical internet of things and big data in healthcare’, Healthc. Inform. Res., 2016, 22, (3), pp. 156163.
    46. 46)
      • 7. Chen, X., Ellington, A.D.: ‘Shaping up nucleic acid computation’, Curr. Opin. Biotechnol., 2010, 21, (4), pp. 392400.
    47. 47)
      • 18. Hermassi, H., Belazi, A., Rhouma, R., et al: ‘Security analysis of an image encryption algorithm based on a DNA addition combining with chaotic maps’, Multimed. Tools Appl., 2014, 72, (3), pp. 22112224.
    48. 48)
      • 12. Hasudungan, R., Pangestuty, D.M., Latifah, A.J.: ‘Solving Minimum Vertex cover problem using DNA computing’, Journal of Physics: Conf. Series, Medan, Indonesia, Vol. 1361, November 2018, pp. 012038.
    49. 49)
      • 32. Cherry, K.M., Qian, L.: ‘Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks’, Nature, 2018, 559, (7714), pp. 370376.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-nbt.2020.0157
Loading

Related content

content/journals/10.1049/iet-nbt.2020.0157
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading