Computing with DNA by operating on plasmids

A new method of computing using DNA plasmids is introduced and the potentia l advantages are listed. The new method is illustrated by reporting a labor atory 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 met hod of molecular computing, was constructed. This computational plasmid con tains a specially inserted series of DNA sequence segments, each of which i s bordered by a characteristic pair of restriction enzyme sites. For the co mputation reported here, the DNA sequence segments of this series were used to represent the vertices of the graph being investigated. By applying a s cheme of enzymatic treatments to the computational plasmids, modified plasm ids 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.