Towards solution of the set-splitting problem on gel-based DNA computing

Weng-Long Chang, Minyi Guo, Michael (Shan-Hui) HoFuture Generation Computer Systems 2004 · DOI

TL;DR

This paper presents a novel DNA computing algorithm for solving the NP-complete set-splitting problem. By leveraging the sticker-based model for constructing solution spaces and employing biological operations within the Adleman-Lipton framework, the authors demonstrate a method to efficiently identify valid solutions, offering a significant step towards practical DNA-based computation for complex problems.

What Problem Does This Paper Address?

The paper tackles the challenge of solving NP-complete problems, a class of computational problems for which no efficient (polynomial-time) algorithm is known. Specifically, it focuses on the "set-splitting problem," which involves partitioning a set S into two subsets, S1 and S2, such that no subset from a given collection C is entirely contained within either S1 or S2. This problem is computationally hard, meaning that as the size of the input grows, the time required to find a solution increases exponentially. Traditional computers struggle with such problems. DNA computing, inspired by the massive parallelism of molecular biology, offers a potential alternative. Previous work by Adleman and Lipton established DNA computing as a viable approach for NP-complete problems like the Hamiltonian path and satisfiability problems. This paper builds upon these foundations by proposing a specific DNA-based algorithm for the set-splitting problem, aiming to improve efficiency and reduce error rates.

Methods

The core of this paper lies in a novel DNA algorithm that combines elements of the Adleman-Lipton model with the sticker-based model.

  • Solution Space Construction (Sticker-Based Model): The algorithm first generates a "solution space" using DNA strands that represent all possible subsets of the input set S. This is achieved by encoding each possible subset as a unique d-digit binary number, where 'd' is the number of elements in S. Each bit in the binary number corresponds to an element in S, with '1' indicating presence and '0' indicating absence. The "sticker" concept is used to design specific DNA sequences (library strands) for each bit, ensuring that these sequences have minimal secondary structures and avoid unintended hybridization, thereby reducing error rates. These library strands are synthesized using a mix-and-split combinatorial technique.
  • Solution Filtering and Identification (Adleman-Lipton Model): Once the solution space is constructed, the algorithm employs a series of biological operations, characteristic of the Adleman-Lipton model, to filter out illegal solutions and identify the legal ones. These operations include:
  • Extract: Separating DNA strands based on the presence or absence of specific "sticker" sequences. This is used to isolate strands that either contain or do not contain certain elements or subsets.
  • Merge: Combining the contents of multiple test tubes (sets of DNA strands).
  • Detect: Determining if a test tube contains any DNA molecules.
  • Discard: Removing unwanted test tubes.

The algorithm iteratively uses these operations to eliminate DNA strands that represent subsets violating the set-splitting condition (i.e., subsets that are entirely contained within a subset from collection C). The remaining strands in the final test tube represent valid solutions to the set-splitting problem.

Datasets

Not discussed in the paper. The paper uses a hypothetical finite set S and a collection C of subsets for demonstration purposes.

Key Insights and Ideas

  • Synergistic Integration: The paper successfully integrates the strengths of the sticker-based model (for robust solution space generation) with the Adleman-Lipton model (for efficient filtering using biological operations). This combination is key to addressing the set-splitting problem.
  • Error Reduction through Design: The emphasis on designing DNA sequences with specific constraints (e.g., avoiding long homopolymer tracts, ensuring mismatches) is crucial for minimizing hybridization errors, a significant challenge in DNA computing.
  • Algorithmic Elegance: The proposed Algorithm 1 provides a clear, step-by-step process that systematically filters the vast solution space to isolate valid set-splitting solutions.
  • Theoretical Foundation: The paper provides theoretical analysis (Theorems 1-4) on the time complexity, volume complexity, number of tubes, and longest library strand length, offering insights into the scalability and efficiency of the proposed DNA algorithm.

Key Results

The paper demonstrates the feasibility of the proposed DNA algorithm through a simulated example. For a finite set S = {1, 2} and a collection C = {{1, 2}}, the algorithm successfully identified the legal partitions: S1 = {1}, S2 = {2} or S1 = {2}, S2 = {1}. The authors also provide theoretical results:

  • Time Complexity: The set-splitting problem can be solved with O(d × f) biological operations, where 'd' is the number of elements in S and 'f' is the number of subsets in C.
  • Solution Space Size: The algorithm requires constructing O(2d) library strands.
  • Tube Usage: The algorithm uses a constant number of three tubes.
  • Library Strand Length: The longest library strand has a length of O(15 × d).

Limitations and Future Work

  • Scalability: While the theoretical complexity is promising, the practical implementation of DNA computing for larger instances of 'd' and 'f' remains a significant challenge due to limitations in current laboratory automation and the exponential growth of the solution space (2d). The paper notes that their simulation was limited to d ≤ 20 due to memory constraints.
  • Experimental Validation: The paper presents simulated results. Actual experimental validation on a physical DNA computer would be a crucial next step to confirm the algorithm's performance and error rates in a real-world setting.
  • Generalization: While the paper focuses on the set-splitting problem, further research could explore the adaptability of this approach to other NP-complete problems or variations of the set-splitting problem.
  • Automation: The authors highlight that their algorithm's operations can be performed in a fully automated manner, which is essential for practical DNA computing. Future work could focus on developing more robust and efficient automated laboratory systems.

Summary updated

BibTeX
@article{chang2004towards,
  author = {Weng-Long Chang and Minyi Guo and Michael (Shan-Hui) Ho},
  title = {{Towards solution of the set-splitting problem on gel-based DNA computing}},
  journal = {Future Generation Computer Systems},
  year = {2004},
  doi = {10.1016/j.future.2003.10.010},
}
Figure