A New Readout Approach in DNA Computing based on Real-Time

A New Readout Approach in DNA Computing basedon Real-Time PCR with TaqMan Probes Zuwairie Ibrahim1, Yusei Tsuboi2, John A. Rose3, Osamu Ono4, andMarzuki Khalid11Faculty of Electrical Engineering, Universiti Teknologi Malaysia, 81310 UTM Skudai, Johor Darul Takzim, Malaysiazuwairie@fke.utm.my, marzuki@utmkl.utm.my2Bio-Mimetic Control Research Center, RIKEN, 2271-130 Anagahora, Shimoshidami, Moriyama-ku, Nagoya, 463-0003, JAPANtsuboi@bmc.riken.jp3Institute of Information Communication Technology, Ritsumeikan Asia Pacific University, 1-1 Jumonjibaru, Beppu-shi, Oita 874-8577 Japanjarose@apu.ac.jp4Institute of Applied DNA Computing, Meiji University, 1-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa-ken, 214-8571 Japanono@isc.meiji.ac.jpAbstract. A new readout approach for the Hamiltonian Path Problem (HPP) in DNA computing based on the real-time polymerase chain re-action (PCR) is investigated. Several types of fluorescent probes and detection mechanisms are currently employed in real-time PCR, includ-ing SYBR Green, molecular beacons, and hybridization probes. In this study, real-time amplification performed using the TaqMan probes is adopted, as the TaqMan detection mechanism can be exploited for the design and development of the proposed readout approach. Double-stranded DNA molecules of length 120 base-pairs are selected as the input molecules, which represent the solving path for an HPP instance.These input molecules are prepared via the self-assembly of 20-mer and 30-mer single-stranded DNAs, by parallel overlap assembly. The proposed readout approach consists of two steps: real-time amplifica-tion in vitro using TaqMan-based real-time PCR, followed by informa-tion processing in silico to assess the results of real-time amplification, which in turn, enables extraction of the Hamiltonian path. The per-formance of the proposed approach is compared with that of conven-tional graduated PCR. Experimental results establish the superior per-formance of the proposed approach, relative to graduated PCR, in terms of implementation time.1 IntroductionSince the discovery of the polymerase chain reaction (PCR) [1], nu-merous applications have been explored, primarily in the life sciences and medicine, and importantly, in DNA computing as well. The subse-quent innovation of real-time PCR has rapidly gained popularity and plays a crucial role in molecular medicine and clinical diagnostics [2]. All real-time amplification instruments require a fluorescence reporter molecule for detection and quantitation, whose signal increase is propor-tional to the amount of amplified product. Although a number of reporter molecules currently exist, it has been found that the mechanism of TaqMan hydrolysis probe is very suitable for the extraction of molecular information in DNA computing, and is thus selected for the current study.A TaqMan DNA probe is a modified, non-extendable dual-labeled oligonucleotides. The 5’ and 3’ ends of the oligonucleotide are termi-nated with attached reporter, such as TAMRA, and quencher fluoropho-res dyes, such as FAM, respectively, as shown in Fig. 1 [3]. Upon laser excitation at 488 nm, the TAMRA reporter dye, in isolation emits fluo-rescence at 518 nm, respectively. Given proximity of the 3’ quencher, however, based on the principle of fluorescence resonance energy trans-fer (FRET), the excitation energy is not emitted by the 5’ reporter, but rather is transferred along the sugar-phosphate-backbone to the FAM quencher. As the FAM quencher fluorophores’ dyes emit this absorbed energy at much longer wavelengths (i.e., lower energy) than the TAMRA reporter fluorophores, the resulting fluorescence cannot be detected by real-time PCR instruments [4].Fig. 1: Illustration of the structure of a TaqMan DNA probe. Here, R and Q denote the reporter and quencher fluorophores, respectively.The combination of dual-labeled TaqMan DNA probes with forward and reverse primers is a must for a successful real-time PCR. As PCR is a repeated cycle of three steps (denaturation, annealing, and polymeriza-tion), a TaqMan DNA probe will anneal to a site within the DNA tem-plate in between the forward and reverse primers during the annealingstep, if a subsequence of the DNA template is complementary to the se-quence of the DNA probe. During polymerization, Thermus aquaticus (Taq) DNA polymerase will extend the primers in a 5’ to 3’ direction. At the same time, the Taq polymerase also acts as a “scissor” to degrade the probe via cleavage, thus separating the reporter from the quencher, as shown in Fig. 2 [5], where R and Q denote reporter dye and quencher dye, respectively. This separation subsequently allows the reporter to emit its fluorescence [6]. This process occurs in every PCR cycle and does not interfere with the exponential accumulation of PCR product. As a result of PCR, the amount of DNA template increases exponentially, which is accompanied by a proportionate increase in the overall fluores-cence intensity emitted by the reporter group of the excised TaqMan probes. Hence, the intensity of the measured fluorescence at the end of each PCR polymerization is correlated to the total amount of PCR prod-uct, which can then be detected, using a real-time PCR instrument for visualization.Fig. 2: Degradation of a TaqMan probe, via cleavage by DNA poly-merase.In this paper, we propose a new readout method tailored specifically to the HPP in DNA computting, which employs a hybrid in vitro-in silico approach. In the in vitro phase, O(|V|2) TaqMan-based real-time PCR reactions are performed in parallel, to investigate the ordering of pairs of nodes in the Hamiltonian path of a |V|-node instance graph, in terms of relative distance from the DNA sequence encoding the known start node. The resulting relative orderings are then processed in silico, which effi-ciently returns the complete Hamiltonian path. To the best of our knowl-edge, the proposed approach is the first experimentally validated optical method specifically designed for the quick readout of HPP instances, in DNA computing. Previously, graduated PCR, which was originally dem-onstrated by Adleman [7], was employed to perform such operations. While a DNA chip based methodology, which makes use of biochip hy-bridization for the same purpose has been proposed [8-10], this method is more costly, and has yet to be experimentally implemented.2 Notation and Basic PrincipleFirst of all, v1(a)v2(b)v3(c)v4(d) denotes a double-stranded DNA (dsDNA) which contains the base-pairs subsequences, v1, v2, v3, and v4, respec-tively. Here, the subscripts in parenthesis (a, b, c, and d) indicate the length of each respective base-pair subsequence. For instance, v1(20) indi-cates that the length of the double-stranded subsequence, v1 is 20 base-pairs (bp). When convenient, a dsDNA may also be represented without indicating segment lengths (e.g., v1v2v3v4).A reaction denoted by TaqMan(v0,v k,v l) indicates that real-time PCR is performed using forward primer v0, reverse primerv, and TaqManlprobe v k. Based on the proposed approach, there are two possible reac-tion conditions regarding the relative locations of the TaqMan probe and reverse primer. In particular, the first condition occurs when the TaqMan probe specifically hybridizes to the template, between the forward and reverse primers, while the second occurs when the reverse primer hybrid-izes between the forward primer and the TaqMan probe. As shown in Fig. 3, these two conditions would result in different amplification patterns during real-time PCR, given the same DNA template (i.e., assuming that they occurred separately, in two different PCR reactions). The higher fluorescent output of the first condition is a typical amplification plot for real-time PCR. In contrast, the relatively lower fluorescent output of the second condition, which reflects the cleavage of a lower number of TaqMan probes via DNA polymerase due to the ‘unfavourable’ hybridi-zation position of the reverse primer, is due to linear rather than expo-nential amplification of the template. Thus, TaqMan(v0,v k,v l) = YES if an amplification plot similar to the first condition is observed, while TaqMan(v0,v k,v l) = NO if an amplification plot similar to the second con-dition is observed.3 The Proposed Readout ApproachConsider an input as a directed weighted graph, G=(V,E), where V={V0, V1, V2, V3, V4, V5}, so that, |V|=6. Let the output of an in vitro computation of an HPP instance of the input graph be represented by a 120-bp dsDNA v0(20)v2(20)v4(20)v1(20)v3(20)v5(20), where the Hamiltonian pathV0→V2→V4→V1→V3→V5, begins at node V0, ends at node V5, and con-tains intermediate nodes V2, V4, V1, and V3, respectively. Note that in practice, only the identities of the starting and ending nodes, and the presence of all intermediate nodes will be known in advance to character-ize a solving path. The specific order of the intermediate nodes within such a path is unknown.Fig. 3: An example of amplification plots corresponding to TaqMan(v0,v k,v l) = YES (first condition) and TaqMan(v0,v k,v l) = NO (second condition).The first part of the proposed approach, which is performed in vitro, consists of [(|V|-2)2-(|V|-2)]/2 real-time PCR reactions, each denoted by TaqMan(v0,v k,v l) for all k and l, such that 0 < k < |V|-2, 1 < l <|V|-1 , and k < l. For this example instance, so that the DNA template is dsDNAs v0v2v4v1v3v5, these 6 reactions, along with the expected output in terms of “YES” or “NO” are as follows:(1) TaqMan(v0,v1,v2) = NO(2) TaqMan(v0,v1,v3) = YES(3) TaqMan(v0,v1,v4) = NO(4) TaqMan(v0,v2,v3) = YES(5) TaqMan(v0,v2,v4) = YES(6) TaqMan(v0,v3,v4) = NONote that the overall process consists of a set of parallel real-time PCR reactions, and thus requires O(1) laboratory steps for in vitro ampli-fication. The accompanying SPACE complexity, in terms of the required number of capillary tubes is O(|V|2). Clearly, only one forward primer is required for all real-time PCR reactions, while the number of reverse primers and TaqMan probes required with respect to the size of input graph are each |V|-3.After all real-time PCR reactions are completed, the in vitro output is subjected to a pseudo-code for in silico information processing, produc-ing the satisfying Hamiltonian path of the HPP instance in O(n2) TIME (here, n denotes vertex number) as follows:Input: A[0…|V|-1]=2 // A[2, 2, 2, 2, 2, 2] A[0]=1, A[|V|-1]=|V| // A[1, 2, 2, 2, 2, 6] for k=1 to |V|-3for l=2 to |V|-2l>kwhileif TaqMan(v0,v k,v l) = YESA[l] = A[l]+1A[k] = A[k]+1elseendifendwhileendforendforIt is assumed that a Hamiltonian path is stored in silico, in an array, let say, A[0…|V|-1], for storage, information retrieval, and processing, such that A[i]∈A returns the exact location of a node, V i∈V, in the Hamiltonian path. Based on the proposed pseudo-code, and example instance, the input array A is first initialized to A = {1, 2, 2, 2, 2, 6}. During the loop operations of the pseudo-code, the elements A[0]∈A and A[|V|-1]∈A, are not involved, as those two elements may conven-iently be initialized to the correct values, as the distinguished starting and ending nodes of the Hamiltonian path are known in advance. The loop operation is thus strictly necessary only for the remaining elements A[1,2,3…, |V|-2]∈A. Again, for the example instance, the output of the in silico information processing is A = {1, 4, 2, 5, 3, 6}, representing the Hamiltonian path, V0→V2→V4→V1→V3→V5. For instance, in this case, it is indicated that V3 is the fifth node in the Hamiltonian path, since A[3] = 5, and so on.4 Experiments4.1 Preparation of Input MoleculesA pool of 120-bp input molecules v0(20)v2(20)v4(20)v1(20)v3(20)v5(20) is pre-pared, via standard protocol of parallel overlap assembly (POA) of sin-gle-stranded DNA strands (ssDNAs). For this purpose, 11 ssDNAs are required, including additional ssDNAs, which act as link sequences for self-assembly. These strands are listed in Table 1. After completion, am-plification via PCR was performed using the same protocol as POA. The forward primers and reverse primers used for the PCR reaction were 5’-CCTTAGTAGTCATCCAGACC-3’ and 5’-CCACTGGTTCTGCATGTAAC-3’, respectively.The PCR product was subjected to gel electrophoresis and the resul-tant gel image was captured, as shown in Fig. 4. The 120-bp band in lane 2 shows that the input molecules have been successfully generated. Af-terwards, the DNA of interest is extracted. The final solution for real-time PCR was prepared via dilution of the extracted solution, by adding ddH2O (Maxim Biotech, Japan) into 100 µl.4.2 Real-time PCR ExperimentsThe real-time PCR reaction involves primers (Proligo, Japan), TaqMan probes (Proligo, Japan), and LightCycler TaqMan Master (Roche Applied Science, Germany). The sequences for forward primers, reverse primers, and TaqMan probes are listed in Tables 2 and Table 3. In Table 2, the GC contents (GC%) and melting temperature (T m), are also shown. The LightCycler TaqMan Master essentially contains 1 vial of enzyme, 3 vials of master mix, and 2 vials of PCR grade/water. The master mix contains FastStart Taq DNA polymerase, reaction buffer, MgCl2, and dNTP mix (with dUTP instead of dTTP). PCR grade/water is important to adjust the final reaction volume for real-time PCR. Subse-quently, a reaction mix is prepared by pipetting 10 µl of enzyme into the master mix.For real-time PCR, as recommended by the manufacturer, the final concentration of primers should be between 0.1-1 µM, whereas the final concentration of the DNA probes should be between 0.05-0.1 µM. The final concentration for primers is set to 0.5 µM in this study, and for theTaqMan probes, the maximum final concentration, which is 0.1 µM, ischosen and prepared.Table 1: The required single-stranded DNAs for the generation of input molecules.Name DNA sequences (5’-3’) Lengthv0CCTTAGTAGTCATCCAGACC 20 v2CGCGCACCTTCTTAATCTAC 20 v4ATGCGCCAGCTTCTAACTAC 20 v1TGGACAACCGCAGTTACTAC 20 v3TCCACGCTGCACTGTAATAC 20 v5GTTACATGCAGAACCAGTGG 20 v2v4GCAGCGTGGAGTAGTTAGAA 20 v4v1AAGGTGCGCGGTATTACAGT 20 v1v3CGGTTGTCCAGTAGATTAAG 20 v0v2GCTGGCGCATGGTCTGGATGACTACTAAGG 30v3v5CCACTGGTTCTGCATGTAACGTAGTAACTG 30Fig. 4: Gel image for the preparation of input molecules. Lane M denotesa 20-bp molecular marker, lane 1 is the product of initial pool generationbased on parallel overlap assembly, and lane 2 is the amplified PCRproduct.Table 2: Sequences for forward primer (FP) and reverse primers (RPs)Table 3: Sequences for TaqMan dual-labeled probes.TaqMan probe SequencesTaqw R-5’-CGCGCACCTTCTTAATCTAC-3’-Q Taqx R-5’-ATGCGCCAGCTTCTAACTAC-3’-Q Taqy R-5’-TGGACAACCGCAGTTACTAC-3’-Q Taqz R-5’-TCCACGCTGCACTGTAATAC-3’-Q In this study, real-time PCR was performed on a LightCycler 2.0 In-strument (Roche Applied Science, Germany) where amplification is car-ried out in a 20 µl LightCycler capillary tube (Roche Applied Science, Germany). Two solutions were prepared for each reaction: (1) 3 µl of a10x primer/probe solution (5 µM of primers and 1 µM of probes), pre-pared by mixing 0.75 µl of 20 µM forward primer solution, 0.75 µl of a20 µM reverse primer solution, and 1.5 µl of a 2 µM probe solution; and,(2) 15 µl of PCR mix, containing 4 µl of reaction mix, 9 µl PCRgrade/water, and 2 µl of the previous 10x primer/probe solution. Notethat even though 3 µl of 10x primer/probe solution was prepared, only 2µl of that solution was used for the preparation of PCR mix. 15 µl ofPCR mix was then injected via pipette into a capillary tube. Afterwards,5 µl of the input molecule solution was injected into the same capillarytube. The capillary tube was then sealed with a stopper, and placed in an adapter. The adapter containing the capillary was placed into a microcen-trifuge, and the centrifugation was performed at 3000 rpm.Seven separate real-time PCR reactions, including a negative controlwere performed, in order to implement the first stage of the proposedHPP readout. Note that the seventh reaction is for a negative control,which contains PCR grade/water instead of input molecules. The ampli-fication consists of 45 cycles of denaturation, annealing, and extension,performed at 95ºC, 48ºC, and 72ºC, respectively. The annealing tempera-ture is primer-dependent, and should be selected at 5ºC below the calcu-lated primer melting temperatures. In the current study, the lowest primer melting temperature was estimated at 53.5ºC. Accordingly, an annealing temperature of 48ºC was selected. The resulting real-time PCR amplifi-cation plots are illustrated in Fig. 5.Fig. 5: Output of real-time PCR and grouping of output signals into three regions: amplification region (YES), non-amplification region (NO), and negative control region. The amplification phase, static phase, and error phase are also shown. The numbering 1 to 6 indicate the [(|V|-2)2-(|V|-2)]/2 reactions TaqMan(v0,v k,v l) of input instance, while the seventh reac-tion is for negative control.5 DiscussionsAs discussed in Section 2, in the in vitro stage of the proposed ap-proach, each real-time PCR reaction is mapped to a binary output (i.e., either “YES” or “NO”), based on the occurrence or absence of the typical exponential amplification. More specifically, a combination of forward primer, reverse primer, and TaqMan probe, operating on an input tem-plate molecule produces an output signal, which may then be recognized as amplification plot corresponding to either the first or second condition, respectively. Based on the output plot of Fig. 5, the output of the nega-tive control (seventh reaction) can be distinguished easily. As shown in Fig. 5, the real-time PCR output signals can be grouped into three re-gions: an amplification region, a non-amplification region, and a nega-tive control region. Given the existence of this grouping, the subsequent in silico information processing is able to determine the Hamiltonian path of the input instance (e.g., V0→V2→V4→V1→V3→V5, for the exam-ple instance).In this study, each real-time PCR reaction consists of 45 cycles, and require about 1 hour and 10 minutes. The resulting set of real-time PCR output signals may collectively be subdivided into three phases: an am-plification phase, a static phase, and an error phase. Here, the amplifica-tion phase is defined as the initial time period, during which amplifica-tion-like signals are observed. The static phase, on the other hand, is defined as the subsequent time period, in which nearly all of the output signals exhibit only slight increases in fluorescence, with an increasing number of cycles. Lastly, the error phase is defined as the time period in which the negative control signal behaves as an amplification-like signal. Consideration of this effect is important, as shown by the current exam-ple instance. In particular, during the error phase (only), the output signal of reaction 3, which is properly clustered into the non-amplification re-gion, enters the amplification region erroneously. In practice, real-time PCR may be halted, if desired, after the 11th cycle (i.e., after 25 min), as the output signals may already be easily distinguished and grouped into the above defined regions, and a set of binary output (i.e., either “YES” or “NO”) data may be obtained, as the static and error phases are not important for this purpose. Note that at present, however, this grouping itself is not computerized.If the ability to extract molecular information is graded based on time factors, the proposed TaqMan-based real-time PCR approach is superior compared to conventional graduated PCR. In particular, for the case of graduated PCR, following DNA extraction, roughly 30 min are normally required to perform each PCR reaction, 30 min for gel electro-phoresis, and another 30 min to stain the gel with SYBR Gold solution. Thus, graduated PCR is proven to be a very time consuming method. As discussed previously, it required about 25 min for the real-time PCR and the in silico information processing can be done in less than 1 min. Hence, it would appear that the proposed approach is superior, in terms of implementation time compared to conventional graduated PCR.6 ConclusionsThis research offers an improved and effective readout approach for DNA computing, which consists of in vitro real-time amplification and in silico information processing, respectively. It is clear that the use of real-time PCR, as proposed in this paper differs from the conventional appli-cation of real-time PCR in the life sciences and medicine. Note that the current approach is originally developed for HPP readout, but the varia-tions of this approach could also be applied to other computation models of DNA computing, in which automated and rapid visualization of the computational output are required.References1. K. Mullis et al., Specific enzymatic amplification of DNA in vitro: The polymerasechain reaction, Cold Spring Harbor Symposium on Quantitative Biology, Vol. 51, 1986, pp. 263-273.2. L. Overbergh et al., The use of real-time reverse transcriptase PCR for the quantifi-cation of cytokine gene expression, Journal of Biomolecular Techniques, Vol. 14, 2003, pp. 33-43.3. N.J. Walker, A technique whose time has come, Science, Vol. 296, 2002, pp. 557-559.4. B. Bubner and I.T. Baldwin, Use of real-time PCR for determining copy numberand zygosity in transgenic plants, Plant Cell Reports, Vol. 23, 2004, pp. 263-271. 5. C.A. Heid et al., Real-time quantitative PCR, Genome Research, Vol. 6, 1996, pp.986-994.6. P.M. Holland et al., Detection of specific polymerase chain reaction product byutilizing the 5’→3’ exonuclease activity of termus aquaticus DNA polymerase, Pro-ceedings of the National Academy of Sciences of the United States of America, Vol.88, 1991, pp. 7276-7280.7. L. Adleman, Molecular computation of solutions to combinatorial problems, Sci-ence, Vol. 266, 1994, pp. 1021-1024.8. J.A. Rose et al., The effect of uniform melting temperatures on the efficiency ofDNA computing, DIMACS Workshop on DNA Based Computers III, 1997, pp. 35-42.9. D.H. Wood, A DNA computing algorithm for directed Hamiltonian paths, Proceed-ings of the Third Annual Conference on Genetic Programming, 1998, pp. 731-734.10. D.H. Wood et al., Universal biochip readout of directed Hamiltonian path problems,Lecture Notes in Computer Science, Springer Verlag, Vol. 2568, pp. 168-181.。