Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/F6262134-523A-4CA3-87F8-6A2364848C8F | ||
| Year | 1999 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | M.G. Lagoudakis and T.H. LaBean. (1999, June). 2D DNA self–assembly for satisfiability. [Online]. Available:https://users.cs.duke.edu/~thl/papers/Lagoudakis_LaBean.pdf | ||
| Appears in Collections |
DNA self-assembly has been proposed as a way to cope with huge combinatorial NP-HARDproblems, such as satisability. However, the algorithmic designs for DNA self-assemblyproposed 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 isgiven. This paper presents an algorithmic design for solving satisability problems usingtwo-dimensional DNA self-assembly (tiling). The main driving factor in this work was thedesign and encoding of the algorithm in a general way that minimizes the dependency onparticular instances. In eect, a large amount of work and preparation can be done inadvance as a batch process in the absence of any particular instance. In practice, it islikely that the total time (from the time an instance is given, to the time a solution isreturned) will be decreased signicantly and laboratory procedures will be simplied.
Copyright © DIAS 2013
