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

在審

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

本發明公開了一種基于遺傳算法的生物網絡比對方法，包括以下步驟：步驟1：讀取源網絡、目標網絡數據文件及其序列相似性得分文件；步驟2：計算源網絡、目標網絡中節點的重要性得分，結合網絡的拓撲相似性和序列相似性得分計算節點對相似性得分；步驟3：基于節點對相似性得分初始化種群；步驟4：計算種群中個體的適應度值；步驟5：選擇、交叉產生下一代；步驟6：重復步驟4、步驟5直至目標函數收斂或迭代次數達到閾值。本發明計算了節點在網絡中的拓撲重要性，結合節點對的序列信息，充分挖掘網絡節點的拓撲和生物信息，使比對結果在拓撲特性和生物特性上保持均衡的高指標。

技術領域

本發明涉及生物網絡全局比對技術領域，具體涉及一種基于遺傳算法的生物網絡比對方法。

背景技術

網絡比對是復雜網絡的一個研究方向，可以應用在生活中常見的交通網絡、社會網絡、生物網絡等。其中，生物網絡比對是一種常用的研究生物分子間相互作用的方法，也是分析物種間功能差異的重要手段，通過對生物網絡的比較，可以挖掘物種間功能的差異性、物種間的知識轉移、系統發育關系等。

現有的生物網絡全局比對方法主要有以下幾種：

(1)“SPINAL:scalable protein interaction network aligment”(期刊出處：Bioinformatics.2013,4(29):917–924)該算法基于局部鄰域匹配構建初始相似性矩陣并由此得到粗粒度的比對結果，使用種子擴展方法以及基于迭代交換的局部改進方法得到細粒度結果。算法存在的問題：節點的生物信息挖掘不充分，導致最終比對的拓撲指標高，但生物指標低。

(2)“PROPER:global protein interaction network alignment throughpercolation matching”(期刊出處：BMC Bioinformatics,2016,17(1):527)該算法假設蛋白質序列的高相似度代表著功能的高相似度，優先挑選出具有高序列相似度的節點對進行匹配，將其作為基礎比對結果，然后在該結果上逐步完善比對結果。算法存在的問題：節點的拓撲信息挖掘不充分，導致最終比對的生物指標高，但拓撲指標低。

(3)“MAGNA++:Maximizing accuracy in global network alignment via bothnode and edge conservation”(期刊出處：Bioinformatics,2015,31(14):2409-2411)該算法隨機產生初始種群并以拓撲評價指標EC/ICS/S3為目標函數，利用遺傳算法在優化比對結果。算法存在的問題：目標函數收斂速度慢，比對結果的指標低。

針對這三種現有算法，現亟需一種新的生物網絡比對方法，能夠提高比對的拓撲質量、比對的生物質量、同時提高比對速度。

發明內容

本發明要解決的技術問題是提供一種基于遺傳算法的生物網絡比對方法，提高比對的拓撲質量和生物質量，解決比對結果拓撲與生物質量不平衡問題，并且能夠提高比對速度。

為了解決上述技術問題，本發明提供了一種基于遺傳算法的生物網絡比對方法，其特征在于，包括以下步驟：

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

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

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

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

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

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