DNA labelled graphs with DNA computing

作     者：WANG ShiYing YUAN Jun LIN ShangWei 

作者机构：School of Mathematical SciencesShanxi UniversityTaiyuan 030006China 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2008年第51卷第3期

页      面：437-452页

核心收录：

学科分类：0710[理学-生物学] 071010[理学-生物化学与分子生物学] 081704[工学-应用化学] 07[理学] 08[工学] 0817[工学-化学工程与技术] 0701[理学-数学] 

基　　金：the National Natural Science Foundation of China (Grant No. 10471081) 

主　　题：DNA labelled graphs DNA computing directed line-graphs 05C28 

摘      要：Let k ? 2, 1 ? i ? k and α ? 1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost nucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be (k, i; α)-labelled if it is possible to assign a label (l 1(x), ..., l k (x)) to each point x of D such that l j (x) ? {0, ..., α ? 1} for any j ? {1, ..., k} and (x, y) ? E(D) if and only if (l k?i+1(x), ..., l k (x)) = (l 1(y), ..., l i (y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is (k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is (2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a (2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a (2i, i; 4)-labelled directed graph.