DNA labelled graphs with DNA computing  

作　　者：WANG ShiYing YUAN Jun LIN ShangWei 

机构地区：[1]School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China

出　　处：《Science China Mathematics》2008年第3期437-452,共16页中国科学：数学（英文版）

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

摘　　要：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.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 uucleotides 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₁（x）,..., l_k（x））to each point x of D such that l_j（x）∈{0,...,a-1}for any j∈{1,...,k}and（x,y）∈E（D）if and only if（l_k-i+1（x）,..., l_k（x））=（l₁（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.

关 键 词：DNA labelled graphs DNA computing directed line-graphs 05C28 

分 类 号：Q523[生物学—生物化学]