[發明專利]基于遺傳算法的生物網絡比對方法

在審

• 申請號: 202011466845.1
• 申請日: 2020-12-14
• 公開（公告）號: CN112446492A
• 公開（公告）日: 2021-03-05
• 發明（設計）人: 陳璟;陳悅
• 申請（專利權）人: 江南大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 蘇州市中南偉業知識產權代理事務所(普通合伙) 32257
• 代理人: 楊慧林

1.一種基于遺傳算法的生物網絡比對方法，其特征在于，包括以下步驟：

步驟1：讀取源網絡、目標網絡數據文件及其序列相似性得分文件；

步驟2：計算源網絡、目標網絡中節點的重要性得分，結合網絡的拓撲相似性和序列相似性得分計算節點對相似性得分；

步驟3：基于節點對相似性得分初始化種群；

步驟4：計算種群中個體的適應度值；

步驟5：選擇、交叉產生下一代；

步驟6：重復步驟4、步驟5直至目標函數收斂或迭代次數達到閾值。

2.如權利要求1所述的基于遺傳算法的生物網絡比對方法，其特征在于，采用最小度啟發式算法計算節點的重要性得分，包括如下步驟：

初始化網絡Gi(i＝1，2)中每個節點和邊的權重，邊的初始權重w(u,v)設為1，節點的初始權重w(u)設為0：

其中u,v表示網絡Gi中的節點，Ei表示網絡Gi中邊的集合；

從度為1的節點開始，到度為10的節點結束，刪除當前度最小的節點u，并更新其相鄰節點和邊的權重，當一個節點被移除時，它的鄰接邊也相應移除，移除的節點和邊的權重被分配給它們的鄰居節點和邊；

當|N(u)|為1時：

當|N(u)|大于1時：

其中N(u)表示節點u的鄰居節點集合，|N(u)|表示節點u的鄰居節點個數；

計算節點v的重要性得分IS(v)：

其中，IS(v)表示節點v的重要性得分，λ控制節點和邊的權重，取0.4；

對節點v的重要性得分進行歸一化處理：

IS(v)＝IS(v)/max_v∈V{IS(v)}。

3.如權利要求2所述的基于遺傳算法的生物網絡比對方法，其特征在于，結合網絡的拓撲相似性和序列相似性得分計算節點對相似性得分，對于網絡G1中的節點u和網絡G2中的節點v,計算節點對(u,v)的相似性得分：

其中控制節點對拓撲相似性得分和序列相似性得分的權重，B(u,v)表示節點對(u,v)的歸一化bit-score值，即從輸入的序列相似性文件中讀取相應數值并進行歸一化處理。

4.如權利要求3所述的基于遺傳算法的生物網絡比對方法，其特征在于，所述初始化種群包括以下步驟：兩個網絡中的任意節點對按照相似性得分S從大到小排列,通過貪心算法選擇當前相似性得分最高的節點對，直到G1網絡中的每個節點都被比對上；隨機產生p-1個比對結果。

5.如權利要求4所述的基于遺傳算法的生物網絡比對方法，其特征在于，所述種群個體適應度值即網絡比對的目標函數：由節點對的相似性得分和邊正確性得分構成：

其中，A表示一個比對結果，F(A)表示比對結果A的目標函數得分，S(u,v)表示節點對(u,v)的相似性得分。

6.如權利要求1所述的基于遺傳算法的生物網絡比對方法，其特征在于，在種群中選擇的過程包括：在迭代的過程中控制種群數目p固定，且p為偶數，為保證在迭代的過程中種群的質量并且加快種群的收斂速度：NABG保留種群前50％的結果至下一代，并選擇上一代種群的第i(0≤ip/2)個個體和第p-1-i個個體為父代，交叉形成剩下的50％個體。

7.如權利要求6所述的基于遺傳算法的生物網絡比對方法，其特征在于，所述交叉的過程為：經過選擇階段選出父代個體后，利用Knuths正則分解和循環分解算法保證兩個父代個體交叉產生一個子代個體，并且子代個體可以繼承兩個父代個體幾乎各一半的特性。

8.一種計算機設備，包括存儲器、處理器及存儲在存儲器上并可在處理器上運行的計算機程序，其特征在于，所述處理器執行所述程序時實現權利要求1到7任一項所述方法的步驟。

9.一種計算機可讀存儲介質，其上存儲有計算機程序，其特征在于，該程序被處理器執行時實現權利要求1到7任一項所述方法的步驟。

10.一種處理器，其特征在于，所述處理器用于運行程序，其中，所述程序運行時執行權利要求1到7任一項所述的方法。