·186 智能系统学报 第6卷 部分字主要是针对DNA序列的错误匹配提出 D(u)={0,2,3,4,5,7},D()={01,3,5,7}于是 的（见图1）.，把此位置的碱基看成是未知的，即没 D(uVv)=D(u)UD(v)={0,1,2,3,4,5,7}, 有定义的位置，据定义1，这样的位置称为洞（而对 D(uA)=D(u)nD()={0,3,5,7},从而uVv= 于对应位置碱基相同的情况则不予考虑).因此，可 ATTCAToC,uAv=AooCoToC. 以将任意2条等长的DNA序列中相同位置碱基既 由以上定义可以得到如下命题， 不相同也不互补的位置称为洞. 命题1任意两相容的部分字，其最大字的洞 与Watson-Crick Hamming距离是一一对应的，即它 们最大字的洞的个数与Watson-Crick Hamming距离 T C GG T T A C A T T G T C A G 相等 图1发生2处错误匹配的DNA双链 证明设任意两相容的部分字为“、，包含于 Fig.1 DNA sequences with two mistakes u、v的最大字为w,由定义6可得D(0)=D(u)∩ 发生错误匹配的位置一般不能确定是哪个碱基 D(),从而H(w)=D(w)=D(u)∩D(v)=H(u)U 发生了错误匹配 H(v),故1H(w)|=IH(u)I+IH(v)I-IH(u)∩ 定义21设x=x2xy=yy2…y.∈{A,T,C H(v)l,又'(u,v)=IH(u)|+IH(v)I-IH(u)∩ <G}*,xy的Watson-Crick Hamming距离定义为 H()I,故二者相等，结论成立. (,）=, 2 DNA杂交反应与DNA编码优化 「1，x≠y,:≠y 实验结果研究表明14]，2条DNA序列是否杂 式中xy:)= ,i=1,2,…,n,y是指 10,其他 交，不是取决于错误匹配的绝对数目，而是取决于错 在Watson-Cick碱基互补原则下与y:配对的碱基 误匹配的频率（错误匹配所占的比率），为此，引入 定义3[9]设Σ={A,T,C,G,0={A,T}, 穿洞率的定义. ={C,G则显然有o∩1=⑦.U1=.o、 定义8部分字w的穿洞率定义为r()= 定义为2个不同的类，则x和y中对应位置属于 Hole(o,其中Hole(o)表示w中洞的个数. 不同类的分量个数称为Watson-Crick Hamming距 穿洞率的大小与任意2个部分字的杂交情况有 离，记为H'(x,y). 定义4字母表U{o上的完全字。称为部 着密切的联系.研究表明，当(0)≥2时，任意2个 分字w的伴随，如果 部分字即使相应位置剩余所有碱基互补，则它们也 i]=[li],iD(w): 不能杂交.于是得到如下命题. 0, i华D(w)且0≤i≤|wl. 命题2任意两DNA序列xy,Ix|=IyI=n, 为简便起见，用部分字的伴随来代替部分字.例 如，用“部分oAoT字”来代替“部分字的伴随oAoT”. 当H(x,）≥2时，x与y不会发生杂交反应， 定义54任意2个等长的部分字u、v, 证明当(x)≥分且r()≥时，有 D(u)CD(v)且由ieD(u)可得u(i)=v(i),则称u 包含于v,记作uCu. 1(x)l≥2,1Hy)川≥2,1H(x)nH(y）1≤2.由 定义64]任意2个等长的部分字山、v,若存 命题1，H'(x,y)=IH(xAy)1=|H(x)I+ 在部分字0使uCw且vCW,则称u、v是相容的，记 作u↑. 1)1-1)n)1≥受+受-受=受，有以 由定义3~5得到如下定义. 上论述知命题成立 定义7任意2个相容部分字u、v、uVv表示包 含u、v的最小的字，即D(uV)=D(w)UD();uA 当r(o)<2时，任意两等长DNA序列错误匹 v表示包含于u、D的最大的字，即D(u八v)= 配情况如图2所示。 D(u)∩D(w). 例1设u=AoTCAToC,v=AToCoToC,则