O'Reilly logo

Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications by Albert Y. Zomaya, Mourad Elloumi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

CHAPTER 9

DNA COMPUTING FOR SUBGRAPH ISOMORPHISM PROBLEM AND RELATED PROBLEMS

Sun-Yuan Hsieh, Chao-Wen Huang, and Hsin-Hung Chou

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required