[發明專利]一種融合社區結構和節點度的局部路徑相似度的蛋白質鏈接預測算法

在審

• 申請號: 201911153140.1
• 申請日: 2019-11-22
• 公開（公告）號: CN111696626A
• 公開（公告）日: 2020-09-22
• 發明（設計）人: 王貴參;王紅梅;李浩;王金哲;王遠威;郭真俊
• 申請（專利權）人: 長春工業大學
• 主分類號: G16B25/10
• 分類號: G16B25/10
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種融合社區結構和節點度的局部路徑相似度的蛋白質鏈接預測算法，該算法的目的是預測蛋白質交互網絡中的潛在鏈接。該方法的步驟主要包括：構建鄰接矩陣，檢測社區結構，構建訓練集和測試集，計算社區緊密度指標，計算基于節點度的局部路徑相似度，計算中所有未鏈接的節點之間的相似度值。現有的鏈接預測方法大多利用節點的共同鄰居信息，而沒有考慮到蛋白質社區結構信息對鏈接預測的貢獻。因此，在考慮到基于局部信息相似性的方法和基于社區結構的蛋白質交互預測方法存在的不足，本發明提出了一種融合社區結構和節點度的局部路徑相似度的蛋白質鏈接預測方法，在考慮蛋白質交互網絡中的社區信息的同時，結合蛋白質之間的拓撲結構進行鏈接預測。

技術領域

本發明屬于復雜網絡領域，尤其涉及一種融合社區結構和節點度的局部路徑相似度的蛋白質鏈接預測算法。

背景技術

近年來，國內外學者在蛋白質交互網絡(protein-protein interactionnetwork, PPI)的鏈接預測方面做了大量的工作。現有的鏈接預測方法通常是利用節點局部信息來進行預測。作為經典的鏈接預測方法，基于局部信息相似性的方法由于具有準確性高和復雜性低的特性，已應用于蛋白質交互網絡中的鏈接預測。基于局部信息相似性的方法通常都會基于節點間相似程度越高，鏈接出現的可能性越高這一假設來進行鏈接預測。經典的局部相似性方法有共同鄰居（Common neighbors, CN）、Adamic-Adar（AA）、資源分配（Resource allocation，RA）和偏好連接（Preferential attachment，PA）等。2002年，Saito等人提出基于節點及其鄰居節點的拓撲關系來預測蛋白質交互出現的可能性。這些經典的鏈接預測方法大多利用節點的共同鄰居信息，而沒有考慮到蛋白質社區結構信息對鏈接預測的貢獻。

蛋白質之間的交互通常依賴生物過程的內部機制。蛋白質社區通常會共同完成某一種或若干種生物學功能。在預測PPI網絡的潛在交互信息時，需要結合蛋白質所在的社區結構信息，來進行蛋白質交互的預測。基于上述理論，近年來，有諸多學者提出了基于社區結構信息的蛋白質交互預測方法。2016年，洪海燕等人將PPI網絡看作一個有權無向圖，提出了一種基于空間關系映射的蛋白質相互作用預測方法。2017年，Sun等人基于群落結構和節點度的關系，提出了一種局部親和力結構(LAS)的相似度計算方法。基于節點鏈接與所屬社區緊密程度有關這一假設，Li等人提出了一種基于社區關系強度的鏈接預測方法。上述方法更注重挖掘網絡拓撲結構，缺乏對蛋白質本身拓撲信息的挖掘。

發明內容

針對基于節點相似性和基于社區結構的鏈接預測算法中存在的不足，本發明提供了一種融合社區結構和節點度的局部路徑相似度的蛋白質鏈接預測算法，所述方法步驟如下：

步驟S1：構建鄰接矩陣

輸入數據為蛋白質交互網絡的鏈接集合，構建鄰接矩陣

步驟S2：檢測社區結構

使用社區發現算法infomap算法，將網絡劃分為不同的社區

步驟S3：劃分訓練集和測試集

隨機刪除一定比例的鏈接作為測試集，剩余的鏈接集合記為，有。以下計算都在中進行

步驟S4：計算每個社區緊密度指標

根據步驟S2中得到的社區劃分，計算社區內的平均最短路徑，用它來衡量社區的緊密度。社區緊密度與社區平均最短路徑成反比

步驟S5：計算基于節點度的局部路徑相似度（Local path similarity based on nodedegree，DLP）

由于次級鄰居和目標節點度對最終的鏈接產生的影響，計算基于次級鄰居和節點度的相似度指標

步驟S6：結合社區緊密度和DLP計算中所有未鏈接的節點之間的相似度值。