DNA computing of solutions to knapsack problems |
| |
Authors: | Henkel Christiaan V Bäck Thomas Kok Joost N Rozenberg Grzegorz Spaink Herman P |
| |
Affiliation: | Institute of Biology, Leiden University, Wassenaarseweg 64, 2333 AL Leiden, The Netherlands. |
| |
Abstract: | One line of DNA computing research focuses on parallel search algorithms, which can be used to solve many optimization problems. DNA in solution can provide an enormous molecular library, which can be searched by molecular biological techniques. We have implemented such a parallel search for solutions to knapsack problems, which ask for the best way to pack a knapsack of limited volume. Several instances of knapsack problems were solved using DNA. We demonstrate how the computations can be extended by in vivo translation of the DNA library into protein. This combination of DNA and protein allows for multi-criterion optimization. The knapsack computations performed can then be seen as protein optimizations, one of the most complex computations performed by natural systems. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|