DNA Hypernetworks for Information Storage and Retrieval | SpringerLink
Skip to main content
Springer Nature Link
Log in

DNA Hypernetworks for Information Storage and Retrieval

  • Conference paper
DNA Computing (DNA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4287))

Included in the following conference series:

Abstract

Content-addressability is a fundamental feature of human memory underlying many associative information retrieval tasks. In contrast to location-based memory devices, content-addressable memories require complex interactions between memory elements, which makes conventional computation paradigms difficult. Here we present a molecular computational model of content-addressable information storage and retrieval which makes use of the massive interaction capability of DNA molecules in a reaction chamber. This model is based on the “hypernetwork” architecture which is an undirected hypergraph of weighted edges. We describe the theoretical basis of the hypernetwork model of associative memory and its realization in DNA-based computing. A molecular algorithm is derived for automatic storage of data into the hypernetwork, and its performance is examined on an image data set. In particular, we study the effect of the hyperedge cardinality and error tolerance on the associative recall performance. Our simulation results demonstrate that short DNA strands in a vast number can be effective in some pattern information processing tasks whose implementation is within reach of current DNA nanotechnology.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baum, E.B.: Building an associative memory vastly larger than the brain. Science 268, 583–585 (1995)

    Article  Google Scholar 

  2. Berge, C.: Graphs and Hypergraphs. North-Holland Publishing, Amsterdam (1973)

    MATH  Google Scholar 

  3. Chen, J., Deaton, R., Wang, Y.-Z.: A DNA-based memory with in vitro learning and associative recall. In: Chen, J., Reif, J.H. (eds.) DAN 2003. LNCS, vol. 2943, pp. 145–156. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  4. Chisvin, L., Duckworth, R.J.: Content-addressable and associative memory: Alternatives to the ubiquitous RAM. IEEE Computer 22(7), 51–64 (1989)

    Google Scholar 

  5. Garzon, M., Bobba, K., Neel, A.: Efficiency and reliability of semantic retrieval in DNA-based memories. In: Chen, J., Reif, J.H. (eds.) DAN 2003. LNCS, vol. 2943, pp. 157–169. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  6. Hopfield, J.: Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Nat. Acad. Sci. 81, 3088–3092 (1984)

    Article  Google Scholar 

  7. Hinton, G.E., Dayan, P., Frey, B.J., Neal, R.M.: The wake-sleep algorithm for unsupervised neural networks. Science 268, 1158–1161 (1995)

    Article  Google Scholar 

  8. Kohonen, T.: Content-Addressable Memories. Springer, Berlin (1980)

    MATH  Google Scholar 

  9. Paziamtzis, K., Sheikholeslami, A.: A low-power content-addressable memory (CAM) using pipelined hierarchical search scheme. IEEE Journal of Solid-State Circuits 39(9), 1512–1519 (2004)

    Article  Google Scholar 

  10. Reif, J.H., LaBean, T.H., Pirrung, M., Rana, V.S., Guo, B., Kingsford, C., Wickham, G.S.: Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability. In: Jonoska, N., Seeman, N.C. (eds.) DNA 2001. LNCS, vol. 2340, pp. 231–247. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  11. Thurber, K.J., Wald, L.D.: Associative and parallel processors. ACM Computing Surveys 7(4), 215–225 (1975)

    Article  MATH  Google Scholar 

  12. Zhang, B.-T., Jang, H.-Y.: A Bayesian Algorithm for In Vitro Molecular Evolution of Pattern Classifiers. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 458–467. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  13. Zhang, B.-T., Yang, J.-S., Chi, S.-W.: Self-organizing latent lattice models for temporal gene expression profiling. Machine Learning 52(1/2), 67–89 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Biointelligence Laboratory, School of Computer Science and Engineering, Seoul National University, Seoul, 151-742, Korea

    Byoung-Tak Zhang & Joo-Kyung Kim

Authors
  1. Byoung-Tak Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joo-Kyung Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Chemistry, Purdue University, 560 Oval Drive, 47907-2084, West Lafayette, IN, USA

    Chengde Mao

  2. Faculty of Education and Integrated Arts and Sciences, Department of Mathematics, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, 169-8050, Tokyo, Japan

    Takashi Yokomori

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zhang, BT., Kim, JK. (2006). DNA Hypernetworks for Information Storage and Retrieval. In: Mao, C., Yokomori, T. (eds) DNA Computing. DNA 2006. Lecture Notes in Computer Science, vol 4287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925903_23

Download citation

  • DOI: https://doi.org/10.1007/11925903_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49024-1

  • Online ISBN: 978-3-540-68423-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation