摘要：设k≥2,1≤i≤k和α≥1是3个整数.对任意一个由长为k的寡聚核苷酸组成的多重集,DNA标号图定义如下:该多重集中的每个寡聚核苷酸作为一个顶点;若一个顶点右端i个核苷酸与另一个顶点左端i个核苷酸相同,则前一顶点控制后一顶点.称有向图D是可(k,i;α)标号的,如果对D中的每个顶点x,可设计一个k长的标号(l_1(x),…,l_k(x)),使得对每一个j∈{1,…,k),l_j(x)∈{0,…,α-1},并且(x,y)是D中的一条弧当且仅当(l_(k-i+1)(x),…,l_k(x))=(l_1(y),…,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算法寻找给定两点间的所有路.