UNSPECIFIED (1996) Models of DNA computation. In: 21st International Symposium on Mathematical Foundations of Computer Science (MFCS 96), SEP 02-06, 1996, JAGIELLONIAN UNIV, POLONIA INST, KRAKOW, POLAND.

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 sub-microscopic 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, silicon-based computer, but instead employ the test-tube technology of genetic engineering. By representing information as sequences of bases in DNA molecules, existing DNA-manipulation 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 error-prone 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 error-resistant 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 linear-time parallel algorithms within our model, particularly for NP-complete 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:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-61550-4
ISSN:	0302-9743
Editor:	Penczek, W and Szalas, A
Date:	1996
Volume:	1113
Number of Pages:	19
Page Range:	pp. 18-36
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 02-06, 1996
URI:	http://wrap.warwick.ac.uk/id/eprint/17764

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item