Cargando…
Prime factorization via localized tile assembly in a DNA origami framework
Modern cybersecurity built on public-key cryptosystems like Rivest-Shamir-Adleman is compromised upon finding solutions to the prime factorization. Nevertheless, solving the prime factorization problem, given a large N, remains computationally challenging. Here, we design DNA origami frameworks (DOF...
Autores principales: | , , , , , , , , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
American Association for the Advancement of Science
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10065441/ https://www.ncbi.nlm.nih.gov/pubmed/37000880 http://dx.doi.org/10.1126/sciadv.adf8263 |
_version_ | 1785018112791281664 |
---|---|
author | Zhang, Yinan Yin, Xiaoyao Cui, Chengjun He, Kun Wang, Fei Chao, Jie Li, Tao Zuo, Xiaolei Li, Ailing Wang, Lihua Wang, Na Bo, Xiaochen Fan, Chunhai |
author_facet | Zhang, Yinan Yin, Xiaoyao Cui, Chengjun He, Kun Wang, Fei Chao, Jie Li, Tao Zuo, Xiaolei Li, Ailing Wang, Lihua Wang, Na Bo, Xiaochen Fan, Chunhai |
author_sort | Zhang, Yinan |
collection | PubMed |
description | Modern cybersecurity built on public-key cryptosystems like Rivest-Shamir-Adleman is compromised upon finding solutions to the prime factorization. Nevertheless, solving the prime factorization problem, given a large N, remains computationally challenging. Here, we design DNA origami frameworks (DOFs) to direct localized assembly of double-crossover (DX) tiles for solving prime factorization with a model consisting of the computing, decision-making, and reporting motifs. The model implementation is based on the sequential assembly of different DX tiles in the DOF cavity that carries overhangs encoding the prime and composite integers. The primes are multiplied and then verified with the composite, and the result is visualized under atomic force microscopy via the presence (success) or absence (failure) of biotin-streptavidin labels on the reporting DX tile. The factorization of semiprimes 6 and 15 is realized with this DOF-based demonstration. Given the potential of massively parallel processing ability of DNA, this strategy opens an avenue to solve complex mathematical puzzles like prime factoring with molecular computing. |
format | Online Article Text |
id | pubmed-10065441 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | American Association for the Advancement of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-100654412023-04-01 Prime factorization via localized tile assembly in a DNA origami framework Zhang, Yinan Yin, Xiaoyao Cui, Chengjun He, Kun Wang, Fei Chao, Jie Li, Tao Zuo, Xiaolei Li, Ailing Wang, Lihua Wang, Na Bo, Xiaochen Fan, Chunhai Sci Adv Physical and Materials Sciences Modern cybersecurity built on public-key cryptosystems like Rivest-Shamir-Adleman is compromised upon finding solutions to the prime factorization. Nevertheless, solving the prime factorization problem, given a large N, remains computationally challenging. Here, we design DNA origami frameworks (DOFs) to direct localized assembly of double-crossover (DX) tiles for solving prime factorization with a model consisting of the computing, decision-making, and reporting motifs. The model implementation is based on the sequential assembly of different DX tiles in the DOF cavity that carries overhangs encoding the prime and composite integers. The primes are multiplied and then verified with the composite, and the result is visualized under atomic force microscopy via the presence (success) or absence (failure) of biotin-streptavidin labels on the reporting DX tile. The factorization of semiprimes 6 and 15 is realized with this DOF-based demonstration. Given the potential of massively parallel processing ability of DNA, this strategy opens an avenue to solve complex mathematical puzzles like prime factoring with molecular computing. American Association for the Advancement of Science 2023-03-31 /pmc/articles/PMC10065441/ /pubmed/37000880 http://dx.doi.org/10.1126/sciadv.adf8263 Text en Copyright © 2023 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC). https://creativecommons.org/licenses/by-nc/4.0/This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license (https://creativecommons.org/licenses/by-nc/4.0/) , which permits use, distribution, and reproduction in any medium, so long as the resultant use is not for commercial advantage and provided the original work is properly cited. |
spellingShingle | Physical and Materials Sciences Zhang, Yinan Yin, Xiaoyao Cui, Chengjun He, Kun Wang, Fei Chao, Jie Li, Tao Zuo, Xiaolei Li, Ailing Wang, Lihua Wang, Na Bo, Xiaochen Fan, Chunhai Prime factorization via localized tile assembly in a DNA origami framework |
title | Prime factorization via localized tile assembly in a DNA origami framework |
title_full | Prime factorization via localized tile assembly in a DNA origami framework |
title_fullStr | Prime factorization via localized tile assembly in a DNA origami framework |
title_full_unstemmed | Prime factorization via localized tile assembly in a DNA origami framework |
title_short | Prime factorization via localized tile assembly in a DNA origami framework |
title_sort | prime factorization via localized tile assembly in a dna origami framework |
topic | Physical and Materials Sciences |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10065441/ https://www.ncbi.nlm.nih.gov/pubmed/37000880 http://dx.doi.org/10.1126/sciadv.adf8263 |
work_keys_str_mv | AT zhangyinan primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT yinxiaoyao primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT cuichengjun primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT hekun primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT wangfei primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT chaojie primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT litao primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT zuoxiaolei primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT liailing primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT wanglihua primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT wangna primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT boxiaochen primefactorizationvialocalizedtileassemblyinadnaorigamiframework AT fanchunhai primefactorizationvialocalizedtileassemblyinadnaorigamiframework |