CHAPTER 9
DNA COMPUTING FOR SUBGRAPH ISOMORPHISM PROBLEM AND RELATED PROBLEMS
9.1 INTRODUCTION
A DNA is a polymer made up of a sequence of subunits known as nucleotides. Distinct nucleotides are detected only with their bases, which come from adenine, guanine, cytosine, and thymine, abbreviated A, G, C, and T, respectively. A DNA strand is essentially a sequence of four types of nucleotides detected by one of four bases they contain [28]. DNA-based computing [24], or more generally molecular computing, is a computational paradigm that uses DNA molecules as information storage media. The techniques of molecular biology, such as polymerase chain reaction (PCR), gel electrophoresis, and enzymatic reactions, can be used as computational operators for copying, sorting, and splitting/concatenating the information in the DNA molecules, respectively [1].
Through the progress in molecular biology, it is now possible to produce about 1018 DNA strands contained in a test tube [28]. We can use each DNA strand to represent a piece of information. Primitive biological operations can be employed to operate 1018 pieces of information simultaneously. It has the same computing power as 1018 processors running in parallel. Accordingly, DNA-based computing can provide a huge parallelism for dealing with the intractable problems in the real world.
Feynman [14] first proposed DNA-based computation in 1961, but his idea was not implemented by experiment ...
