基于圖形表示的獨特碼碼型序列比較方法*

劉偉華 謝 鑫

（海軍工程大學核科學技術學院 武漢 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 結語

相比于傳統的直接比較碼型序列的方法，基于圖形的相似性比較方法利用數形結合的思想，將不易觀察的原始碼型序列轉換成易于比較的數值序列。選用數值序列的優點在于可以根據實際情況選擇合適的不變量來調整數值序列的長度。基于圖形的相似性比較方法從獨特碼碼型序列的實際情況出發，在考慮了獨特碼碼元均衡性所帶來的不便的情況下，為獨特碼碼型序列相似性的比較提供了一種可視化的檢測手段。