基于图形表示的独特码码型序列比较方法*

刘伟华 谢 鑫

（海军工程大学核科学技术学院 武汉 430032）

1 引言

由于意外事故而造成破坏导致引发重大灾难性后果的系统被称为要害系统。独特码[1]是针对要害系统极端的安全性要求设计而成的增强安全系统的解保密码，它是一组在异常环境下被偶然产生概率极小的特殊序列，由事件、码长、码型这三个基本要素构成。独特码在同时使用时存在相互干扰的潜在风险，所以需要对独特码码对之间的相似性进行分析，从而选出相互之间相似性较小的码对以降低在使用过程中出现问题的可能性。

1983 年 Hamori和 Ruskin[2]开发了一种基于计算机图形学的新方法来替代传统的基于字母序列的核苷酸序列表示方法，该方法将核苷酸序列的信息映射成便于显示和操作的三维空间函数。1986年Gates[3]提出了DNA序列的二维图形表示，其他的研究人员像是 Nandy、Leong和 Morgenthaler[4～7]等也相继提出了许多不同的图形表示方法。他们的方法是在坐标系中选择四个基本方向来表示DNA序列中四个碱基的含量。2001年Randic和Vracko[8]等还在图形表示的基础上，将DNA序列转化为矩阵等数学表示，进一步用矩阵不变量来研究DNA序列的相似性，取得了不错的效果，证明了该思路的可行性。

独特码的序列相似性分析一般是通过序列直接比较来实现的。对于二元码来说，序列是由两种事件（A和B）所组成的字符串，单纯地进行序列比对难以获取有用的信息。独特码码型序列在结构上与核苷酸序列存在相似之处，所以考虑将图形表示的的思想应用于独特码领域。本文提出基于图形表示的独特码码型序列比较方法，通过挖掘对应图形隐含的信息来比较码型序列的相似性。

2 序列向图形的转换

2.1 基本思想

基于图形表示的独特码码型比较方法通过将码型序列转换为图形表示，然后将图形映射为矩阵，再通过比较矩阵不变量的方式来比较独特码码型序列的相似性。对于二元码来说，码型序列只由两种码元组成，若是直接将其转换为对应的图形表示，一来与独特码的二维迷宫映射图[9]重复，二来其蕴含的信息较少，不便于后续的矩阵构建和不变量提取。现考虑利用连续独特码之间的变化方向来作为转换前的信息。变化方向共有四种，分别是AA、AB、BA、BB。这样一来，信息的类别从两种变成了四种，扩大了一倍，使得可以提取的信息变得更加丰富。需要强调的是，虽然码元变化方向与码元对的表示方式类似，但是代表的含义却不尽相同，这一点需要注意区分。

2.2 转换方法

把独特码码型序列表示成位于二维坐标轴上的图形，因为独特码的码元对具有均衡性的特点，即每个码元对（AA、AB、BA、BB）的数量大致相同，若是用四个坐标方向分别代表四种码元变化方向，就很容易造成对应图形的交叠和混乱，难以进行有效地区分和比较。为了在空间中便于观察，将第一象限中的整个角度进行三等分，产生了以原点为端点，0°、30°、60°、90°四条射线为坐标轴的新坐标系。新坐标系的四个坐标轴方向依次代表AA、AB、BA、BB这四种变化方向。四个坐标轴之间不存在互为反向的现象，所以避免了因为码元对的均衡性带来的不便和干扰。同时也因为变化方向的计量都是非负数，所以不需要考虑负方向轴的问题，整个图形都是位于第一象限。在新建立的坐标系上，按照每次变化方向增加一次就沿相应坐标轴前进一个单位的方式将独特码码型序列映射为二维空间中的一个个坐标点，然后将坐标点依次连接起来，形成码型序列的对应图形表示。需要说明的是，虽然将码型序列按照新坐标轴的方式映射成了对应图形，但是在后续计算的时候还是按照二维笛卡尔坐标系的方式进行。

3 图形向矩阵的转换

3.1 图形的特征矩阵

为了更直观地观察码型序列，将码型序列转换为图形表示，而为了更方便地提取码型序列的相关信息，将码序列的图形表示映射为对应矩阵。记构建的二维图形中第i点和第j点的坐标分别为(xi，yi)和(xj，yj)。图形表示的特征矩阵常见的有三种，分别是E矩阵、M/M矩阵、L/L矩阵[10]，下面分别进行介绍：

1）E矩阵：其元素是曲线上两个坐标点之间的欧氏距离。其公式为

2）M/M矩阵：其元素是曲线上两个坐标点的欧氏距离与它们之间存在的单位线段之比。

其公式为

3）L/L矩阵：其元素是曲线上两个坐标点的欧氏距离与它们之间的图论距离（曲线上两点之间的线段长度之和）之比。

3.2 矩阵不变量

序列比较涉及到搜索序列之间的最佳对应关系，以及在不知道字符串元素之间的确切对应关系时，使用距离函数度量相似性或不相似性等问题。序列之间的差异可能由于码元的替换而产生，寻找序列之间的最佳对应关系需要考虑排列和匹配。如果用矩阵来表示序列，所有这些情况都可以避免。通过使用一组矩阵不变量来表征矩阵，可以很容易地对矩阵进行比较。

常见的矩阵不变量包括矩阵的主特征值、最大行和、最小行和以及平均行和等。主特征值是特征值中模最大的特征值。在所有特征值中，矩阵的主特征值往往起着特殊的作用。矩阵各行元素之和当中最大的被称为最大行和，最小的被称为最小行和，最大行和以及最小行和分别表示矩阵的主要特征值的上下界。在矩阵的阶数较大难以进行特征值的有效计算时，可以通过最大行和以及最小行和来确定主特征值的取值范围。各行元素之和的平均值被称为平均行和，其优势在于可以很容易地计算出来。当矩阵的单个矩阵元素相差不大时，平均行和可以用来大致估计主特征值的取值。两个码型序列的矩阵不变量的比较一般是通过向量的形式进行的，常见的比较方式包括比较欧氏距离和夹角的余弦值这两种：

1）比较两个向量之间的欧氏距离，两个序列的相似程度与两个向量之间的欧氏距离成负相关。

2）比较两个向量之间夹角的余弦值，两个序列的相似程度与两个向量之间夹角的余弦值成正相关。

4 相似性比较

4.1 聚类分组

聚类是把一个数据对象的集合划分成几个子集，使子集内对象相似而子集间对象不相似的过程[11]。聚合层次聚类[12]是一种常用的聚类方法，它先将每个数据视为一个个单独的子集，然后按照距离度量选择距离最近的两个或多个子集进行合并来形成新的子集，然后重复合并的过程直到最后只剩下一个子集。采用聚合层次聚类的方式将码长为24位的独特码码集分成4组，再分别从每组中随机选出2类不同码型的独特码作为代表，将其依次进行标号，对应的序号、组别及码型如表1所示。

表1 聚类后产生的各分组代表码型

4.2 方法实现

根据前面所讲的方式，将独特码码型序列映射到二维空间的第一象限中。以码型1作为代表，其对应的图形如图1所示。

图1 码型1的对应图形

再根据码型序列对应的图形，构建特征矩阵，本文选用的是L/L矩阵。其主对角线元素为0，所有元素小于等于1。其公式为

其中xi、xj、yi、yj为坐标点的对应值，e(k，k+1)代表欧式距离。

特征矩阵构建完成之后，从中提取主特征值和平均行和作为特征不变量并根据这两个数值形成特征向量。各码型序列的特征不变量如表2所示。

表2 各码型序列的特征不变量

表3 各码型序列的欧式距离比较矩阵

因为独特码本身就是按照严格的特性标准筛选出来的，彼此之间在性质上相差并不大，所以不能选用比较夹角的余弦值这种较为粗略的方式。在此处选用比较欧氏距离的方式，这样的话即便很微小的差异也可以进行比较。两个向量X(x1，x2，…，xi)和Y(y1，y2，…，yi)）的欧式距离的计算公式如下：

各码型序列之间的欧式距离比较矩阵如表3所示。

通过表3中的矩阵可以发现，原来隶属于相同码组的独特码码型序列之间的相似性比较大，而隶属于不同码组的码型序列之间的相似性比较小。重复上述步骤进行多次试验，所得结论相同。基于图形表示的独特码码型序列比较方法能够较好地以定量的方式对独特码码型序列的相似性进行比较和分析。

5 结语

相比于传统的直接比较码型序列的方法，基于图形的相似性比较方法利用数形结合的思想，将不易观察的原始码型序列转换成易于比较的数值序列。选用数值序列的优点在于可以根据实际情况选择合适的不变量来调整数值序列的长度。基于图形的相似性比较方法从独特码码型序列的实际情况出发，在考虑了独特码码元均衡性所带来的不便的情况下，为独特码码型序列相似性的比较提供了一种可视化的检测手段。