相关实验视频
Updated: Jul 8, 2026

16:24
Analyzing and Building Nucleic Acid Structures with 3DNA
Published on: April 26, 2013
在DNA计算机上解决20个变量的3-SAT问题
Ravinderjit S Braich1, Nickolas Chelyapov, Cliff Johnson
1University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.
概括
研究人员使用DNA计算机解决了一个复杂的20个变量问题,探索了100多万种可能性. 这表明,在用生物手段解决大型计算问题方面取得了重大进展.
科学领域:
- 生物计算是一种生物计算.
- 计算复杂性理论 计算复杂性理论
- 分子计算分子计算
背景情况:
- 三满足性 (3-SAT) 问题是计算机科学中一个基本的NP-完整问题.
- 对于传统的电子计算机来说,解决大型的3-SAT实例在计算上具有挑战性.
研究的目的:
- 为了证明一个简单的DNA计算机在解决复杂的计算问题上的能力.
- 研究使用生物分子进行大规模计算的可行性.
主要方法:
- 用基于DNA的计算方法编码和解决了3-SAT问题的20个变量实例.
- DNA计算机对超过100万个 (2^20) 的可能性进行了详尽的搜索,以找到唯一的解决方案.
主要成果:
- DNA计算机成功地确定了对20个变量3-SAT问题的独特解决方案.
- 这是迄今为止使用非电子,生物方法解决的最大的计算问题之一.
结论:
- DNA计算为解决计算密集的问题提供了一个可行的替代方案.
- 这种解决方案的规模表明,DNA计算机在解决超出人类或传统计算限制的问题方面有潜力.
相关概念视频
DNA as a Genetic Template
Two structural features of the DNA molecule provide a basis for the mechanisms of heredity: the four nucleotide bases and its double-stranded nature. The Watson-Crick model of double-helical DNA structure, proposed in 1952, drew heavily upon the X-ray crystallography work of researchers Rosalind Franklin and Maurice Wilkins. Watson, Crick, and Wilkins jointly received the Nobel Prize in Physiology or Medicine for their work in 1962. Franklin was, controversially, excluded from the prize for...
DNA Microarrays
Microarrays are high-throughput and relatively inexpensive assays that can be automated to analyze large quantities of data at a time. They are used in genome-wide studies to compare gene or protein expression under two varied conditions, such as healthy and diseased states. Microarrays consist of glass or silica slides on which probe molecules are covalently attached through surface functionalization. Most commonly, the slides are prepared through the chemisorption of silanes to silica...
DNA as a Genetic Template
Two structural features of the DNA molecule provide a basis for the mechanisms of heredity: the four nucleotide bases and its double-stranded nature. The Watson-Crick model of double-helical DNA structure, proposed in 1952, drew heavily upon the X-ray crystallography work of researchers Rosalind Franklin and Maurice Wilkins. Watson, Crick, and Wilkins jointly received the Nobel Prize in Physiology or Medicine for their work in 1962. Franklin was, controversially, excluded from the prize for...
Statically Indeterminate Problem Solving
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
Castigliano's Theorem: Problem Solving
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam is...
Functions of Three or More Variables
A function of three variables assigns a single real number to each point in three-dimensional space. Every point is identified by its Cartesian coordinates, x, y, and z, and the function maps this ordered triple to a scalar value. Such functions are commonly used to describe physical quantities that vary throughout space.A representative example is the electric potential generated by a point charge. In this case, the potential at a given location depends only on the distance from the charge. If...

