Ternary representation of N (N = 1 or 2)-input and 1-output algorithmic self-assembly demonstrated by DNA.

ABSTRACT

Deoxyribonucleic acid (DNA) is effective for molecular computation because of its high energy efficiency, high information density, and parallel-computing capability. Although logic implementation using DNA molecules is well established in binary systems (base value of 2) via decoration of hairpin structures on DNA duplexes, systems with base values of >2 (e.g. 3, corresponding to a ternary system) are rarely discussed owing to the complexity of the design and the experimental difficulties with DNA. In this study, DNA rule tiles that participate to form algorithmic DNA crystals exhibiting the ternary representation of an N (N = 1 or 2)-input and 1-output algorithmic assembly are conceived. The number of possible algorithmic patterns is [Formula see text] in the ternary N-input and 1-output logic gate. Thus, the number of possible rules is 27 (=33) for a 1-input and 1-output algorithmic logic gate and 19 638 (=39) for a 2-input and 1-output algorithmic logic gate. Ternary bit information (i.e. 0-, 1-, and 2-bit) is encoded on rule tiles without hairpins and with short and long hairpins. We construct converged, line-like, alternating, and commutative patterns by implementing specific rules (TR00, TR05, TR07, and TR15, respectively) for the 1-input and 1-output gate and an ascending line-like pattern (with the rule of TR3785) for the 2-input and 1-output gate. Specific patterns generated on ternary-representing rule-embedded algorithmic DNA crystals are visualized via atomic force microscopy, and the errors during the growth of the crystals are analyzed (average error rates obtained for all experimental data are <4%). Our method can easily be extended to a system having base values of >3.