一種CCA-層次聚類的基因聚類算法

摘? 要：針對基因芯片技術帶來的海量基因表達數據，為了充分挖掘其蘊含的生物信息和潛在的生物機制，提出一種基于CCA-層次聚類的基因聚類算法（CCA-Hc）。該算法在層次聚類的基礎上引入典型相關分析，優化相似性矩陣計算方法。首先，利用典型相關分析方法結合基因的多個特征信息進行基因相關性度量，得到基因相似性矩陣。然后將該相似性矩陣作為層次聚類的鄰近矩陣進行凝聚層次聚類。在Oryza sativa L.（水稻）的基因表達數據集上進行CCA-Hc聚類效果測試實驗，結果表明，與采用歐式距離的傳統層次聚類算法（EUC-Hc）相比，CCA-Hc的內部穩定性指標和生物功能性指標均優于EUC-Hc，具有更佳的魯棒性和聚類準確性，更有利于去發現基因間的共表達關系。

關鍵詞：基因表達數據；聚類算法；典型相關分析；層次聚類

DOI：10.15938/j.jhust.2023.05.011

中圖分類號： TP391

文獻標志碼： A

文章編號： 1007-2683（2023）05-0085-06

A Gene Clustering Algorithm Based on the CCA-Hierarchical Clustering

LIN Qianmin

（School of Electrical Engineering and Automation， Xiamen University of Technology， Xiamen 361024， China）

Abstract：Aiming at the massive gene expression data brought by gene chip technology， in order to fully mine the biological information and potential biological mechanisms contained in it， this paper proposes a gene clustering algorithm based on CCA-hierarchical clustering （CCA-Hc）. The algorithm introduces canonical correlation analysis on the basis of hierarchical clustering， and optimizes the calculation method of similarity matrix. First， the canonical correlation analysis method is used to measure the gene correlation by combining the multiple feature information of the gene， and the gene similarity matrix is obtained. Then the similarity matrix is used as the neighbor matrix of hierarchical clustering for agglomerative hierarchical clustering. The CCA-Hc clustering effect test experiment was performed on the gene expression dataset of Oryza sativa L. （rice）. The results show that， compared with the traditional hierarchical clustering algorithm using Euclidean distance （EUC-Hc）， CCA-Hc is superior to EUC-Hc in both internal stability index and biological functional index， and has better robustness and clustering accuracy. It is more conducive to discovering the co-expression relationship between genes.

Keywords：gene expression data; clustering algorithm; canonical correlation analysis; hierarchical clustering

收稿日期： 2022-06-08

基金項目： 福建省科技廳引導性項目（2019H0039）；福建省中青年教師教育科研項目（JAT210341）.

通信作者：

林倩閩（1992—），女，碩士，助理實驗師，E-mail：1023447133@qq.com.

0? 引? 言

隨著高通量測序技術的不斷快速發展，出現越來越多復雜度高、數據量大的生物數據。不同測序技術可以得到不同水平的生物數據，如通過基因組測序得到DNA水平的生物數據，轉錄組測序得到RNA水平的生物數據?；虮磉_數據是通過DNA微陣列技術（又稱為基因芯片技術）檢測得到，是不同細胞在不同條件下的基因動態表達水平［1］?；蚴菙y帶遺傳物質的DNA片段，在不同細胞中會有不同的表達方向［2］，從而可以控制不同的性狀。為此基因表達數據蘊含著豐富且重要的生物機制，具有很大的研究價值。

在基因表達數據分析中，聚類分析方法被廣大研究者選用，用以發現具有相似表達行為的基因集，基因間的共表達、共調控關系等，對于推斷未知的基因功能及在疾病診斷方面具有重要意義［2］。目前基因聚類算法根據聚類對象可以分為基于基因、基于樣本聚類以及基于基因樣本的雙聚類［3-4］。根據聚類方式的不同，又可以分為以K-means算法［5］、K-MEDOIDS［6］為代表的基于分區的聚類算法，以BIRCH算法［7］、CURE算法［8］為代表的基于層次的聚類算法，以DBSCAN算法［9］、OPTICS算法［10］為代表的基于密度的聚類算法和以CLIQUE算法［11］為代表的基于網格的聚類算法。

在對基因表達數據進行聚類分析時，主要是度量基因之間的相關性，把相關性程度高的基因聚在一起。很多基因聚類研究中把皮爾森相關系數、歐式距離、曼哈頓距離等作為相關性程度的度量方式［12］。這些度量方式是基于基因的整體表達水平進行的，即一個基因只由一個一維的數據矩陣表示。而在實際的的測序過程中，往往會在不同的細胞周期進行實驗測量基因的表達水平，使得一個基因會有多組數據，每組數據代表該基因的一個特征。大部分的研究中采用求和的方式把基因多個特征的數據進行累加，進而分析基因之間的相關性。這種方法存在的問題是忽略了基因各個特征對表達水平的影響，從而對聚類結果造成影響。

為了解決上述問題，本文把典型相關分析（Canonical Correlation Analysis， CCA）引入到層次聚類中來，搭建出基于CCA-層次聚類的基因聚類算法（CCA-Hc）。典型相關分析是一種計算變量之間相關性的統計學分析方法，能結合變量的多個特征，得到變量的整體相關性［13］。利用典型相關分析度量基因之間的相關性，能充分考慮基因的多個特征信息，使得聚類結果中的基因集相似性程度更高。同時采用凝聚層次聚類，可以從聚類樹狀圖中直觀地分析聚類結果，從而整體上提高聚類效果。最后用GEO數據庫上的基因數據集來驗證CCA-Hc算法的有效性。

1? CCA-Hc算法設計

1.1? 典型相關分析

給定基因微陣列數據矩陣An×m=（G，T），n表示基因個數，m表示條件的種類數。每個基因可以看成是一個變量，使用典型相關分析方法分析變量相關性時，假設變量X有p個特征，變量Y有q個特征，p≤q，每個特征均對應m個不同條件的數據，則

X=［x1，…，xp］T（1）

Y=［y1，…，yq］T（2）

變量X的數據矩陣為

x11x12x13…x1m

x21x22x23…x2m

x31x32x33…x3m

xp1xp2xp3…xpm

變量Y的數據矩陣為

y11y12y13…y1m

y21y22y23…y2m

y31y32y33…y3m

yq1yq2yq3…yqm

變量X和變量Y的協方差矩陣為

∑=Cov（X，Y）=Var（X）Cov（X，Y）

Cov（Y，X）Var（Y）=∑11∑12∑21∑22（3）

變量X和變量Y的線性表達式記為U、V，表示為：

U=a1x1+a2x2+…+apxp=aTX（4）

V=b1y1+b2y2+…+bqyq=bTY（5）

變量X和變量Y進行典型相關性分析時，可用這兩個變量的線性表達式U、V之間相關系數的最大值來度量變量之間的相關性程度，即

maxa，bcorr（U，V）=aT∑12b（aT∑11a×bT∑22b）1/2（6）

在求解上述最值表達式時，運用拉格朗日數乘法求解瑞利熵矩陣（∑-111∑12∑-122∑21）得到p個特征值，記為λ1，λ2…λp。這p個特征值即變量X和變量Y之間的典型相關系數。每一個相關系數再應用卡方檢驗進行顯著性檢驗，得到p個卡方檢驗p-value值，記為p1，p2…pp。為了更好地表示變量之間的典型相關程度，引入一個關于典型相關系數和p-value值的權重函數W來表示，定義為：

W=∑pi=1λiI（logPi）∑pi=1I（logPi）（7）

其中I（logPi）=0P>0.05-logPP≤0.05

這樣每兩個變量之間就能得到一個w值來度量它們的相關性程度。對基因表達數據的n個基因進行如上方法的典型相關分析后，最終得到一個n×n的相似性矩陣。

1.2? 層次聚類

目前常用的聚類算法有基于分區、基于層次、基于密度和基于網絡4種類型［2］，其中基于層次聚類的算法因原理通俗易懂、結果直觀且精度高等優點而被廣泛使用［14］。層次聚類分為自下而上的凝聚聚類和自上而下的分裂聚類兩種［15］，其中凝聚層次聚類運用最為廣泛，同時凝聚層次聚類在無預先定義類別數的分類中具有明顯優勢［16］。故本文采用的是凝聚層次聚類，可以用樹狀圖和嵌套簇圖來表示，例如圖1所示。

下面介紹凝聚層次聚類的聚類過程：

步驟1：視每一個數據點（如基因變量）為一個集群；

步驟2：計算鄰近矩陣，把類間距離最接近的兩個集群進行合并；

步驟3：重復步驟2，直到所有數據點合并完成。

步驟2中的類間距離即兩個集群之間的距離，傳統的層次聚類類間距離計算方法有如下幾種［17］：

1）兩個集群中距離最近的兩個樣本距離；

2）兩個集群中距離最遠的兩個樣本距離；

3）兩個集群中所有樣本之間的距離再求平均值；

完成所有聚類步驟后會生產一個樹狀圖（又叫聚類樹）。采用不同的變量相關性程度度量方式和不同的類間距離計算方法都將對聚類結果造成影響。

1.3? CCA-HC算法

傳統的層次聚類算法其計算復雜度為O（n3）， 由于在聚類過程中需要不斷地重復計算類間距離、不斷地更新鄰近矩陣，從而消耗大量的時間與資源［18］。對于數據量龐大的基因微陣列數據，迫切需要對算法進行優化，降低復雜度。本文提出了一種基于CCA和層次聚類的基因聚類算法（CCA-HC），優化相似性矩陣計算方法，把典型相關分析的輸出作為層次聚類的輸入，即把典型相關分析得到的相似性矩陣作為層次聚類的鄰近矩陣。

CCA-HC在度量基因相關性程度時采用典型相關分析的方法，在層次聚類方式上選擇自下而上的凝聚層次聚類。CCA-HC充分利用了典型相關分析和層次聚類的優點，能夠結合基因的多個特征來量化基因之間的相關性，使得聚類結果中的基因集相似性程度更高，也能自主選擇集群數目以得到更佳的聚類效果［18］。

2? 實驗與結果分析

2.1? 實驗數據

為了評價章節一中提出算法的聚類效果，在GEO數據庫上下載Oryza sativa L.（水稻）的基因表達數據集，得到的原始數據集共有45063個基因，樣本數為41。由于原始數據集基因數龐大，對其計算分析時不論在存儲空間還是計算程序上都提出了較高的要求，為此進行適當的數據預處理顯得尤為重要。

本文在數據預處理方面開展的主要工作有：把基因名未知的數據剔除；過濾掉樣本表達量過低的基因；采用log2的對數函數對原始數據進行標準化處理等。經過如上處理后得到4564×41的數據矩陣，用于后續的實驗分析。預處理后的實驗數據集統計情況如表1所示。

1.5? 評價標準

基因表達數據的聚類效果可以從聚類結果中同一集群的相關性程度以及聚類算法的穩定性等方面進行評價，用生物功能性指標和內部穩定性指標來描述。

1.生物功能性指標

生物同源性指標（biological homogeneity index， BHI）是用來評估聚類集群在生物功能意義上的同源性程度［19］。在基因本體（gene ontology， GO）數據庫上下載水稻的基因功能類數據，可以得知每個水稻基因所對應的生物組織功能，用來分析同一聚類集群中的基因在功能上的相關性。BHI公式計算如下：

BHI（K，B）=1K∑Kk=11nk（nk-1）∑i≠j∈CkI（B（i）=B（j））（8）

式中：C為聚類結果中的任一集群；B為基因功能類集合，當基因i和基因j所對應的功能類存在交集，則I（B（i）=B（j））=1，否則為0。最終得到的BHI是介于0～1的值，BHI值越大，表示基因聚類集群的生物功能相關性越大，聚類效果更佳［19］。

2.內部穩定性指標

內部穩定性指標在于評價聚類算法的魯棒性，通過改變基因微陣列數據的某幾列進行聚類，進而比較基于不同數據的聚類結果。優值系數（figure of merit， FOM）是內部穩定性指標中的一種，表示數據列改變后基因之間的平均群內方差［20］。FOM公式計算如下：

FOM（l，K）=1N∑Kk=1∑i∈Ck（l）dist（xi，l，Ck（l））（9）

式中：FOM的取值范圍是0到無窮大，FOM值越小表示該聚類算法的穩定性越好［20］。

2.3? 結果與分析

為驗證CCA-Hc的聚類效果，對比采用歐式距離的傳統層次聚類算法（EUC-Hc），運用相同數據集進行實驗。為了獲得更加準確的聚類效果，本實驗設置不同的聚類集群參數，確定聚類集群數目K分別為2、4、6、7、9、11、12這7組實驗，并通過BHI和FOM指標對這7組實驗的聚類結果進行評估，BHI和FOM指標值分別見表2和表3。

表2中的差異率指的是CCA-Hc的BHI指標比EUC-Hc的BHI指標相差的百分比，同理可以計算表3中的差異率。

根據表2和表3的實驗指標數據發現，對于7組不同的聚類集群數目實驗，本文提出的CCA-Hc的BHI指標均高于EUC-Hc，FOM指標均低于EUC-Hc，這表明CCA-Hc的魯棒性更好，聚類結果中同一集群的基因相關性更大，聚類效果更加顯著。同時還發現，集群數目對CCA-Hc的影響較小，K選不同的值，BHI指標值穩定在0.463～0.467之間，FOM指標值穩定在2.695～2.697之間，而集群數目對EUC-Hc算法的影響相對比較明顯。

圖2為CCA-Hc在Oryza sativa L.數據集的聚類樹狀圖，可以自行在所需的層級對樹狀圖進行“剪枝”操作以獲得合適的聚類效果［21］。

3? 結? 論

本文為了充分有效地挖掘基因表達數據所蘊含的生物機制，提出一種基于CCA-層次聚類的基因聚類算法（CCA-Hc）。把典型相關分析方法引入到凝聚層次聚類中來進行多特征基因的聚類分析，成為本文的創新之處。該算法利用典型相關分析方法度量基因之間的相關性程度，能夠充分考慮基因的多個特征信息。同時采用凝聚層次聚類可自主選擇聚類集群數目，直觀顯示聚類結果。

基于Oryza sativa L.（水稻）的基因表達數據集，本文對比了CCA-Hc和EUC-Hc的聚類效果，使用BHI和FOM兩個評價指標進行衡量，結果表明CCA-Hc的魯棒性和聚類準確性均更好，更有利于去探索基因表達數據潛在的生物機制。

參 考 文 獻：

［1］? 歐陽玉梅. 基因表達數據聚類分析技術及其軟件工具［J］. 生物信息學， 2010， 8（2）： 104.

OUYANG Yumei. Gene Expression Data Cluster Analysis Technology and Software Tools［J］. Bioinformatics， 2010， 8（2）： 104.

［2］? 高華成. 基于數據降維框架的基因聚類算法［D］. 南京：南京郵電大學， 2021.

［3］? 姚登舉， 詹曉娟， 張曉晶. 一種加權K-均值基因聚類算法［J］. 哈爾濱理工大學學報， 2017， 22（2）： 112.

YAO Dengju， ZHAN Xiaojuan， ZHANG Xiaojing. A Weighted K-Means Gene Clustering Algorithm［J］. Journal of Harbin University of Science and Technology， 2017， 22（2）： 112.

［4］? 方匡南， 陳遠星， 張慶昭， 等. 雙向聚類方法綜述［J］. 數理統計與管理， 2020， 39（1）：22.

FANG Kuangnan， CHEN Yuanxing， ZHANG Qingzhao， et al. Review of Bidirectional Clustering Methods［J］. Journal of Applied Statistics and Management， 2020， 39（1）：22.

［5］? 吳明陽， 張芮， 岳彩旭， 等. 應用K-means聚類算法劃分曲面及實驗驗證［J］. 哈爾濱理工大學學報， 2017（1）：54.

WU Mingyang， ZHANG Rui， YUE Caixu， et al. Application of K-means Clustering Algorithm for Surface Division and Experimental Verification［J］. Journal of Harbin University of Science and Technology， 2017（1）：54.

［6］? LACKO D， HUYSMANS T， VLEUGELS J， et al. Product Sizing with 3D Anthropometry and K-medoids Clustering［J］. Computer-Aided Design， 2017： S0010448517301173.

［7］? ZHANG T， RAMAKRISHNAN R，LIVNY M. BIRCH： A New Data Clustering Algorithm and Its Applications［J］. Data Mining and Knowledge Discovery， 1997， 1（2）：141.

［8］? FUSHIMI T， MORI R. High-Speed Clustering of Regional Photos Using Representative Photos of Different Regions［C］. 2018 IEEE/WIC/ACM International Conference on Web Intelligence （WI）， IEEE， 2018： 520.

［9］? Al-MAMORY S O， KAMIL I S. A New Density Based Sampling to Enhance DBSCAN Clustering Algorithm［J］. Journal of Computer Science， 2019， 32（4）： 315.

［10］ANKERST M， BREUNIG M M， KRIEGEL H P， et al. OPTICS： Ordering Points to Identify the Clustering Structure［C］// SIGMOD 1999， Proceedings ACM SIGMOD International Conference on Management of Data， June 1-3， 1999， Philadelphia， Pennsylvania， USA. ACM， 1999： 2008， 99.

［11］王飛， 王國胤， 李智星， 等. 一種基于網格的密度峰值聚類算法［J］.小型微型計算機系統， 2017（5）： 1034.

WANG Fei， WANG Guoyin， LI Zhixing， et al. A Grid-based Density Peak Clustering Algorithm［J］. Journal of Chinese Computer Systems， 2017（5）： 1034.

［12］YAO J， CHANG C， SALMI M L， et al. Genome-scale Clusteranalysis of Replicated Microarrays Using Shrinkage Correlation Coefficient［J］. BMC Bioinformatics， 2008， 9： 288.

［13］HONG S， CHEN X， JIN L， et al. Canonical Correlation Analysis for RNA-seq Co-expression Networks［J］. Nucleic Acids Res， 2013， 41（8）： e95.

［14］萬靜， 鄭龍君， 何云斌， 等. 高維數據的高密度子空間聚類算法［J］. 哈爾濱理工大學學報， 2020， 25（4）： 84.

WAN Jing， ZHENG Longjun， HE Yunbin， et al. High-Density Subspace Clustering Algorithm for High-Dimensional Data［J］. Journal of Harbin University of Science and Technology， 2020， 25（4）： 84.

［15］劉昊. 基于聚類算法的生物分析軟件的設計與實現［D］. 上海：復旦大學， 2013.

［16］喬錦榮， 原新鵬， 梁旭東， 等. 凝聚層次聚類方法在降水預報評估中的應用［J］. 干旱氣象， 2022，40（4）： 690.

QIAO Jinrong， YUAN Xinpeng， LIANG Xudong， et al. Application of Agglomerative Hierarchical Clustering Method in Precipitation Forecast Evaluation［J］. Arid Meteorology， 2022，40（4）： 690.

［17］JASKOWIAK P A， CAMPELLO R J， COSTA I G. On the Selection of Appropriate Distances for Gene Expression Data Clustering［J］. BMC Bioinformatics， 2014， 15（2）： 1.

［18］季姜帥，裴頌文. 面向異質基因數據的智能層次聚類算法研究［J］. 小型微型計算機系統， 2021， 43（9）：1808.

JI Jiangshuai， PEI Songwen. Research on Intelligent Hierarchical Clustering Algorithm for Heterogeneous Genetic Data［J］. Journal of Chinese Computer Systems， 2021， 43（9）：1808.

［19］DATTA S， DATTA S. Methods for Evaluating Clustering Algorithms for Gene Expression Data Using a Reference Set of Functional Classes［J］. BMC Bioinformatics， 2006， 7（1）： 1.

［20］DATTA S. Comparisons and Validation of Statistical Clustering Techniques for Microarray Gene Expression Data［J］. Bioinformatics， 2003， 19（4）： 459.

［21］HULOT A，CHIQUET J， JAFFRZIC F， et al. Fast Tree Aggregation for Consensus Hierarchical Clustering［J］. BMC Bioinformatics， 2020， 21（1）： 12.

（編輯：溫澤宇）