LIPIcs.DNA.27.11.pdf
- Filesize: 1.42 MB
- 21 pages
Document
Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching
Authors
Arnav Solanki 
,
Marc Riedel
-
Part of:
Volume:
27th International Conference on DNA Computing and Molecular Programming (DNA 27)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on DNA Computing and Molecular Programming - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-09-08
File
Document Identifiers
Author Details
- Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN, USA
Acknowledgements
We thank David Soloveichik, Olgica Milenkovic, Boya Wang, and Cameron Chalk.
Cite As Get BibTex
Tonglin Chen, Arnav Solanki, and Marc Riedel. Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DNA.27.11
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.
Subject Classification
ACM Subject Classification
- Computing methodologies → Parallel computing methodologies
- Applied computing → Computational biology
Keywords
- Molecular Computing
- DNA Computing
- DNA Storage
- Parallel Computing
- Strand Displacement
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Leonard M Adleman. Molecular computation of solutions to combinatorial problems. Science, pages 1021-1024, 1994.
-
Nagendra Athreya, Olgica Milenkovic, and Jean-Pierre Leburton. Detection and mapping of dsDNA breaks using graphene nanopore transistor. Biophysical Journal, 116(3):292a, 2019.
- Luis Ceze, Jeff Nivala, and Karin Strauss. Molecular digital data storage using DNA. Nature Reviews Genetics, 20(8):456-466, August 2019. URL: https://doi.org/10.1038/s41576-019-0125-3.
- George Church, Yuan Gao, and Sriram Kosuri. Next-generation digital information storage in DNA. Science (New York, N.Y.), 337:1628, August 2012. URL: https://doi.org/10.1126/science.1226355.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
-
M. J. Flynn. Some computer organizations and their effectiveness. IEEE Transactions on Computers, C-21(9):948-960, 1972.
-
Joachim Krug and Herbert Spohn. Universality classes for deterministic surface growth. Physical Review A, 38(8):4271, 1988.
-
Wentian Li. Power spectra of regular languages and cellular automata. Complex Systems, 1(1):107-130, 1987.
-
Ke Liu, Chao Pan, Alexandre Kuhn, Adrian Pascal Nievergelt, Georg E Fantner, Olgica Milenkovic, and Aleksandra Radenovic. Detecting topological variations of DNA at single-molecule level. Nature communications, 10(1):1-9, 2019.
- David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences, 107(12):5393-5398, 2010. URL: https://doi.org/10.1073/pnas.0909380107.
- S. Tabatabaei, Boya Wang, Nagendra Athreya, Behnam Enghiad, Alvaro Hernandez, Christopher Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, and Olgica Milenkovic. DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nature Communications, 11, December 2020. URL: https://doi.org/10.1038/s41467-020-15588-z.
-
S Kasra Tabatabaei, Boya Wang, Nagendra Bala Murali Athreya, Behnam Enghiad, Alvaro Gonzalo Hernandez, Christopher J Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, and Olgica Milenkovic. DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nature communications, 11(1):1-10, 2020.
-
Boya Wang, Cameron Chalk, and David Soloveichik. SIMD||DNA: Single instruction, multiple data computation with DNA strand displacement cascades. In Chris Thachuk and Yan Liu, editors, DNA Computing and Molecular Programming, pages 219-235, Cham, 2019. Springer International Publishing.
-
Bernard Yurke. A DNA-fuelled molecular machine made of DNA. Nature, 406(6796: 605), 2000.