L. (2019). Sci. Rep. 9 (Art. No.: 4998).98 98 Goldman, N., Bertone, P., Chen, S. et al. (2013). Nature 494: 77–80.
99 99 Anavy, L., Vaknin, I., Atar, O. et al. (2019). Nat. Biotechnol. 37: 1229–1236.
100 100 Organick, L., Ang, S.D., Chen, Y.‐J. et al. (2018). Nat. Biotechnol. 36: 242–248.
101 101 Church, G.M., Gao, Y., and Kosuri, S. (2012). Science 337: 1628.
102 102 Shipman, S.L., Nivala, J., Macklis, J.D., and Church, G.M. (2017). Nature 547: 345–349.
103 103 Li, S., Jiang, Q., Liu, S. et al. (2018). Nat. Biotechnol. 36: 258–264.
104 104 Ma, W., Zhan, Y., Zhang, Y. et al. (2019). Nano Lett. 19: 4505–4517.
105 105 De Silva, P.Y. and Ganegoda, G.U. (2016). BioMed Res. Int. 2016 (Art. No.: 8072463).
106 106 Tagore, S., Bhattacharya, S., Islam, M.A., and Islam, M.L. (2010). J. Proteomics Bioinform. 3: 234–243.
107 107 Currin, A., Korovin, K., Ababi, M. et al. (2017). J. R. Soc. Interface 14 (Art. No.: 20160990).
2 DNA Computing: Methodologies and Challenges
Deepak Sharma and Manojkumar Ramteke
Department of Chemical Engineering, Indian Institute of Technology Delhi, New Delhi, Hauz Khas, New Delhi, 110016, India
2.1 Introduction to DNA Computing Methodologies
Humans are looking for new approaches to computing since the starting of civilization. Over the years, researchers have invented many systems for computation, from “counting with abacus” to “complex computing by using modern‐day computers.” According to Moore's observation [1], the number of transistors on a silicon chip is found to be doubling in every 18–24 months, which results in the development of faster computing devices. However, in the coming decades, producing such faster computing devices will be more challenging as the size of the transistor is already approaching to a molecular level. Moreover, engineering such silicon chips is gradually becoming more complex and less cost effective. This compelled the researchers to look for alternative computing devices and methodologies. Biomolecular computing is one such excellent alternative to traditional silicon‐based computing methods.
Biomolecular computing is illustrated for the first time by Adleman in 1994 [2] to solve the Hamiltonian path problem (HPP) using deoxyribonucleic acid (DNA). In such DNA‐based computing (referred to as DNA computing), enzymatic reactions and manipulations such as addition, amplification, and cutting of the DNA are used for performing the computing. Subsequently, DNA computing is used by several researchers [3–8] to solve a variety of combinatorial problems. These studies have exploited high parallelism of DNA reactions over sequential operations occurring in silicon‐based computers to solve the computationally intractable problems. Such parallel processing in DNA computer builds the confidence for solving the problems that are presently not solvable with silicon‐based computers. Moreover, DNA became an effective and efficient material for faster computation, storage, and information processing owing to the significant advancements in biomolecular techniques such as gel electrophoresis, polymerase chain reaction (PCR), affinity separation, restriction enzyme digestion, etc. [9,10].
Despite initial success, the increase in problem size leads to a significant bottleneck in scaling the existing DNA computing procedures for large size problem formulations. This is primarily because the amount of DNA required increases exponentially with size even though the number of biochemical steps required increases with a polynomial function. Further, there is a significant compounding of experimental errors involved, which makes these procedures redundant for solving the bigger size formulations. Also, the real‐life problems often have continuous search spaces and multiple optimal solutions, whereas the existing DNA computing procedures are mostly developed for discrete search spaces involving a single optimal solution.
2.2 Key Developments in DNA Computing
In 1994, Adleman [2] used the DNA for computation in the first‐ever molecular experiment performed to solve the HPP. Molecular biology experiments were performed to address the instance graph having seven vertices and fourteen edges. A year later, Lipton [3] presented a new model for solving another NP‐complete (nondeterministic polynomial time complete) problem known as satisfiability (SAT) problem using a DNA computer. SAT problem is also solved by Smith et al. [4] and Liu et al. [6] with new surface‐based DNA computing models.
Along with these models, other researchers [7,11,12] also solved NP‐complete problems with a different approach. Sakamoto et al. [5] used DNA hairpin formation to solve the SAT problem. Chao et al. [13] developed a single‐molecule “DNA navigator” to solve a maze. These models of DNA computing are discussed in the next section.
2.2.1 Adleman Model
Adleman's DNA computer [2] solved a small instance of a hard computational problem, the HPP. For a given graph, this problem asks for a path with a fixed start and end vertices that visits every vertex exactly once (Figure 2.1a). In his representation, each vertex is encoded using 20 bp nucleotides. Edges are encoded as 20‐mers, with the first 10 nucleotides complementary to the last 10 nucleotides of the start vertex and the last 10 complementary to the first 10 of the end vertex (Figure 2.1b). By mixing and ligating oligonucleotides corresponding to vertices and edges, concatenates are formed that represent paths through the network (Figure 2.1c). A path through the graph involves all vertices such that each vertex represented only once is a correct solution to the problem and is referred to as the Hamiltonian path. However, the random nature of ligations leads to the formation of other incorrect paths that do not meet the required condition of the Hamiltonian path. Therefore, several biochemical steps are required (Figure 2.1d,e) to extract the correct path from the set of all paths generated in the ligation process. First, such biochemical step is the PCR, which amplifies only those paths that start and end with right vertices. In the second step, only the paths of correct length are extracted using gel electrophoresis. Finally, the presence of every vertex sequence is confirmed using affinity separation. If any DNA remains after the last separation, this must correspond to a Hamiltonian path.
Figure 2.1 Adleman's DNA computing procedure [2]. For (a) given super graph, vertices and edges are encoded using the (b) encoding strategy, and (c) mixed to generate all possible paths through the graph using ligation. The correct length path is selected using (d) gel electrophoresis. All correct length paths are further screened to confirm the presence of sequence corresponding to each vertex one by one starting from first to the last vertex using (e) affinity chromatography.
Consider a supergraph shown in Figure 2.1a involving five vertices. The objective is to obtain a path that starts from vertex 1 and ends at vertex 5 such that each vertex is represented only once. Initially, the DNA sequences of 20 bp are designed for each vertex and edge such that these should lead to linear DNA. For starting and ending edge, the complementary sequence of all 20 bp of starting and ending vertex
