DNA标号图和DNA计算

设$k\geq 2, 1\leq i \leq k$ 和 $\alpha \geq 1$是3个整数. 对任意一个由长为$k$的寡聚核苷酸组成的多重集, DNA标号图定义如下: 该多重集中的每个寡聚核苷酸作为一个顶点; 若一个顶点右端$i$个核苷酸与另一个顶点左端$i$个核苷酸相同, 则前一顶点控制后一顶点. 称有向图$D$是可$(k,i;\alpha)$标号的, 如果对$D$中的每个顶点$x$, 可设计一个$k$长的标号$(l_{1}(x),\ldots ,l_{k}(x)),$使得 对每一个$j\in \{1,\ldots,k\}$, $l_j(x)\in \{0,\ldots,\alpha-1\}$, 并且$(x,y)$是$D$中的一条弧当且仅当 $(l_{k-i+1}(x),\ldots,l_k(x))=(l_1(y),\ldots,l_i(y)).$ 由生物背景, 对一个有向图,若存在两个整数$k$和$i$, 使得它是可$(k,i;4)$标号的, 则它就是一个DNA标号图. 系统地研究了DNA标号图. 首先, 给出了它和一些已有图类之间的关系. 接着, 证明了对任意的DNA标号图,都存在一个正整数$i$, 使得它是可 $(2i,i;4)$标号的,这有利于DNA标号图的存储和操作. 此外, 还确定了最小的$i$, 并设计了一个多项式时间的算法对给定的DNA标号图进行$(2i,i;4)$标号. 最后, 在一个有$(2i,i;4)$标号的有向图上, 设计了一个DNA算法寻找给定两点间的所有路.