Recognizing DNA Splicing

Matteo Cavaliere, Natasa Jonoska, Peter Leupold

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Motivated by recent techniques developed for observing evolutionary dynamics of a single DNA molecule, we introduce a formal model for accepting an observed behavior of a splicing system. The main idea is to input a marked DNA strand into a test tube together with certain restriction enzymes and, possibly, with other DNA strands. Under the action of the enzymes, the marked DNA strand starts to evolve by splicing with other DNA strands. The evolution of the marked DNA strand is “observed” by an outside observer and the input DNA strand is “accepted” if its (observed) evolution follows a certain expected pattern. We prove that using finite splicing system (finite set of rules and finite set of axioms), universal computation is attainable with simple observing and accepting devices made of finite state automata.
Original languageEnglish
Title of host publicationDNA Computing
Subtitle of host publication11th International Workshop on DNA Computing, DNA11, London, ON, Canada, June 6-9, 2005. Revised Selected Papers.
EditorsAlessandra Carbone, Niles A. Pierce
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-34165-9
ISBN (Print)978-3-540-34161-1
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Recognizing DNA Splicing'. Together they form a unique fingerprint.

Cite this