| Popis: |
Summarization: DNA self-assembly has been proposed as a way to cope with huge combinatorial NP-HARD problems, such as satisability. However, the algorithmic designs for DNA self-assembly proposed so far are highly dependent on the instance to be solved. The required work (DNA synthesis, tile construction, encoding, etc.) can be done only after the instance is given. This paper presents an algorithmic design for solving satisability problems using two-dimensional DNA self-assembly (tiling). The main driving factor in this work was the design and encoding of the algorithm in a general way that minimizes the dependency on particular instances. In eect, a large amount of work and preparation can be done in advance as a batch process in the absence of any particular instance. In practice, it is likely that the total time (from the time an instance is given, to the time a solution is returned) will be decreased signicantly and laboratory procedures will be simplied. Παρουσιάστηκε στο: 5th DIMACS Workshop on DNA Based Computers |
