Molecular learning with DNA kernel machines

Yung-Kyun Noh, Daniel D. Lee, Kyung-Ae Yang, Cheong-Tag Kim, Byoung-Tak ZhangBiosyst 2015 · DOI

TL;DR

This paper introduces a novel biomolecular algorithm for learning and classification using DNA molecules. By interpreting DNA hybridization as a kernel computation, they demonstrate a method for in vitro pattern recognition that achieves competitive performance with traditional machine learning algorithms, paving the way for seamless integration of computation within biological systems.

What Problem Does This Paper Address?

The paper tackles the challenge of creating computational systems that can learn and adapt within biological environments. While previous research has explored molecular computation for tasks like logic gates or implementing pre-defined neural networks using DNA, a significant gap has been the ability for these molecular systems to learn from examples and adapt their behavior. This is crucial for applications like disease detection within living tissues, where the system needs to recognize patterns without prior explicit programming. The authors aim to bridge this gap by developing a molecular learning algorithm that can perform pattern recognition directly on DNA molecules.

Methods

The core innovation lies in framing molecular learning within the context of kernel machines. The authors propose that DNA hybridization, the process of two single-stranded DNA molecules binding to form a double strand, can be interpreted as computing the inner product between vectors representing these DNA sequences in a high-dimensional feature space. This is the essence of the kernel trick in machine learning.

Key methodological aspects include:

  • DNA Kernel Definition: The kernel element $K_{ij}$ is defined as the quantity of hybridized double strands formed between sequence $i$ and the complement of sequence $j$. This quantity is directly measurable in vitro.
  • Molecular Learning Algorithm: A two-phase process is proposed:
  • Learning Phase: This involves iterative hybridization and selection of "hetero-labeled" double-stranded DNA molecules. This process is mathematically shown to converge to a population of molecules representing a weight vector that captures discriminative information from the training data. This is analogous to finding the closest vectors within the convex cones of different classes in the feature space.
  • Classification Phase: An unknown DNA sequence is hybridized with the learned population. The resulting hybridization amount is used to classify the unknown sequence, effectively computing the inner product with the learned weight vector.
  • Annealing Schedule for Positive Definiteness: A crucial aspect is ensuring the resulting kernel matrix is positive definite, a requirement for many kernel methods. The authors demonstrate that a controlled annealing schedule (gradually cooling the temperature during hybridization) guarantees this property, preventing issues with non-positive definite kernels that can lead to poor classification.
  • Biomolecular Implementation: The paper outlines a potential in vitro implementation using DNA hybridization, denaturing, PCR amplification, and gel electrophoresis. They propose using different lengths of DNA molecules for different classes to facilitate separation.

Datasets

The paper utilizes both simulated and real-world datasets for evaluation:

  • Artificial Datasets: Used for initial simulations to demonstrate the concept and the effect of different temperature schedules on kernel properties and classification boundaries.
  • Real Biological Datasets:
    • Gene Expression Data (AML/ALL): Microarray data from leukemia cells, preprocessed and encoded into binary strings of length 1000.
  • DNA Sequence Classification: Datasets involving the classification of sequences based on the presence of splice regions, including data from C. elegans, Drosophila, and synthetic sequences.

Key Insights and Ideas

  • DNA Hybridization as a Kernel: The fundamental insight is that the physical process of DNA hybridization can be directly mapped to the mathematical concept of a kernel function, enabling the application of powerful kernel-based machine learning algorithms in a molecular context.
  • In Vitro Learning: The algorithm demonstrates that learning and classification can occur directly on DNA molecules without relying on conventional electronic computers for the core computation. This opens doors for truly bio-integrated computing.
  • Annealing for Kernel Properties: The temperature schedule during hybridization is not just a parameter but a critical control mechanism for ensuring the positive definiteness and controlling the sparsity of the DNA kernel matrix. This is a novel way to tune kernel properties.
  • Geometric Interpretation of Molecular Learning: The learning process is elegantly interpreted geometrically as finding the closest vectors within the convex cones of different classes in a high-dimensional feature space, providing a clear understanding of how the molecular operations achieve classification.

Key Results

  • Competitive Performance: The proposed DNA learning algorithm achieved performance comparable to, and in some cases superior to, standard machine learning algorithms like Support Vector Machines (SVMs) and Kernel Fisher Discriminant Analysis (kFDA) on benchmark datasets.
  • Positive Definite Kernels: Simulations and theoretical analysis confirmed that a controlled annealing temperature schedule reliably produces positive definite kernel matrices, essential for stable learning.
  • Sparsity Control: The temperature schedule and the design of DNA sequences (e.g., using common patterns) can be used to control the sparsity of the kernel matrix, influencing the decision surface.
  • Preliminary Wet Lab Results: The paper includes gel electrophoresis results demonstrating the separation of hybridized DNA molecules, providing initial experimental validation for the proposed biomolecular implementation.

Limitations and Future Work

  • Yield Optimization: The authors acknowledge that future work needs to focus on optimizing the yield of these biomolecular processes.
  • Complex DNA Operational Design: Real-world implementation requires addressing additional complex constraints in DNA operational design.
  • Experimental Validation: While preliminary results are presented, extensive experimental validation of the full learning algorithm in vitro is still needed.
  • Scalability and Robustness: Further research is required to assess the scalability of the approach to larger datasets and its robustness to biological noise and variations.
  • Seamless Integration: The ultimate goal of implementing learning and classification seamlessly within a living cell remains a long-term objective.

Summary updated

BibTeX
@article{noh2015molecular,
  author = {Yung-Kyun Noh and Daniel D. Lee and Kyung-Ae Yang and Cheong-Tag Kim and Byoung-Tak Zhang},
  title = {{Molecular learning with DNA kernel machines}},
  journal = {Biosyst.},
  year = {2015},
  doi = {10.1016/j.biosystems.2015.06.007},
}
Figure