Related Experiment Video
Updated: May 31, 2026

DNA-Tethered RNA Polymerase for Programmable In vitro Transcription and Molecular Computation
Published on: December 29, 2021
An unenumerative DNA computing model for vertex coloring problem
Jin Xu1, Xiaoli Qiang, Yan Yang
1Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing, China. jxu@pku.edu.cn
Abstract:
The solution space exponential explosion caused by the enumeration of the candidate solutions maybe is the biggest obstacle in DNA computing. In the paper, a new unenumerative DNA computing model for graph vertex coloring problem is presented based on two techniques: 1) ordering the vertex sequence for a given graph in such a way that any two consecutive labeled vertices i and i+1 should be adjacent in the graph as much as possible; 2) reducing the number of encodings representing colors according to the construture of the given graph. A graph with 12 vertices without triangles is solved and its initial solution space includes only 283 DNA strands, which is 0.0532 of 3(12) (the worst complexity).
Related Concept Videos
Vector Algebra: Graphical Method
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
Graphical Representation of Inequalities
Castigliano's Theorem: Problem Solving
Synthetic Disvision of Polynomials
DNA as a Genetic Template
DNA as a Genetic Template
