Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/16430
Title: Graph-Theoretic Formalization of Hybridization in DNA Sticker Complexes
Authors: BRIJDER, Robert 
GILLIS, Joris 
VAN DEN BUSSCHE, Jan 
Issue Date: 2013
Source: Natural Computing, 12 (2), p. 223-234
Abstract: Sticker complexes are a formal graph-based data model for a restricted class of DNA complexes, motivated by potential applications to databases. This data model allows for a purely declarative definition of hybridization. We introduce the notion of terminating hybridization, which intuitively means that only a finite number of different products can be generated. We characterize this notion in purely graph-theoretic terms. Under a finite alphabet, each product is shown to be of polynomial size. Yet, terminating hybridization can still produce results of exponential size, in that there may be exponentially many different (nonisomorphic) finished products. We indicate a class of complexes where hybridization is guaranteed to be polynomially bounded.
Keywords: DNA; hybridization; graph-theory; complexity
Document URI: http://hdl.handle.net/1942/16430
ISSN: 1567-7818
e-ISSN: 1572-9796
DOI: 10.1007/s11047-013-9361-1
ISI #: 000319433600009
Category: A1
Type: Journal Contribution
Validations: ecoom 2014
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
paper.pdf
  Restricted Access
Article227.74 kBAdobe PDFView/Open    Request a copy
Show full item record

SCOPUSTM   
Citations

1
checked on Sep 3, 2020

Page view(s)

82
checked on May 28, 2022

Download(s)

76
checked on May 28, 2022

Google ScholarTM

Check

Altmetric


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