Classical models of computing and information processing are based on operations on sequences of symbols. However, natural processes in which three dimensional molecular structures can emerge imply 'structural' computation in nature. We demonstrate a molecular solution to a graph-theoretic problem by construction of the actual graph as a solution to the problem. A graph is a construct embedded in three dimensional space consisting of vertices connected by edges. The question of whether the vertices of a given graph can be rendered using three colors such that connected edges are colored distinctly belongs to class of computational problems termed `NP hard'.

Previously, DNA computation has addressed NP hard problems through binary encodings representing graphs or paths in the graph and by performing parallel molecular operations, followed by a sequence of selection methods to extract the answer. The number of extraction protocols in all these proposals increases with increase of the number of vertices or edges of the graph. The solution of the three-colorability problem for a graph of 6 vertices and 9 edges reported here uses a constant number of steps, which does not increase with the size of the graph. The graph is shown in a DNA representation on the left of the figure below. The structure corresponding to the solution of the problem was identified through its resistance to restriction endonuclease cleavage. A ligated molecule (right below) that traverses each edge of the graph at least once demonstrated the formation of the structure, was identified by its length, and was confirmed through sequencing. Although the graph itself is planar, the necessity of such single strand required that the graph is placed on a surface of genus 2 (e.g., an inflated figure-8 shape).


This research supported by NIGMS, NSF, ARO and the W.M. Keck Foundation.