Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13016Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | GILLIS, Joris | - |
| dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
| dc.date.accessioned | 2012-01-18T10:16:38Z | - |
| dc.date.available | NO_RESTRICTION | - |
| dc.date.available | 2012-01-18T10:16:38Z | - |
| dc.date.issued | 2012 | - |
| dc.identifier.citation | Horimoto, Katsuhisa; Nakatsui, Masahiko; Popov, Nicolaj (Ed.). Proceedings of Algebraic and Numeric Biology 2010, Springer-Verlag, p.18-37. | - |
| dc.identifier.isbn | 978-3-642-28066-5 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/13016 | - |
| dc.description.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. | - |
| dc.language.iso | en | - |
| dc.publisher | Springer-Verlag | - |
| dc.relation.ispartofseries | Lecture Notes in Computer Science | - |
| dc.subject.other | DNA Computing; Formal Model; Relational Algebra | - |
| dc.subject.other | DNA Computing, theoretical computer science, hybridization, graphs | - |
| dc.title | A Formal Model for Databases in DNA | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.authors | Horimoto, Katsuhisa | - |
| local.bibliographicCitation.authors | Nakatsui, Masahiko | - |
| local.bibliographicCitation.authors | Popov, Nicolaj | - |
| local.bibliographicCitation.conferencedate | July 31-August 2, 2010 | - |
| local.bibliographicCitation.conferencename | Algebraic and Numeric Biology | - |
| local.bibliographicCitation.conferenceplace | Hagenberg - Austria | - |
| dc.identifier.epage | 37 | - |
| dc.identifier.spage | 18 | - |
| local.bibliographicCitation.jcat | C1 | - |
| dc.relation.references | Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995) Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 226, 1021–1024 (1994) CrossRef Amos, M.: Theoretical and Experimental DNA Computation. Springer, Heidelberg (2005) Arita, M., Hagiya, M., Suyama, A.: Joining and rotating data with molecules. In: Proceedings 1997 IEEE International Conference on Evolutionary Computation, pp. 243–248 (1997) Boneh, D., Dunworth, C., Lipton, R.J., Sgall, J.: On the computational power of DNA. Discrete Applied Mathematics 71, 79–94 (1996) CrossRef Cardelli, L.: Strand algebras for DNA computing. In: Deaton and Suyama [9], pp. 12–24 Chen, J., Deaton, R.J., Wang, Y.-Z.: A DNA-based memory with in vitro learning and associative recall. Natural Computing 4(2), 83–101 (2005) CrossRef Condon, A.E., Corn, R.M., Marathe, A.: On combinatorial DNA word design. Journal of Computational Biology 8(3), 201–220 (2001) CrossRef Deaton, R., Suyama, A. (eds.): DNA 15. LNCS, vol. 5877. Springer, Heidelberg (2009) Diatchenko, L., Lau, Y.F., et al.: Suppression subtractive hybridization: a method for generating differentially regulated or tissue-specific cDNA probes and libraries. Proceedings of the National Academy of Sciences 93(12), 6025–6030 (1996) CrossRef Dirks, R.M., Pierce, N.A.: Triggered amplification by hybridization chain reaction. Proceedings of the National Academy of Sciences 101(43), 15275–15278 (2004) CrossRef Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999) Liu, Q., Wang, L., et al.: DNA computing on surfaces. Nature 403, 175–179 (1999) Lyngsø, R.B.: Complexity of Pseudoknot Prediction in Simple Models. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 919–931. Springer, Heidelberg (2004) CrossRef Majumder, U., Reif, J.H.: Design of a biomolecular device that executes process algebra. In: Deaton and Suyama [9], pp. 97–105 Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing. Springer, Heidelberg (1998) Ramakrishnan, R., Gehrke, J.: Database Management Systems. McGraw-Hill (2002) Reif, J.H.: Parallel biomolecular computation: models and simulations. Algorithmica 25(2-3), 142–175 (1999) CrossRef Reif, J.H., LaBean, T.H., Pirrung, M., Rana, V.S., Guo, B., Kingsford, C., Wickham, G.S.: Experimental Construction of Very Large Scale DNA Databases with Associative Search Capability. In: Jonoska, N., Seeman, N.C. (eds.) DNA 2001. LNCS, vol. 2340, pp. 231–247. Springer, Heidelberg (2002) CrossRef Rozenberg, G., Spaink, H.: DNA computing by blocking. Theoretical Computer Science 292, 653–665 (2003) CrossRef Sager, J., Stefanovic, D.: Designing Nucleotide Sequences for Computation: A Survey of Constraints. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 275–289. Springer, Heidelberg (2006) CrossRef Sakamoto, K., et al.: State transitions by molecules. Biosystems 52, 81–91 (1999) CrossRef Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 315(5805), 1585–1588 (2006) CrossRef Shortreed, M.R., et al.: A thermodynamic approach to designing structure-free combinatorial DNA word sets. Nucleic Acids Research 33(15), 4965–4977 (2005) CrossRef Van den Bussche, J., Van Gucht, D., Vansummeren, S.: A crash course in database queries. In: Proceedings 26th ACM Symposium on Principles of Database Systems, pp. 143–154. ACM Press (2007) Yamamoto, M., Kita, Y., Kashiwamura, S., Kameda, A., Ohuchi, A.: Development of DNA Relational Database and Data Manipulation Experiments. In: Mao, C., Yokomori, T. (eds.) DNA12. LNCS, vol. 4287, pp. 418–427. Springer, Heidelberg (2006) CrossRef | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| local.relation.ispartofseriesnr | 6479 | - |
| dc.bibliographicCitation.oldjcat | C2 | - |
| dc.identifier.doi | 10.1007/978-3-642-28067-2_2 | - |
| local.bibliographicCitation.btitle | Proceedings of Algebraic and Numeric Biology 2010 | - |
| item.fulltext | With Fulltext | - |
| item.contributor | GILLIS, Joris | - |
| item.contributor | VAN DEN BUSSCHE, Jan | - |
| item.fullcitation | GILLIS, Joris & VAN DEN BUSSCHE, Jan (2012) A Formal Model for Databases in DNA. In: Horimoto, Katsuhisa; Nakatsui, Masahiko; Popov, Nicolaj (Ed.). Proceedings of Algebraic and Numeric Biology 2010, Springer-Verlag, p.18-37.. | - |
| item.accessRights | Closed Access | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| hagenberg.pdf | Non Peer-reviewed author version | 510.2 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.