title: DNA computing of solutions to knapsack problems.
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.
authors.affiliation: Institute of Biology, Leiden University, Wassenaarseweg 64, 2333 AL Leiden, The Netherlands.
authors.forename: Christiaan V
authors.initials: CV
authors.lastname: Henkel
authors.forename: Thomas
authors.initials: T
authors.lastname: Bäck
authors.forename: Joost N
authors.initials: JN
authors.lastname: Kok
authors.forename: Grzegorz
authors.initials: G
authors.lastname: Rozenberg
authors.forename: Herman P
authors.initials: HP
authors.lastname: Spaink
mesh_terms: D000465:Algorithms; D039301:Computers, Molecular / Q000706:statistics & numerical data; D015723:Gene Library; D010957:Plasmids / Q000235:genetics; D014176:Protein Biosynthesis; D049490:Systems Biology