• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

利用生物分子DNA计算机解决0/1背包问题。

Solving the 0/1 knapsack problem by a biomolecular DNA computer.

作者信息

Taghipour Hassan, Rezaei Mahdi, Esmaili Heydar Ali

机构信息

Department of Pathology, Tabriz University of Medical Sciences, Tabriz, Iran.

出版信息

Adv Bioinformatics. 2013;2013:341419. doi: 10.1155/2013/341419. Epub 2013 Feb 18.

DOI:10.1155/2013/341419
PMID:23509451
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC3588402/
Abstract

Solving some mathematical problems such as NP-complete problems by conventional silicon-based computers is problematic and takes so long time. DNA computing is an alternative method of computing which uses DNA molecules for computing purposes. DNA computers have massive degrees of parallel processing capability. The massive parallel processing characteristic of DNA computers is of particular interest in solving NP-complete and hard combinatorial problems. NP-complete problems such as knapsack problem and other hard combinatorial problems can be easily solved by DNA computers in a very short period of time comparing to conventional silicon-based computers. Sticker-based DNA computing is one of the methods of DNA computing. In this paper, the sticker based DNA computing was used for solving the 0/1 knapsack problem. At first, a biomolecular solution space was constructed by using appropriate DNA memory complexes. Then, by the application of a sticker-based parallel algorithm using biological operations, knapsack problem was resolved in polynomial time.

摘要

用传统的硅基计算机解决一些数学问题，如NP完全问题是有问题的，而且需要很长时间。DNA计算是一种替代的计算方法，它使用DNA分子进行计算。DNA计算机具有大规模的并行处理能力。DNA计算机的大规模并行处理特性在解决NP完全和硬组合问题方面特别受关注。与传统的硅基计算机相比，DNA计算机可以在很短的时间内轻松解决诸如背包问题等NP完全问题和其他硬组合问题。基于贴纸的DNA计算是DNA计算的方法之一。在本文中，基于贴纸的DNA计算被用于解决0/1背包问题。首先，通过使用适当的DNA记忆复合体构建一个生物分子解空间。然后，通过应用基于贴纸的并行算法并使用生物操作，背包问题在多项式时间内得到解决。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/fe718c4621b7/ABI2013-341419.alg.003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/1a910381dcc6/ABI2013-341419.001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/8d42b872c986/ABI2013-341419.002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/6b2aad1e52b3/ABI2013-341419.003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/3d33b875cdb1/ABI2013-341419.alg.001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/2860e1b69564/ABI2013-341419.alg.002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/fe718c4621b7/ABI2013-341419.alg.003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/1a910381dcc6/ABI2013-341419.001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/8d42b872c986/ABI2013-341419.002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/6b2aad1e52b3/ABI2013-341419.003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/3d33b875cdb1/ABI2013-341419.alg.001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/2860e1b69564/ABI2013-341419.alg.002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/2f1a/3588402/fe718c4621b7/ABI2013-341419.alg.003.jpg

相似文献

1
Solving the 0/1 knapsack problem by a biomolecular DNA computer.利用生物分子DNA计算机解决0/1背包问题。
Adv Bioinformatics. 2013;2013:341419. doi: 10.1155/2013/341419. Epub 2013 Feb 18.
2
Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing.基于DNA计算，每个NP完全或NP难问题的最优解是否由其特征决定。
Biosystems. 2005 Apr;80(1):71-82. doi: 10.1016/j.biosystems.2004.10.003. Epub 2004 Nov 26.
3
Molecular Sticker Model Stimulation on Silicon for a Maximum Clique Problem.用于最大团问题的硅基分子标签模型刺激
Int J Mol Sci. 2015 Jun 12;16(6):13474-89. doi: 10.3390/ijms160613474.
4
Parallelizing Assignment Problem with DNA Strands.利用DNA链并行化分配问题。
Iran J Biotechnol. 2020 Jan 1;18(1):e2547. doi: 10.30498/IJB.2020.195413.2547. eCollection 2020 Jan.
5
Solving the Family Traveling Salesperson Problem in the Adleman-Lipton Model Based on DNA Computing.基于 DNA 计算的 Adleman-Lipton 模型中的家庭旅行商问题求解。
IEEE Trans Nanobioscience. 2022 Jan;21(1):75-85. doi: 10.1109/TNB.2021.3109067. Epub 2021 Dec 30.
6
A new solution for maximal clique problem based sticker model.一种基于贴纸模型的最大团问题新解决方案。
Biosystems. 2009 Feb;95(2):145-9. doi: 10.1016/j.biosystems.2008.09.007. Epub 2008 Oct 17.
7
Parallel computation with molecular-motor-propelled agents in nanofabricated networks.在纳米制造网络中利用分子马达驱动的粒子进行并行计算。
Proc Natl Acad Sci U S A. 2016 Mar 8;113(10):2591-6. doi: 10.1073/pnas.1510825113. Epub 2016 Feb 22.
8
DNA computing of solutions to knapsack problems.
Biosystems. 2007 Mar;88(1-2):156-62. doi: 10.1016/j.biosystems.2006.06.001. Epub 2006 Jun 10.
9
A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing.一种基于DNA分子计算解决不平衡分配问题的并行生物优化算法。
Int J Mol Sci. 2015 Oct 23;16(10):25338-52. doi: 10.3390/ijms161025338.
10
A parallel algorithm for solving the n-queens problem based on inspired computational model.一种基于启发式计算模型求解n皇后问题的并行算法。
Biosystems. 2015 May;131:22-9. doi: 10.1016/j.biosystems.2015.03.004. Epub 2015 Mar 27.

引用本文的文献

1
Model Checking Temporal Logic Formulas Using Sticker Automata.使用贴纸自动机对时态逻辑公式进行模型检测。
Biomed Res Int. 2017;2017:7941845. doi: 10.1155/2017/7941845. Epub 2017 Sep 28.

本文引用的文献

1
Design and self-assembly of two-dimensional DNA crystals.二维DNA晶体的设计与自组装。
Nature. 1998 Aug 6;394(6693):539-44. doi: 10.1038/28998.
2
DNA solution of the maximal clique problem.最大团问题的DNA解决方案。
Science. 1997 Oct 17;278(5337):446-9. doi: 10.1126/science.278.5337.446.
3
Molecular computation of solutions to combinatorial problems.组合问题解决方案的分子计算。
Science. 1994 Nov 11;266(5187):1021-4. doi: 10.1126/science.7973651.
4
DNA solution of hard computational problems.难以计算问题的DNA解决方案。
Science. 1995 Apr 28;268(5210):542-5. doi: 10.1126/science.7725098.