Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13016
Title: A Formal Model for Databases in DNA
Authors: GILLIS, Joris 
VAN DEN BUSSCHE, Jan 
Issue Date: 2012
Publisher: Springer-Verlag
Source: Horimoto, Katsuhisa; Nakatsui, Masahiko; Popov, Nicolaj (Ed.). Proceedings of Algebraic and Numeric Biology 2010, Springer-Verlag, p.18-37.
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 6479
Abstract: Our goal is to better understand, at a theoretical level, the database aspects of DNA computing. Thereto, we introduce a formally defined data model of so-called sticker DNA complexes, suitable for the representation and manipulation of structured data in DNA. We also define DNAQL, a restricted programming language over sticker DNA complexes. DNAQL stands to general DNA computing as the standard relational algebra for relational databases stands to general-purpose con- ventional computing. The number of operations performed during the execution of a DNAQL program, on any input, is only polynomial in the dimension of the data, i.e., the number of bits needed to represent a single data entry. Moreover, each operation can be implemented in DNA using a constant number of laboratory steps. We prove that the relational algebra can be simulated in DNAQL.
Keywords: DNA Computing; Formal Model; Relational Algebra;DNA Computing, theoretical computer science, hybridization, graphs
Document URI: http://hdl.handle.net/1942/13016
ISBN: 978-3-642-28066-5
DOI: 10.1007/978-3-642-28067-2_2
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
hagenberg.pdfPreprint510.2 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

4
checked on Sep 3, 2020

Page view(s)

46
checked on May 25, 2022

Download(s)

88
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.