Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Natural Computing

21-09-2023

Parallel pairwise operations on data stored in DNA: sorting, XOR, shifting, and searching

Authors: Arnav Solanki, Tonglin Chen, Marc Riedel

Published in: Natural Computing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Prior research has introduced the Single-Instruction-Multiple-Data paradigm for DNA computing (SIMD DNA). It offers the potential for storing information and performing in-memory computations on DNA, with massive parallelism. This paper introduces three new SIMD DNA operations: sorting, shifting, and searching. Each is a fundamental operation in computer science. Our implementations demonstrate the effectiveness of parallel pairwise operations with this new paradigm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
Perhaps counter-intuitively, sorting binary values in hardware is as difficult algorithmically as sorting arbitrary values such as integers or real numbers (Cormen et al. 2009).
 
Literature
Adleman LM (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021–1024CrossRef
Athreya N, Milenkovic O, Leburton J-P (2019) Detection and mapping of dsDNA breaks using graphene nanopore transistor. Biophys J 116(3):292CrossRef
Broadwater DB, Kim HD (2016) The effect of basepair mismatch on DNA strand displacement. Biophys J 110(7):1476–1484CrossRef
Chen T, Solanki A, Riedel M (2021) Parallel pairwise operations on data stored in DNA: sorting, shifting, and searching. In: 27th international conference on DNA computing and molecular programming (DNA 27). Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, LondonMATH
Flynn MJ (1972) Some computer organizations and their effectiveness. IEEE Trans Comput 21(9):948–960CrossRefMATH
Li L, Jiang W, Lu Y (2018) A modified Gibson assembly method for cloning large DNA fragments with high GC contents. Synth Metab Pathw Methods Protoc 203–209
Liu K, Pan C, Kuhn A, Nievergelt AP, Fantner GE, Milenkovic O, Radenovic A (2019) Detecting topological variations of DNA at single-molecule level. Nat Commun 10(1):1–9
Radding C.M, Beattie K.L, Holloman W.K, Wiegand R.C (1977) Uptake of homologous single-stranded fragments by superhelical dna: Iv. branch migration. Journal of molecular biology 116(4), 825–839
Salehi SA, Jiang H, Riedel MD, Parhi KK (2015) Molecular sensing and computing systems. IEEE Trans Mol Biol Multi-Scale Commun 1(3):249–264CrossRef
Tabatabaei SK, Wang B, Athreya NBM, Enghiad B, Hernandez AG, Fields CJ, Leburton J-P, Soloveichik D, Zhao H, Milenkovic O (2020) DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nat Commun 11(1):1–10CrossRef
Wang B, Chalk C, Soloveichik D (2019) SIMD||DNA: single instruction, multiple data computation with DNA strand displacement cascades. In: Thachuk C, Liu Y (eds) DNA computing and molecular programming. Springer, Cham, pp 219–235CrossRefMATH
Yurke B, Turberfield AJ, Mills AP, Simmel FC, Neumann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406(6796):605–608CrossRef
Metadata
Title
Parallel pairwise operations on data stored in DNA: sorting, XOR, shifting, and searching
Authors
Arnav Solanki
Tonglin Chen
Marc Riedel
Publication date
21-09-2023
Publisher
Springer Netherlands
Published in
Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-023-09964-z

Premium Partner

    Image Credits