Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13016
Full 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.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 | Open Access | - |
item.contributor | GILLIS, Joris | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fulltext | With Fulltext | - |
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 |
SCOPUSTM
Citations
4
checked on Sep 3, 2020
Page view(s)
56
checked on Sep 5, 2022
Download(s)
106
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.