基于層次聚類的生物網(wǎng)絡(luò)全局比對算法

田盼盼，陳 璟，2

（1.江南大學 人工智能與計算機學院，江蘇 無錫 214122；2.江南大學 江蘇省模式識別與計算智能工程實驗室，江蘇 無錫 214122）

0 概述

近年來，隨著高通量技術(shù)的發(fā)展，通過實驗方法檢測到蛋白質(zhì)相互作用（Protein-Protein Interaction，PPI）的數(shù)量大幅增加，形成了越來越多的PPI 網(wǎng)絡(luò)。發(fā)現(xiàn)并理解蛋白質(zhì)之間的相互作用，是生物學領(lǐng)域內(nèi)的重要課題之一［1］。對PPI 網(wǎng)絡(luò)的分析能夠增進對生物學過程的理解，不同物種間相互作用組的比對在蛋白質(zhì)功能預測、保守功能成分檢測、物種間知識轉(zhuǎn)移等方面具有重要意義［2］。

網(wǎng)絡(luò)比對按映射關(guān)系可分成局部比對和全局比對。局部比對旨在找到高度保守的小型網(wǎng)絡(luò)區(qū)域，并生成多對多節(jié)點映射，例 如LePrimAlign［3］、LocalAli［4］、Pin-Align［5］。全局比對旨在找到較大的保守區(qū)域并生成一對一的節(jié)點映射，例如Isorank［6］、GRAAL［7］、H-GRAAL［8］、MI-GRAAL［9］、C-GRAAL［10］、L-GRAAL［11］、NETAL［12］、SPINAL［13］、PINALOG［14］、ModuleAlign［15］、PROPER［16］、AligNet［17］、IsoRankN［18］、BEAMS［19］、SMETANA［20］等，其中后3種算法屬于多網(wǎng)絡(luò)比對，其余為2個網(wǎng)絡(luò)的比對。本文著重研究2個網(wǎng)絡(luò)的全局比對。

在現(xiàn)有2 個網(wǎng)絡(luò)的全局比對算法中，IsoRank 算法是先進的全局比對算法，其主要利用類似谷歌頁面排序算法（PageRank）的方法計算節(jié)點相似性，并采用貪心算法進行比對。GRAAL 系列算法利用圖形度標簽相似性作為節(jié)點的拓撲相似度，結(jié)合其他搜索算法比對PPI 網(wǎng)絡(luò)。NETAL 算法基于拓撲和生物相似性構(gòu)建相似性矩陣，利用貪心搜索方法比對網(wǎng)絡(luò)。SPINAL 算法首先基于二分圖構(gòu)建初始相似性矩陣，利用種子-擴展算法并基于迭代交換局部改進比對節(jié)點。PINALOG 算法首先利用聚類算法提取密集模塊，計算模塊間的相似度并通過模塊匹配提取比對的種子集合，并將比對擴展至種子節(jié)點的鄰域。ModuleAlign 算法基于輸入網(wǎng)絡(luò)的層次聚類計算蛋白質(zhì)間的同源性得分，整合了序列信息以及局部和全局網(wǎng)絡(luò)拓撲作為評分方案，通過迭代算法尋找一種在實現(xiàn)較好整體得分的同時最大化保守相互作用數(shù)量的比對方法。PROPER 算法首先根據(jù)序列信息設(shè)置閾值篩選種子集合，然后利用滲透圖匹配（Percolation Graph Matching，PGM）算法［21］擴展種子。AligNet 算法是成對網(wǎng)絡(luò)比對算法，其先將網(wǎng)絡(luò)劃分成多個重疊簇，再進行簇間的局部比對，最后將其組合擴展為全局比對。

上述算法大多從拓撲和生物2 個角度考慮蛋白質(zhì)的相似性，由于PPI 網(wǎng)絡(luò)存在噪聲，僅考慮拓撲特征可能對比對產(chǎn)生誤導，而序列信息的不完全性使得僅考慮生物信息會影響比對的準確性，序列上相似不一定代表功能相似。此外，生物網(wǎng)絡(luò)被觀察到是高度模塊化的［22］，同一個功能模塊中蛋白質(zhì)相互連接密集，不同模塊間蛋白質(zhì)相互連接稀疏［23］，部分算法利用層次聚類［24］、密度聚類［25］等模塊檢測技術(shù)從PPI 網(wǎng)絡(luò)中提取出具有相似功能的蛋白質(zhì)，將功能模塊檢測融入網(wǎng)絡(luò)比對中，更準確地預測蛋白質(zhì)功能，但通常需要借助同源信息。因此，利用較少的額外信息實現(xiàn)良好的拓撲與生物一致性的平衡，是需要進一步研究的問題。

本文基于種子-擴展算法和功能模塊檢測，提出一種生物網(wǎng)絡(luò)全局比對算法JAlign。結(jié)合節(jié)點及其鄰居節(jié)點的拓撲特征和序列信息構(gòu)建目標函數(shù)，利用Jerarca 層次聚類算法［26］劃分功能模塊，并通過匈牙利算法從中提取種子，綜合種子與鄰居節(jié)點的連接關(guān)系、節(jié)點相似性和度，將比對從種子節(jié)點擴展至其鄰居節(jié)點，同時對剩余節(jié)點再次進行加權(quán)二分圖匹配，找到更多匹配節(jié)點，從而實現(xiàn)拓撲和生物一致性的平衡。

1 基于層次聚類的生物網(wǎng)絡(luò)全局比對

1.1 問題描述

2 個PPI 網(wǎng)絡(luò)分別用無向圖G1=（V1，E1）和G2=（V2，E2）表 示，其中：V1、V2表示網(wǎng)絡(luò)中的節(jié)點集 合；E1、E2表示網(wǎng)絡(luò)中的邊集合；節(jié)點表示蛋白質(zhì)；邊表示2 個蛋白質(zhì)間的相互作用；N（i）表示節(jié)點i的鄰居節(jié)點集合；N（j）表示節(jié)點j的鄰居節(jié)點集合。全局比對f：V1→V2，是 將G1中的V1節(jié)點映射 到G2的V2節(jié)點上，形成一對一的映射關(guān)系，令f(V1)={f()v∈V2|v∈V1}，f(E1)={(f(u)，f(v))∈E2|(u，∈E1}。全局網(wǎng)絡(luò)比對的目的是找到比對節(jié)點對相似性得分之和最大的映射關(guān)系。

1.2 JAlign 算法

本文提出JAlign 算法，利用功能模塊檢測和種子-擴展算法實現(xiàn)全局比對。該算法主要分為3 個階段，分別是種子篩選階段、擴展階段和局部優(yōu)化階段。在種子篩選階段，先基于拓撲和序列信息構(gòu)建目標函數(shù)，再利用層次聚類算法劃分功能模塊并進行模塊間的比對，從模塊對中提取高相似度節(jié)點對作為種子節(jié)點。在擴展階段，先根據(jù)種子節(jié)點計算其鄰居節(jié)點的相似性，再迭代比對高得分的節(jié)點對，逐步將比對擴展至所有可比對的節(jié)點。在局部優(yōu)化階段，先對剩余節(jié)點構(gòu)建二分圖，再利用最大加權(quán)匹配比對剩余節(jié)點，將比對節(jié)點對合并到比對集合。

1.2.1 種子篩選階段

種子篩選階段包括目標函數(shù)構(gòu)建、功能模塊檢測及種子篩選2 個部分。

1）目標函數(shù)構(gòu)建

目標函數(shù)用于衡量節(jié)點間的相似性，是后續(xù)比對的重要依據(jù)，結(jié)合序列信息與拓撲特征可避免僅考慮生物信息或拓撲信息對比對結(jié)果產(chǎn)生的誤導。節(jié)點i和節(jié)點j的序列相似性根據(jù)BLAST bit-score值［27］計算，如式（1）所示：

其中：bblast（i，j）表示節(jié)點i、j之間的BLAST bit-score 值。

若2 個節(jié)點的鄰居節(jié)點拓撲相似，則這2 個節(jié)點拓撲相似的可能性更高，通過同時考慮鄰居節(jié)點的拓撲相似性和節(jié)點本身的相似度計算節(jié)點對的拓撲相似性，能夠更全面地衡量節(jié)點間的拓撲特征。計算節(jié)點i、j拓撲相似性得分T（i，j）的過程如下：首先初始化T0(i，j)=1；然后構(gòu)建二分圖GB=（VB，EB），其中VB由N（i）節(jié)點和N（j）節(jié)點的2 個不相交集合組成，EB中的邊(i′，j′)由N（i）、N（j）中節(jié)點所有可能的連接組成，i′∈N(i)，j′∈N(j)，邊的權(quán)重w(i′，j′)=最后利用貪心算法，每次選中權(quán)重最大的邊添加到匹配集合，遍歷完所有邊后得到GB的匹配集合M，計算該匹配M對應的值。計算公式如式（2）所示：

其中：|N(i)|、|N(j)|表 示節(jié)點i、j的鄰居節(jié)點 數(shù)；d(i)、d(j)表示節(jié)點i、j的度表 示G1、G2中節(jié)點度的最大值；it是迭代次數(shù)；θ是平衡鄰居節(jié)點和節(jié)點本身拓撲相似性比重的參數(shù)，0≤θ≤1。經(jīng)過多次迭代后，矩陣T的最終值為節(jié)點的拓撲相似性。

在計算序列和拓撲相似性之后，可得到節(jié)點的相似性得分，如式（3）所示：

其中：α是平衡拓撲和序列權(quán)重的參數(shù)，0≤α≤1；B(i，j)和T(i，j)分別是序列得分和拓撲得分。

2）功能模塊檢測及種子篩選

生物網(wǎng)絡(luò)的模塊化特征使得具有相似生物功能的蛋白質(zhì)連通密集，功能模塊檢測將功能相似的節(jié)點劃分為同一模塊。從功能模塊中篩選種子，將功能信息融入到比對中，相較于在整個網(wǎng)絡(luò)內(nèi)篩選種子節(jié)點，縮小了種子節(jié)點的選擇范圍，通過對高質(zhì)量的種子進行擴展，提高了比對結(jié)果質(zhì)量。種子篩選階段的算法流程如圖1 所示。首先利用Jerarca 聚類算法劃分輸入網(wǎng)絡(luò)中的功能模塊，構(gòu)成模塊集合，結(jié)合匈牙利算法先進行模塊內(nèi)比對，計算模塊間相似性；然后模塊間比對，得到模塊間的最佳匹配結(jié)果；最后從中篩選出高相似性的節(jié)點對作為種子節(jié)點，其中Jerarca 聚類算法通過節(jié)點間距離劃分模塊，使得在聚類時不會遺漏一些常規(guī)的不完全連通的功能模塊，也不需要GO 文件輔助劃分模塊，從而減少了輸入信息。

圖1 種子篩選流程Fig.1 Procedure of seed selection

種子篩選階段偽代碼算法1 所示。

算法1SeedSelect 算法

種子篩選階段的具體過程如下：

1）根據(jù)式（3）計算節(jié)點間的相似性得分S（u，v）。

2）利用Jerarca 聚類算法檢測G1、G2中的功能模塊，并將模塊信息分別存入集合C1、C2中。

3）計算模塊間的相似性得分（算法1 第4 行和第5 行）。利用匈牙利算法進行模塊內(nèi)比對，得到模塊內(nèi)節(jié)點間的最佳映射關(guān)系MH，計算比對模塊的相似性得分sc，如式（4）所示：

其中：ci、cj分別表示C1、C2中第i、j個模塊；MH是通過匈牙利算法得到的ci、cj內(nèi)節(jié)點的比對集合。

4）根據(jù)模塊間的相似性得分sc，采用匈牙利算法得到模塊間的匹配結(jié)果MC，依據(jù)相似性得分值分布的第3、4 分位數(shù)，篩選出前25%的節(jié)點對作為種子繼續(xù)擴展（算法1 第6 行和第7 行）。

1.2.2 擴展階段

種子篩選階段能夠?qū)⒉糠种匾?jié)點比對上，但仍存在多數(shù)節(jié)點未涉及。為了將比對從種子節(jié)點擴展至整個網(wǎng)絡(luò)，本文提出一種新的擴展方法，基本思路是某一對節(jié)點的鄰居節(jié)點相似性越高，則這對節(jié)點比對上的概率越高，即比對上的鄰居節(jié)點數(shù)越多，該節(jié)點對越可能被比對上。以種子節(jié)點為中心，遍歷其鄰居節(jié)點，將比對逐步從種子節(jié)點擴展至周圍節(jié)點，但僅依靠節(jié)點間的連接關(guān)系確定比對節(jié)點也不全面，會存在多對節(jié)點滿足擴展條件，而每步節(jié)點對的選擇都會對后續(xù)節(jié)點的比對產(chǎn)生影響，從多角度考慮可以得出較為全面的結(jié)果。本階段通過綜合考慮節(jié)點間的連接關(guān)系、度特征、節(jié)點相似性，更全面、謹慎地確定擴展節(jié)點，產(chǎn)生更優(yōu)的比對結(jié)果。

擴展階段偽代碼如算法2 所示。

算法2Extension 算法

擴展階段的具體過程如下：

1）將種子節(jié)點對添加到比對集合M（算法2第1 行）。

2）計算種子的鄰居節(jié)點間的結(jié)構(gòu)相似性（算法2第2 行和第3 行）。遍歷種子節(jié)點的所有鄰居節(jié)點，計算每一對鄰居節(jié)點在已比對節(jié)點集合中的公共鄰居節(jié)點數(shù)作為鄰居節(jié)點的結(jié)構(gòu)相似性得分sstru，如式（5）所示：

3）綜合鄰居節(jié)點結(jié)構(gòu)相似性sstru、度、節(jié)點相似性S選擇擴展節(jié)點對（算法2 第5～15 行）。首先對所有結(jié)構(gòu)相似性從高到低排序，將得分最高的節(jié)點對添加到集合N，若N中存在多個得分最高的節(jié)點對，計算節(jié)點間的度差值，保留集合N中度差值最小的節(jié)點對，若N中存在多個最小度差值節(jié)點對，則根據(jù)式（3）中相似性得分S選擇節(jié)點對，將相似性得分最高的節(jié)點對添加到比對集合中。

4）每有一對新的節(jié)點比對成功，更新其鄰居節(jié)點的相似性得分（算法2 第2 行），重復上述過程，直至沒有可選擇的節(jié)點對。

1.2.3 局部優(yōu)化階段

擴展階段只是將比對從種子節(jié)點擴展到節(jié)點的鄰域，這對于種子節(jié)點的選擇非常重要，而模塊檢測是從網(wǎng)絡(luò)中提取出連通密集模塊并從中篩選出種子，因此，選擇的種子節(jié)點多數(shù)是在連通密集的子圖中的，對于較為離散或連通度不高的子圖，比對上的概率很低，而這一部分子圖中可能有部分節(jié)點是重要節(jié)點。為了解決這一問題，局部優(yōu)化階段對剩余節(jié)點進行局部優(yōu)化比對，通過二分圖的加權(quán)匹配比對剩余節(jié)點，使得孤立節(jié)點也能參與比對，將比對覆蓋至整個網(wǎng)絡(luò)。具體過程如下：

1）查找出G1、G2網(wǎng)絡(luò)中未比對上的節(jié)點，構(gòu)建二分圖Gb，所有邊的權(quán)重為該節(jié)點對的相似性得分S。

2）選擇權(quán)重最大的邊合并到比對集合M中。

3）刪除步驟2 中選中的節(jié)點對及其相關(guān)的邊。

4）重復步驟2、3，直至圖中沒有邊存在。

如圖2 所示，先選中權(quán)重最大的邊（a，d），若a、d節(jié)點均未在比對集中出現(xiàn)過，則將節(jié)點對（a，d）添加到比對集合中，刪除a、d節(jié)點及其相關(guān)的邊，再從剩余邊中選擇權(quán)重最大的邊，選擇的邊是（b，e），確定b、e節(jié)點未出現(xiàn)在現(xiàn)有比對集合中，將（b，e）添加到比對集合，刪除b、e節(jié)點及其相關(guān)的邊，此時，Gb中無可匹配節(jié)點對存在，比對結(jié)束，將節(jié)點對（a，d）、（b，e）合并至比對集合，得到最終比對結(jié)果。

圖2 剩余節(jié)點匹配示例Fig.2 Example of the matching for remaining nodes

1.3 時間復雜度分析

令n=max{|V1|，|V2|}，m=max{|E1|，|E2|}。第一階段是種子篩選，計算節(jié)點相似性的時間復雜度為O(n2)，聚類算法劃分模塊的時間復雜度為O(n2logan)，匈牙利算法的時間復雜度是O(n2)，因此，第一階段的時間復雜度為O(n2logan)；第二階段是擴展比對，種子節(jié)點對最多有n對，每個種子節(jié)點的鄰居節(jié)點最多有m個，因此，復雜度為O(nm2)；第三階段是剩余節(jié)點比對，剩余節(jié)點最多有n個，因此，第三階段的時間復雜度為是O(n2)。至此，本文算法總的時間復雜度為O(n2logan+nm2)。在生物網(wǎng)絡(luò)普遍性假設(shè)中，m≈nlogan，所以，本文算法的時間復雜度為O(nm2)=O(n3logan)。

2 實驗與結(jié)果分析

2.1 實驗數(shù)據(jù)

實驗所用數(shù)據(jù)來自Isobase［28］數(shù)據(jù)庫的真實網(wǎng)絡(luò)數(shù)據(jù)和NAPAbench［29］合成網(wǎng)絡(luò)數(shù)據(jù)，真實網(wǎng)絡(luò)數(shù)據(jù)包括Caenorhabditis Elegans（CE）、Saccharomyces Cerevisiae（SC）、Drosophila Melanogaster（DM）、Homo Sapiens（HS）等4 個物種，合成網(wǎng)絡(luò)包括Crystal Growth（CG）、Duplication Mutation Completion（DMC）、Duplication with Random Mutation（DMR）。生物網(wǎng)絡(luò)的節(jié)點和邊信息見表1，其中真實網(wǎng)絡(luò)的數(shù)據(jù)均經(jīng)過預處理，排除了自循環(huán)、重復的邊和節(jié)點。

表1 網(wǎng)絡(luò)數(shù)據(jù)信息Table 1 Network data information

2.2 評價指標

對于網(wǎng)絡(luò)比對算法的性能，從拓撲質(zhì)量和生物質(zhì)量2 個方面進行評估。

1）拓撲質(zhì)量度量

邊正確性（Edge Correctness，EC）［7］是衡量網(wǎng)絡(luò)比對拓撲質(zhì)量最常用的指標，通過計算f映射下保守邊在源網(wǎng)絡(luò)中的比例來評估比對的質(zhì)量，不能懲罰將稀疏網(wǎng)絡(luò)映射到密集網(wǎng)絡(luò)的比對。EC 計算公式如式（6）所示：

其中：|E1|表示G1網(wǎng)絡(luò)的邊數(shù)；|f（E1）|表示以f映射方式覆蓋到G2中的邊的邊數(shù)。

誘導保守子結(jié)構(gòu)得分（Induced Con-served-structure Score，ICS）［30］計算保守邊與誘導邊的比例，克服了EC 的問題，但不能懲罰將密集網(wǎng)絡(luò)映射到稀疏網(wǎng)絡(luò)的比對。ICS 計算公式如式（7）所示：

對稱子結(jié)構(gòu)得分（Symmetric Sub-structure Score，S3）［31］針對源網(wǎng)絡(luò)和目標網(wǎng)絡(luò)，既能懲罰稀疏到密集的比對又能懲罰密集到稀疏的比對。S3的計算公式如式（8）所示：

其中：分母表示根據(jù)比對f將G1和G2誘導子圖重疊得到復合圖計算圖中唯一邊的數(shù)目；|E1|表示G1網(wǎng)絡(luò)中的邊數(shù)。

2）生物質(zhì)量度量

生物質(zhì)量使用功能一致性（Functional Coherence，F(xiàn)C）［32］來衡量，F(xiàn)C 利用GO 術(shù)語測量比對蛋白質(zhì)的功能一致性。GO 術(shù)語描述蛋白質(zhì)的生物特性，包括分子功能（Molecular Function，MF）、細胞成分（Cellular Component，CC）、生物過程（Biological Process，BP）［33］。通常認為具有相似GO術(shù)語的蛋白質(zhì)其生物功能相似。FC 計算公式如式（9）和式（10）所示：

其中：GO（u）和GO（f（u））表示節(jié)點u和f（u）被注釋的GO 集合。

2.3 結(jié)果分析

本文將JAlign 算法與L-GRAAL、SPINAL、ModuleAlign 算法進行比較，在參數(shù)設(shè)置上，拓撲相似性計算中θ設(shè)置為0.5，迭代2 次，總相似性中α設(shè)置 為0.4。Jerarca 聚類中選 擇RCluster［26］迭代算法，迭代3 次，層次樹構(gòu)建使用UPGMA［26］算法。其他算法的參數(shù)設(shè)置參照原文設(shè)置，具體參數(shù)設(shè)置如表2所示。

表2 3 種對比算法的參數(shù)設(shè)置Table 2 Parameters setting of three alignment algorithms

2.3.1 合成網(wǎng)絡(luò)比對結(jié)果分析

4 種算法在合成網(wǎng)絡(luò)上的比對結(jié)果如表3 所示，其中，加粗的數(shù)據(jù)為最佳結(jié)果，加下劃線的數(shù)據(jù)為次優(yōu)結(jié)果，下同。在拓撲指標上，JAlign 算法的結(jié)果明顯優(yōu)于其他3 種算法；在生物指標FC 上，JAlign 算法僅次于SPINAL 算法，L-GRAAL 算法表現(xiàn)最差?？傮w而言，JAlign 算法在合成網(wǎng)絡(luò)上表現(xiàn)最好，在保證了較好的生物特性的基礎(chǔ)上實現(xiàn)了最好的拓撲質(zhì)量。

表3 合成網(wǎng)絡(luò)比對結(jié)果Table 3 Alignment result for synthesis networks

2.3.2 真實網(wǎng)絡(luò)比對結(jié)果分析

在真實網(wǎng)絡(luò)上，分別從EC、ICS、S3、FC 這4 個方面對比4 種算法，4 種算法在EC 指標上的結(jié)果如表4所示。實驗結(jié)果表明：在CE-SC、CE-HS、DM-HS 中，ModuleAlign 算法表現(xiàn)最 好；在SC-HS、SC-DM 中，JAlign 算法表現(xiàn)最好。

表4 不同算法在不同物種上的EC 指標Table 4 EC index of different algorithms for different species

表5 是不同算法在ICS 指標上的對比結(jié)果。實驗結(jié)果表明：L-GRAAL 算法在CE-SC、CE-DM、CE-HS、DM-HS 實驗中結(jié)果最好；JAlign 算法在這4 組實驗中表現(xiàn)僅次于L-GRAAL 算法，在SC-HS、SC-DM 實驗中結(jié)果最好；SPINAL 在各組實驗中結(jié)果最差。

表5 不同算法在不同物種上的ICS 指標Table 5 ICS index of different algorithms for different species

表6 是不同算法在S3指標上的對比結(jié)果，S3是從源網(wǎng)絡(luò)和目標網(wǎng)絡(luò)2 個方面度量拓撲特征，能夠更全面地分析算法的拓撲質(zhì)量。實驗結(jié)果表明：JAlign算法在網(wǎng)絡(luò)規(guī)模較大的物種上，相較于其他算法表現(xiàn)最好，也較為穩(wěn)定；L-GRAAL 算法僅次于JAlign，且在小網(wǎng)絡(luò)上結(jié)果較好?？偨Y(jié)上述結(jié)果，JAlign 算法在拓撲質(zhì)量上可以得到穩(wěn)定、最好的實驗結(jié)果，L-GRAAL 算法整體表現(xiàn)僅次于JAlign 算法。

表6 不同算法在不同物種上的S3指標Table 6 S3 index of different algorithms for different species

表7 是不同算法在FC 指標上的對比結(jié)果。從生物指標角度來看，SPINAL 算法和JAlign 算法結(jié)果相近，L-GRAAL 算法表現(xiàn)最差。

表7 不同算法在不同物種上的FC 指標Table 7 FC index of different algorithms for different species

表8 給出了不同算法運行時間的比較，實驗計算機使用Inter Core i7-10510U 2.30 GHz 處理器，內(nèi)存16 GB，算法在Linux Ubuntu 環(huán)境下運行。實驗結(jié)果表明，在時間效率上JAlign 算法也具有一定優(yōu)勢，SPINAL、ModuleAlign 算法運行時間較長。

表8 不同算法的運行時間Table 8 Running time of different algorithms

結(jié)合拓撲質(zhì)量度量結(jié)果分析，雖然SPINAL 算法在生物指標上表現(xiàn)很好，但在拓撲指標上表現(xiàn)較差，而L-GRAAL 算法則與之相反，其在犧牲一定生物質(zhì)量的基礎(chǔ)上實現(xiàn)了較好的拓撲質(zhì)量，4 種算法中只有JAlign 算法同時實現(xiàn)了最佳的拓撲度量和生物度量。進一步分析實驗過程可知，JAlign 算法在目標函數(shù)中添加了拓撲特征并降低了序列特征的比重，在聚類算法中也僅依靠節(jié)點的結(jié)構(gòu)信息來劃分模塊，但隨著序列信息所占比例的降低，其在生物指標上表現(xiàn)仍優(yōu)于大部分算法，這說明JAlign 算法可以實現(xiàn)生物一致性和拓撲特性的良好平衡。

3 結(jié)束語

本文提出的生物網(wǎng)絡(luò)全局比對算法JAlign。基于種子-擴展算法，利用層次聚類算法檢測功能模塊并進行模塊匹配，根據(jù)目標函數(shù)從模塊中篩選種子節(jié)點。在此基礎(chǔ)上，結(jié)合鄰居節(jié)點與種子節(jié)點間的連接關(guān)系將比對擴展至種子節(jié)點的鄰居節(jié)點，并對剩余節(jié)點構(gòu)建二分圖進行最大加權(quán)匹配，使得孤立節(jié)點也有機會被比對上。實驗結(jié)果表明，該算法能夠全面地考慮比對過程，實現(xiàn)拓撲質(zhì)量與生物質(zhì)量的良好平衡，相較于其他3 種對比算法，其在拓撲和生物角度同時達到了最優(yōu)的比對結(jié)果。為優(yōu)化JAlign 算法的效率，進一步提高算法在生物功能方面的性能，下一步將對功能模塊檢測部分做并行化處理，并將模塊檢測應用到目標函數(shù)計算和種子的擴展階段。