The Library
Models of DNA computation
Tools
UNSPECIFIED (1996) Models of DNA computation. In: 21st International Symposium on Mathematical Foundations of Computer Science (MFCS 96), JAGIELLONIAN UNIV, POLONIA INST, KRAKOW, POLAND, SEP 0206, 1996. Published in: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1996, 1113 pp. 1836.
Full text not available from this repository.Abstract
The idea that living cells and molecular complexes can be viewed as potential machinic components dates back to the late 1950s, when Richard Feynman delivered his famous paper describing submicroscopic computers. Recently, several papers have advocated the realisation of massively parallel computation using the techniques and chemistry of molecular biology. Algorithms are not executed on a traditional, siliconbased computer, but instead employ the testtube technology of genetic engineering. By representing information as sequences of bases in DNA molecules, existing DNAmanipulation techniques may be used to quickly detect and amplify desirable solutions to a given problem.
We review the recent spate of papers in this field and take a critical view of their implications for laboratory experimentation. We note that extant models of DNA computation are flawed in that they rely upon certain errorprone biological operations. The one laboratory experiment that is seminal for current interest and claims to provide an efficient solution for the Hamiltonian path problem has proved to be unrepeatable by other researchers. We introduce a new model of DNA computation whose implementation is likely to be far more errorresistant than extant proposals. We describe an abstraction of the model which lends itself to natural algorithmic description, particularly for problems in the complexity class NP. In addition we describe a number of lineartime parallel algorithms within our model, particularly for NPcomplete problems. We describe an ''in vitro'' realisation of the model and conclude with a discussion of future work and outstanding problems.
Item Type:  Conference Item (UNSPECIFIED)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Series Name:  LECTURE NOTES IN COMPUTER SCIENCE  
Journal or Publication Title:  MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1996  
Publisher:  SPRINGERVERLAG BERLIN  
ISBN:  3540615504  
ISSN:  03029743  
Editor:  Penczek, W and Szalas, A  
Official Date:  1996  
Dates: 


Volume:  1113  
Number of Pages:  19  
Page Range:  pp. 1836  
Publication Status:  Published  
Title of Event:  21st International Symposium on Mathematical Foundations of Computer Science (MFCS 96)  
Location of Event:  JAGIELLONIAN UNIV, POLONIA INST, KRAKOW, POLAND  
Date(s) of Event:  SEP 0206, 1996  
URI:  http://wrap.warwick.ac.uk/id/eprint/17764 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 