Graph-theoretic formalization of hybridization in DNA sticker complexes

作     者：Brijder, Robert Gillis, Joris J. M. Van den Bussche, Jan 

作者机构：Hasselt Univ Diepenbeek Belgium Transnat Univ Limburg Diepenbeek Belgium 

出 版 物：《NATURAL COMPUTING》 

年 卷 期：2013年第12卷第2期

页      面：223-234页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：DNA Hybridization Graph-theory Complexity 

摘      要：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.