Computing with DNA by operating on plasmids

Head, T.; Rozenberg, G.; Bladergroen, R.S; Breek, C.K.D; Lommerse, P.H.M; Spaink, H.P

doi:doi:10.1016/S0303-2647(00)00091-5

A new method of computing using DNA plasmids is introduced and the potential advantages are listed. The new method is illustrated by reporting a laboratory computation of an instance of the NP-complete algorithmic problem of computing the cardinal number of a maximal independent subset of the vertex set of a graph. A circular DNA plasmid, specifically designed for this method of molecular computing, was constructed. This computational plasmid contains a specially inserted series of DNA sequence segments, each of which is bordered by a characteristic pair of restriction enzyme sites. For the computation reported here, the DNA sequence segments of this series were used to represent the vertices of the graph being investigated. By applying a scheme of enzymatic treatments to the computational plasmids, modified plasmids were generated from which the solution of the computational problem was selected. This new method of computing is applicable to a wide variety of algorithmic problems....Show moreA new method of computing using DNA plasmids is introduced and the potential advantages are listed. The new method is illustrated by reporting a laboratory computation of an instance of the NP-complete algorithmic problem of computing the cardinal number of a maximal independent subset of the vertex set of a graph. A circular DNA plasmid, specifically designed for this method of molecular computing, was constructed. This computational plasmid contains a specially inserted series of DNA sequence segments, each of which is bordered by a characteristic pair of restriction enzyme sites. For the computation reported here, the DNA sequence segments of this series were used to represent the vertices of the graph being investigated. By applying a scheme of enzymatic treatments to the computational plasmids, modified plasmids were generated from which the solution of the computational problem was selected. This new method of computing is applicable to a wide variety of algorithmic problems. Further computations in this style are in progress. (C) 2000 Elsevier Science Ireland Ltd. All rights reserved.Show less

Leiden University Scholarly Publications

View statistics

Documents

In Collections

Computing with DNA by operating on plasmids