Programming in biomolecular computation

Research output: Contribution to journalConference articleResearchpeer-review

Documents

Our goal is to provide a top-down approach to biomolecular computation. In spite of widespread discussion about connections between biology and computation, one question seems notable by its absence: Where are the programs? We introduce a model of computation that is evidently programmable, by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its functioning is defined by a single and relatively small set of chemical-like reaction rules. Further properties: the model is stored-program: programs are the same as data, so programs are not only executable, but are also compilable and interpretable. It is universal: all computable functions can be computed (in natural ways and without arcane encodings of data and algorithm); it is also uniform: new “hardware” is not needed to solve new problems; and (last but not least) it is Turing complete in a strong sense: a universal algorithm exists, that is able to execute any program, and is not asymptotically inefficient.

A prototype model has been implemented (for now in silico on a conventional computer). This work opens new perspectives on just how computation may be specified at the biological level.

Original languageEnglish
JournalElectronical Notes in Theoretical Computer Science
Volume268
Pages (from-to)97-114
Number of pages18
ISSN1571-0661
DOIs
Publication statusPublished - 2010
Event1st International Workshop on Interactions between Computer Science and Biology - Amsterdam, Netherlands
Duration: 10 Jun 201010 Jun 2010
Conference number: 1

Conference

Conference1st International Workshop on Interactions between Computer Science and Biology
Number1
CountryNetherlands
CityAmsterdam
Period10/06/201010/06/2010

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 16411659