A nano instance-based learning by non-specific hybridization of DNA sequences

doi:10.21203/rs.3.rs-2953096/v1

Download PDF

Article

A nano instance-based learning by non-specific hybridization of DNA sequences

https://doi.org/10.21203/rs.3.rs-2953096/v1

This work is licensed under a CC BY 4.0 License

Version 1

posted

You are reading this latest preprint version

DNA, or deoxyribonucleic acid, is a powerful molecule that plays a fundamental role in the storing and processing genetic information of all living organisms. In recent years, scientists over the world have devoted to taking advantage of its high density, energy efficiency and long durability to solve the challenges in information technology. Here, we propose to build an instance-based learning model by DNA molecules. The handwriting digit images in MNIST dataset are encoded by DNA sequences using a deep learning encoder. And the reversal complementary sequence of a query image is used to hybridize with the training instance sequences. Simulation results by NUPACK show that this classification model by DNA could achieve 95% accuracy on average. Wet-lab experiments also validate the predicted yield is consistent with the hybridization strength. Our work proves that it is feasible to build an effective instance-based classification model for practical application.

Biological sciences/Computational biology and bioinformatics/Image processing

Biological sciences/Biological techniques/Sensors and probes

It is well known that DNA plays a critical role in biological information processing by storing and transmitting the genetic information that is necessary for the development, growth, and function of all living organisms. From the perspective of information processing, DNA molecules have three unique properties: high density, massive parallelism, and low energy consumption^[1]. These advantages make it a promising material to develop nanoscale information processing paradigms. In the last three decades, scientific communities have explored its potential application in three directions: DNA computing, DNA self-assembly, and DNA storage^[2].

In 1994, Adleman first solved a version of traveling salesman problem through DNA hybridization and magnetic bead separation technology^[3]. His pioneering work burned the enthusiasm for a real parallel computing paradigm inherent in biochemical reactions. Tremendous efforts have been paid to solve non-deterministic Polynomial (NP) problems by standard protocols and enzymes at the molecular level, such as satisfiability problem (SAT)^{[4, 5]} , graph coloring problem^[6], and exhaustive attack on cryptography algorithms^[7]. Although DNA computing has the potential for massively parallel processing, the number of DNA molecules required to perform the computation becomes unmanageably large as the size and complexity of the computation increase. This limitation hinders its application from handling larger and more complex computations^[8].

Researchers also developed DNA-based logic gates which could perform simple computational operations, such as AND, OR, and XOR operations^[9]. By combining these logic gates into more complex circuits, they hoped to develop new DNA-based computing systems that can perform more advanced operations. Liu et. al proposed a theoretical model for the logical NAND gate based on the induced hairpin formation of DNA on a solid surface^[10]. DNA strand-displacement reactions (SDR) are a type of biochemical reaction in which one DNA strand displaces another strand from a DNA duplex by hybridizing to one of the strands and breaking the hydrogen bonds that hold the two strands together. One of the key advantages of DNA strand-displacement reactions is their high specificity and programmability. By designing specific DNA sequences, researchers can control the sequence of events during the reaction, allowing for the creation of complex molecular machines and systems^[11]. In 2011, a large-scale molecular circuit was built to implement the square root from 0 to 15 by 130 DNA strands^[12]. In the same year, an SDR-based Hopfield network demonstrated its ability to play a “read your mind” game^[13]. In 2017, Cherry et.al implemented an SDR-based winner-take-all neural network to classify handwritten digits ‘1’ to ‘9’ in the MNIST dataset^[14]. As the size and complexity of the DNA computing or synthetic biology system increase, scalability becomes a significant challenge. And the efficiency and specificity of DNA strand-displacement reactions are sensitive to reaction conditions including temperature, pH, salt concentration, etc.

DNA storage is an emerging technology that uses DNA molecules as a medium for information storage. In 1995, Baum proposed a method that builds an associate memory larger than the brain^[15]. Following his idea, Reif et.al first constructed a DNA library containing sequences which could implement associative search^[16]. Yamamoto et. al constructed a large-scale DNA memory based on nested PCR, which could search over 16 million address spaces^[17]. In recent years, researchers have made significant progress in developing practical and scalable solutions for long-term data storage. In 2012, Church et.al demonstrated the potential of DNA as a storage medium by encoding and decoding a book-length message^[18]. In 2017, Erlich Y. et. al introduced a new approach to DNA storage that uses "DNA Fountain" coding and DNA synthesis on microchips to enable the rapid, low-cost production of large amounts of DNA data^[19]. As the storage capacity increases, data management issue must be considered^[20]. Recently, Organick L. et.al proposed an algorithm to random access in more than 13 million DNA oligonucleotides^[21]. A metastable hybridization-based DNA storage system designed by Kim J. et.al can erase information rapidly and permanently^[22]. Bee et.al implemented a content-based similarity search by encoding the compacted features of images by 80 nucleotides^[23].

Instance-based learning^[24] is a type of non-parametric learning which made prediction for a new data instance based on its similarity to previously observed instances in a training dataset. The algorithms store the entire training dataset in memory and use it to classify new instances based on a similarity measure, such as Euclidean distance or cosine similarity. As they make predictions on the stored instances without building an explicit model, these methods are very flexible, interpretable, robust, and adaptable. The main drawbacks are the expensive memory and computation cost given huge training instances.

In this paper, we propose to construct an instance-based classifier by DNA molecules to recognize the handwritten digits in the MNIST database^[25]. A LeNet-5 network^[25] is used to extract image features while an encoder and a predictor is used to map similar images into similar DNA sequences. Dry-lab simulation results by NUPACK show that the proposed classifier could achieve 95% accuracy on average. And the wet-lab hybridization experiments with 500 instances validate that the predicted yield by NUPACK is consistent with the hybridization strength between the query sequence and the training ones. In sum, both the simulation and wet-lab results demonstrate that it is possible to build a practical instance-based learning model by DNA molecules which could accommodate millions of instances and perform parallel computing.

The workflow of the image encoding architecture.

To build a DNA instance-based classifier for the MNIST database the key issue is to encode digit (0–9) images so that similar ones should be encoded by similar DNA sequences. That is, the reversal complementary sequence of one image should be highly possible to hybrid with the sequences of the same class images, and less likely hybrid with those of the other class images. For this goal, the encoding architecture in Fig. 1A includes three blocks: a LeNet-5 backbone for feature extraction, an encoder and a predictor to map similar feature vectors to similar DNA sequences.

LeNet-5 is a classic convolutional neural network composed of seven layers for handwritten digit recognition. Given a 28×28 grayscale image, the output of the second fully-connected layer (FC2) is used as its feature vector. The encoder consists of two fully connected layers to translate a feature vector into the one-hot encoded DNA sequence. The predictor includes two convolutional layers to predict the hybridization degree of DNA duplex, here referred to as “simulated yield”. In biochemistry, yield is the amount of substance that is obtained from a particular biological process or reaction, usually expressed as a percentage. Specifically, the closer the yield is to 1, the stronger the hybridization degree of the DNA duplex.

Figure 1B shows the workflow of the encoding architecture, and the training process includes three stages:

First, train the LeNet-5 backbone to classify the 60,000 images in MNIST database;

Second, train the predictor by 300,000 DNA sequences pairs whose yields are labeled by NUPACK^[26];

Finally, train the encoder based on the similarity of the feature vectors, their MNIST labels and the predicted yield.

The encoding performance

The MNIST database is composed of two mutually exclusive subsets: training set of 60, 000 images and testing set of 10, 000 images. Figure 2A shows the clustering result of the training images on a 2-D plane by t-SNE^[27], where the left is based on the LeNet-5 feature vectors and the right is on the encoded DNA sequences. In both cases, images within the same class label are almost clustered in the same group. But their neighboring relationship in the feature vector space may be different from that in the DNA sequence space.

This is because the training process considers both the label similarity and the hybridization constraint. This difference in neighboring relationship can be observed for the 4 pair images in Group A and B. In general, the encoded DNA sequences could reflect the similarity of images to a high degree.

To quantify the hybridization degree, we define the yield for a pair of DNA sequences as the concentration ratio of the DNA duplex at equilibrium to that at the initial concentration. This value generally ranges from 0 to 1. Figure 2B shows the distribution of hybridization yield according to the Euclidean distance of their feature vectors. Most of the yield is larger than 0.8 when the Euclidean distance is less than 9, and the yield is close to 0 when the Euclidean distance is larger than 17. When the Euclidean distance ranges from 9 to 16, about one-third is close to one and the rest is close to zero. Figure 2C presents 4 pairs of images to reflect the relationship between their similarity and the Euclidean distance. When the Euclidean distance is larger than 9, most of the images tenders to be different. All in all, the yield distribution reveals that the encoder assures similar images usually have a large hybridization yield (> 0.7) while those dissimilar have a low yield(< 0.2).

Figure 2D shows the top 50 nearest neighbors of a query sequence of image ‘5’ according to the predicted yield by NUPACK. As expected, images of digit ‘5’ are the first majority which is 46%. The second and third majority comes from digits ‘9’ and ‘6’ which is about 14% and 12%. Further, most of the images of digit ‘5’ are in the top 30. This means that the total hybridization yield of the query sequence with those of digit ‘5’ should be significantly larger than that with other digit images. This demonstrates that the total yield of the query sequence with each digit label could serve as an indicator of the similarity degree.

Simulated classification performance by NUPACK

We randomly select 1000 images (100 for each digit number) from the MNIST testing set to verify the performance of the proposed instance-based classifier by the MNIST training set. Given one query image, we calculate the total yield of its encoding sequence with those in each digit number respectively by NUPACK. The largest yield class will be the predicted as its class label. Details of the simulation experiment can be found in Method section.

Figure 3A and 3B show the yield distribution of these query sequences with those in the same digit class(A) and those from other class(B). Comparing 3A and 3B, we could see that these query sequences usually have larger yield with their own class sequences (> 0.8) and smaller yield with other class sequences (< 0.1). These observations indicate that the query sequences tender to have higher yield with their own class instances than with other class ones.

Figure 3C presents the average accuracy for each digit class and the overall accuracy is about 95%. Only digit class ‘4’ has the least accuracy (86%), and this is consistent with the yield distribution in Fig. 3A and 3B. That is, the query sequences have relative low yield with their own class sequences and relative larger yield with other class sequences. The main reason may be attributed to its relative low encoding quality. Back to the clustering results in Fig. 2B, we can see that the 6000 training instances for digit ‘4’ are scattered in two sub-clusters which are surrounded by 6 other clusters. Furthermore, Fig. 3D presents the 51 misclassified query images and most of them are irregular handwritings. Their detailed predicted yields for each class can be found in supplementary Table 1.

Experimental validation of the hybridization yield

We construct a small classifier by randomly selecting 50 sequences for each digit label. Figure 4A shows the average yield of 9 query sequences (0–9) predicted by NUPACK. For each query sequence, the predicted yield with its own label is always the largest (see the diagonal values in each row). That means this small classifier could correctly recognize the digit number for the 10 query sequences (0–9).

To verify this observation, we conduct a wet-lab experiment to measure the real hybridization strength between the 9 query sequences and the 50 training samples for digit 3. Figure 4B shows the measured fluorescence intensity, and the larger the intensity, the higher degree of the hybridization would be. For each case, we repeat the three-time experiments. Columns A and B are used as control groups for TE buffer and TE buffer added with fluorescent dye respectively. The rest columns correspond to query sequences for 0(Q0) to 9(Q9). We could see that column F(Q3) has the largest fluorescence intensity than others. That is, query sequence Q3 has the highest hybridization strength with the training sequences. And columns K(Q8), J(Q7), and H(Q5) have a relative larger intensity. These observed fluorescence intensities are consistent with the average predicted yield for the 10 query sequences in Fig. 4A. This demonstrates that the predicted yield could reflect the hybridization strength, and it is feasible to build a large classifier with DNA sequences which is composed of tens of thousands of instances.

In this paper, we propose to construct an instance-based classifier by non-specific hybridization of DNA sequences. Images in the MNIST dataset are encoded into DNA sequences by a deep learning network in Fig. 1. Then the DNA sequences representing the training images are synthesized and those belonging to the same class are grouped in one test tube or a spot on a solid surface. The reversal complementary sequences of the query image are used to hybridize with those DNA sequences simultaneously. Finally, the winner label (or the one with the largest hybridization strength) is assigned as the output. Simulation results by NUPACK and the wet-lab experiment demonstrate the feasibility of the proposed method. Compared with the SDR-based classifier^[14], the proposed classifier by non-specific hybridization has the following advantages.

Firstly, it is more robust. The implementation of the cascade of the seesaw DNA gate is not only time-consuming, but also sensitive to biochemical reaction conditions, such as the concentration gradient of substrates, temperature, and perfect hybridization. On the contrary, the non-specific hybridization process in the proposed classifier requires no these rigorous requirements and it only needs one round of hybridization.

Secondly, it is easily implemented and more efficient. The cascade of SDR reactions is very complicated and laborious, which has to screen the output DNA strands as the input of the next round of reaction. The proposed classifier could be implemented on a solid surface on which millions of samples can be organized according to their class labels. The fluorescence intensity of hybridization can be directly read out by an optical scanning machine. Furthermore, the non-specific hybridization relieves the computation burden to calculate the similarity between the query sample and the training samples. Combined with the nanoscale of DNA molecules, it provides an easy way to construct a classifier with massive instances.

Thirdly, it is extendible and flexible to larger classes. In Cherry’s work^[14], they only accomplished 1–9 digit recognition. To recognize more classes, the complexity of the SDR computation circuit had to be increased dramatically. However, the proposed classifier could accommodate problems with a hundred or thousand classes by modifying the encoding network structure and increasing the length of the encoding DNA sequences.

The hybridization degree of DNA sequences is an ideal distance metric for both search algorithms and classifications. But we are convinced that DNA-based classifiers have more practicability than similarity search at this stage. Because of the considerable expenditures and latency of synthesis, separation, amplification and sequencing. Meanwhile, error correction of sequences is another issue to be considered. Though DNA-based similarity search performs comparably to state-of-the-art in silico algorithms, these costs cast a shadow over practical applications. In our work, we eliminate the needs of separation and sequencing, but only fluorescent dye staining to indicate classification results. The mechanism brings great convenience and operability for the proposed approach.

Feature extraction. We first fine-tune the struct of LeNet-5: modify the dimension of the second linear layer to 50 and train the network by MNIST training set as usual. Then drop the last layer of LeNet-5 and froze the optimal model parameters of other layers. The outputs of the second linear layer are used as the image feature vectors.

Sequence encoding. The encoder is composed of 2 fully-connected layers which map a 50-D image feature vector to a matrix of 59 \(\times\) 4. Each row of the matrix is a 4-channel probability vector whose components sum to 1. Each channel represents one of the 4 bases: adenine (A), thymine (T), cytosine (C), and guanine (G). At each position, the channel with the maximum probability is assigned to the corresponding base.

Encoder training. Encoder aims to map similar images to similar DNA sequences. Specifically, the reversal complementary of one sequence should hybridize with the other with high yield while dissimilar sequences tender to have low yield. For pairs of images, the loss function of the encoder considers the following three factors during the training process: 1) Euclidean distance of feature vectors; 2) The consistency of the MNIST labels; 3) their simulated yield.

Predictor training. The predictor mainly supervises the performance of the encoder. A randomly generated dataset of 300,000 DNA sequences pairs is used to train the predictor. The yield of each pair of sequences is determined by NUPACK. As the yield usually ranges from 0 to 1, mean square error (MSE) is used as the loss function to optimize the predictor.

NUPACK protocol. (1) DNA analysis model at 25\(℃\); (2) concentration of \(1nmol/L\) for both positive-strand and negative-strand;(3) constrain complex is consists of up to 2 DNA sequences; (4) No metal ions added. Other omitted parameters are by default.

Dry-lab experiment parameters: (1) DNA analysis model at 25\(℃\); (2) concentration of each labeled sequence \(1nmol/L\); (3) concentration of the query sequence \(1\mu mol/L\); (4) Constrain complex consists of up to 2 DNA sequences; (5) No metal ions added. Other omitted parameters are by default.

Materials and equipments. The DNA oligonucleotides for the wet-lab experiment are purchased from SBS Genetech Co.Ltd. and purified by Ultra PAGE (Ultra-Polyacrylamide Gel Electrophoresis). They are dissolved in TE buffer (Beijing Solarbio Science & Technology Co.,Ltd.)and stored at − 20°C. The SYBR GreenⅠ(SGⅠ), purchased from MCE (MedChemExpress, USA), is stored at − 20°C. Cytomics FC 500 (Beckman Coulter, USA) is the instrument to measure fluorescence intensity.

DNA is dissolved in TE buffer solution (50 mmol/ l pH 8.0) and diluted to 10 µ mol/ L. Then, each of the 10 µ L template (10 µ Mol/ L) are added to a 1.5 ml centrifuge tube and10 µ L DNA aptamer (10 µ Mol/ L), vortex mixed, and heated at 95 ° C for 10 min to open the secondary knot of single-stranded DNA Structure. Slowly cool to room temperature and dilute with TE buffer solution. The final concentration of aptamer and DNA template is 50 nmol/ L, and the dsDNA is stored at 4 ℃ for standby. Add 100 µ L dsDNA (50 nmol/L) to a cell of microplate, followed by 10 µ L SGI of which the final concentration is 10*SGI and excessive. TE buffer only and TE buffer with SGI are taken as control blanks. There are three repeats for each reaction.

Cytomics FC 500 is used to measure and record the fluorescence intensity. The parameters are: 25 ℃, medium speed vibrating plate for 20 seconds, incubation for 10 minutes, emission length of 485 nanometers, and absorption wavelength of 520 nanometers.

Competing interests

The authors declare no competing interests.

Ceze, L., Nivala, J. and Strauss, K. Molecular digital data storage using DNA. Nat Rev Genet. 20(8): 456-466.(2019)
Meiser, L. C., Nguyen, B. H., Chen, Y. J., Nivala, J., Strauss, K., Ceze, L. and Grass, R. N. Synthetic DNA applications in information technology. Nat Commun. 13(1): 352.(2022)
Adleman. Molecular Computation of Solutions to Combinatorial Problems. Science. 1994)
Liu, W., Gao, L., Liu, X., Wang, S. and Xu, J. Solving the 3-SAT problem based on DNA computing. Journal of chemical information and computer sciences. 43(6): 1872-1875.(2003)
Liu, W., Gao, L., Zhang, Q., Xu, G., Zhu, X., Liu, X. and Xu, J. A random walk DNA algorithm for the 3-SAT problem. Current Nanoscience. 1(1): 85-90.(2005)
Liu, W., Zhang, F. and Xu, J. A DNA algorithm for the graph coloring problem. Journal of chemical information and computer sciences. 42(5): 1176-1178.(2002)
Adleman, L. M., Rothemund, P. W., Roweis, S. and Winfree, E. On applying molecular computation to the data encryption standard. Journal of computational biology. 6(1): 53-63.(1999)
Cox, J. C., Cohen, D. S. and Ellington, A. D. The complexities of DNA computation. Trends in biotechnology. 17(4): 151-154.(1999)
Liu, W., Zhu, X., Wang, X., Yin, Z. and Wang, S. Simulating the XOR gates based on the induced hairpin formation. Current Nanoscience. 4(1): 108-110.(2008)
Liu, W., Shi, X., Zhang, S., Liu, X. and Xu, J. A new DNA computing model for the NAND gate based on induced hairpin formation. Biosystems. 77(1-3): 87-92.(2004)
Yurke, B., Turberfield, A. J., Mills, A. P., Simmel, F. C. and Neumann, J. L. A DNA-fuelled molecular machine made of DNA. Nature. 406(6796): 605-608.(2000)
Qian, L. and Winfree, E. Scaling up digital circuit computation with DNA strand displacement cascades. science. 332(6034): 1196-1201.(2011)
Qian, L., Winfree, E. and Bruck, J. Neural network computation with DNA strand displacement cascades. nature. 475(7356): 368-372.(2011)
Cherry, K. M. and Qian, L. Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks. Nature. 559(7714): 370-376.(2018)
Baum, E. B. Building an associative memory vastly larger than the brain. Science. 268(5210): 583-585.(1995)
Reif J H, LaBean T H, Pirrung M, et al. Experimental construction of very large scale DNA databases with associative search capability. DNA Computing: 7th International Workshop on DNA-Based Computers, DNA7 Tampa, FL, USA, June 10–13, 2001 Revised Papers 7. Springer Berlin Heidelberg,231-247 (2002).
Yamamoto, M., Kashiwamura, S., Ohuchi, A. and Furukawa, M. Large-scale DNA memory based on the nested PCR. Natural Computing. 7(3): 335-346.(2008)
Church, G. M., Gao, Y. and Kosuri, S. Next-generation digital information storage in DNA. Science. 337(6102): 1628.(2012)
Erlich, Y. and Zielinski, D. DNA Fountain enables a robust and efficient storage architecture. science. 355(6328): 950-954.(2017)
ZAN, X., YAO, X., XU, P., BAO, Z., LI, X., LI, X. and LIU, W. A Survey on File Architecture in DNA Storage. JOURNAL OF ELECTRONICS & INF ORMATION TECHNOLOGY. 44: 1-10.(2022)
Organick, L., Ang, S. D., Chen, Y. J., Lopez, R., Yekhanin, S., Makarychev, K., Racz, M. Z., Kamath, G., Gopalan, P., Nguyen, B., Takahashi, C. N., Newman, S., Parker, H. Y., Rashtchian, C., Stewart, K., Gupta, G., Carlson, R., Mulligan, J., Carmean, D., Seelig, G., Ceze, L. and Strauss, K. Random access in large-scale DNA data storage. Nat Biotechnol. 36(3): 242-248.(2018)
Kim, J., Bae, J. H., Baym, M. and Zhang, D. Y. Metastable hybridization-based DNA information storage to allow rapid and permanent erasure. Nat Commun. 11(1): 5008.(2020)
Bee, C., Chen, Y.-J., Ward, D., Liu, X., Seelig, G., Strauss, K. and Ceze, L. Content-Based Similarity Search in Large-Scale DNA Data Storage System. bioRxiv. 2020)
Daelemans, W., Van den B., Antal. Memory-based language processing. Cambridge University Press. (2005)
LeCun, Y., Bottou, L., Bengio, Y. and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE. 86(11): 2278-2324.(1998)
Zadeh, J. N., Steenberg, C. D., Bois, J. S., Wolfe, B. R., Pierce, M. B., Khan, A. R., Dirks, R. M. and Pierce, N. A. NUPACK: Analysis and design of nucleic acid systems. Journal of computational chemistry. 32(1): 170-173.(2011)
Van der Maaten, L. and Hinton, G. Visualizing data using t-SNE. Journal of machine learning research. 9(11): 2008)

There is NO Competing Interest.

SIAuthorFree.docx
Supplemental material for A nano instance-based learning by non-specific hybridization of DNA sequences
FigS1.tif
TableS1.tif
TableS2.tif

Download PDF

Version 1

posted

You are reading this latest preprint version

A nano instance-based learning by non-specific hybridization of DNA sequences

Status:

Version 1

Abstract

Figures

Introduction

Results

The encoding performance

Simulated classification performance by NUPACK

Experimental validation of the hybridization yield

Discussion

Method

Declarations

Competing interests

References

Additional Declarations

Supplementary Files

Status:

Version 1