DNA and Databases: The Sticker Complex Model

Abstract

Desoxyribonucle¨ınezuur (DNA) is de drager van genetische informatie in grote en kleine organismen. Een DNA-streng is opgebouwd uit vier verschillende basisdeeltjes, nucleotiden of basen genoemd: A, C, T, en G (zie Figuur 1). Bindingen kunnen ontstaan tussen complementaire basen, A-T en C-G. Twee DNA-strengen die volledig gebonden zijn, vormen de beroemde dubbele helix. Het vormen van bindingen tussen complementaire basen wordt hybridizatie genoemd. Afhankelijk van de lengte en de omgevingsfactoren, kunnen twee niet perfect complementaire DNA-strengen toch binden. Bijvoorbeeld, DNAstrengen CCCACCC en GGGGGGG zijn niet perfect complementair, want basen A en G zijn niet complementair. Toch is het mogelijk dat de C-G-bindingen sterk genoeg zijn om ´e´en imperfectie te tolereren. DNA-moleculen worden bewaard in een waterige oplossing in een proefbuis. Door de oplossing op te warmen worden bindingen tussen basen gebroken, dit proces heet denaturatie. Hybridizatie en denaturatie zijn de twee belangrijkste operaties op DNA-moleculen.

We have developed an abstract model of the DNA molecule, called the sticker complex model, aimed at data storage and data manipulation on the application level and aimed at practical viability on the implementation level. On the sticker complex model an applicative programming language is defined with an emptiness-test, a for-loop and a let statement, called DNAQL. The sticker complex model and its programming language DNAQL is a descendant of Adleman-style DNA computing, with a set of operators implemented by enzymes alongside the omnipresent hybridization. Nonetheless, its focus on data manipulation makes it substantially different from previous computing models. Turing completeness is sacrificed for efficiency and optimizability, as is conventional in database research. Indeed, databases need to handle vast amounts of data and quickly answer a continuous stream of queries. Hence, queries need to be efficiently answerable. One issue in the sticker complex mode, is that the DNAQL operator hybridization can result in infinite complexes. A thorough analysis of this issue resulted in a characterization of terminating hybridization. This laid the foundation of a type system that identifies well behaving programs. The usefulness of the model and the programming language with regards to data storage and manipulation are demonstrated by a simulation of the relational algebra, a corner stone of current database systems. Moreover, the simulation proves to be well typed establishing the power of the type system.