[發明專利]一種復雜網絡圖的概要方法及其在蛋白質關系網中的應用

在審

• 申請號: 201911335783.8
• 申請日: 2019-12-23
• 公開（公告）號: CN110956223A
• 公開（公告）日: 2020-04-03
• 發明（設計）人: 董一鴻;徐麗麗;王雄
• 申請（專利權）人: 寧波大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 寧波誠源專利事務所有限公司 33102
• 代理人: 徐雪波;鄧青玲

本發明涉及一種復雜網絡圖的概要方法及其在蛋白質關系網中的應用，將復雜網絡圖記為G＝(V，E)，V為節點的集合，E為邊的集合，包括：步驟1、在復雜網絡圖中挑選出子圖H＝(V′,E′)，對于子圖中任意兩節點組成的邊滿足條件：sup(e(u,v)，H)≥k?2，將這些子圖標記為稠密子圖；步驟2、將每個稠密子圖中的所有節點壓縮成一個節點，將該節點標記為超點，將與所有超點相關聯的邊，標記為超邊；步驟3、將所有超點和除超點外的其他節點組成新的節點集合，將超邊和除超邊外的其他邊組成新的邊集合，將新的節點集合和新的邊集合形成概要圖。能有效減小數據規模，降低網絡布局中節點和關聯邊密集的現象，近似保持原始圖的冪率性和聚類系數；且能清晰地顯示數據整體結構。

本發明要求以下中國專利申請的優先權，申請日為：2018年12月24日，申請號為：201811583927.7，該申請的全部內容通過引用結合在本申請中。

技術領域

本發明涉及數據處理領域，特別涉及一種復雜網絡圖的概要方法及其在蛋白質關系網中的應用。

背景技術

現代社會存在大量的復雜網絡，如計算機網絡、物聯網、通信網、交通網絡、以及社會關系網絡等，對網絡進行有效的分析成為重要的科學問題。復雜網絡可以用數據結構中的圖進行描述，圖的節點表示網絡中的實體，邊表示實體間的聯系。隨著網絡規模的增大，需要占用更多的存儲空間。超大規模的復雜網絡給算法分析和可視化帶來了挑戰，復雜網絡節點和邊關聯數量眾多，難以從原始網絡圖中進行有效信息提取并分析；其結構的復雜且出現噪聲邊影響原始圖的可視化，人們無法準確觀察到網絡的拓撲結構。

大規模圖數據中隱藏了大量有用的信息，需要進行有效的提取。近年來科研人員開始研究如何將大規模圖的節點聚集成若干組，構造一個能反映原始圖結構和圖屬性的小規模圖，稱為概要圖，概要圖在復雜網絡的存儲分析和可視化中扮演重要角色。采用圖概要技術將大規模的圖轉化為相對較小的圖，保持原始圖的結構和性質。一般將結構或者屬性值相近的節點進行概要化生成概要圖，代替原始圖來進行相應圖分析算法，有效壓縮圖數據的規模、減少存儲空間壓力、減少圖數據中冗余噪聲邊的影響和增強可視化的展示效果，在一定程度上解決了復雜網絡所面對的問題。但目前概要算法在度量相似結構中大多從網絡網絡結構考慮，例如：基于團或者基于度的性質考慮，沒有考慮到對復雜網絡的小世界特性和無標度特性的研究。復雜網絡是呈現高度復雜性的網絡，復雜網絡的小世界特性與網絡的平均聚類系數有關，無標度特性與網絡的冪率性有關。因此，針對大規模的復雜網絡，構建保持復雜網絡圖特性的概要圖并進行進一步分析逐漸成為近幾年的研究熱點。

蛋白質是一種復雜的有機化合物，也稱“多肽”，它由氨基酸分子排列的線性鏈所構成，其氨基酸序列是由對應的基因序列所確定。多個蛋白質可以組成復合體來實現某一特定功能。蛋白質及其復合物的功能有很多，最主要的幾種基本生物功能由：組成和修復成物體、調節生物體的生理機能，運輸載體和供給能量。近年來，越來越多的生物學研究者開始研究蛋白質組學，蛋白質組學是應用各種技術研究蛋白質組的一門新興科學，其目的時從整體的角度分析細胞內動態變化的蛋白質組分、表達水平與修飾狀態，了解蛋白質之間的相互作用與聯系，揭示蛋白質功能與細胞生命活動規律。然而細胞中的每一個蛋白質都不是孤立存在的，每一項生命活動從開始到結束都會涉及到多個蛋白質，這些蛋白質通過相互作用連在一起共同完成一項生命活動。因此，在蛋白質組學中，大多學著采用蛋白質相互作用網絡(ProteinProtein Interaction Networks)來研究紛繁復雜的蛋白質相互作用關系。蛋白質相互作用網絡，也稱蛋白質關系網，可以描述呈一個以蛋白質為節點，蛋白質相互作用關系為邊構成的網絡。蛋白質相互作用關系網絡刻畫了一個生物體內所有蛋白質之間的全局關系，因此蛋白質相互作用關系網絡研究是生物學和計算機科學領域的一個研究重點。并且在細胞生物活動中，絕大多數蛋白質都是通過與其他蛋白質的相互作用形成蛋白質復合物來共同完成一個指定的功能。但是在某一個蛋白質相互作用網絡中，需要分析的蛋白質結構分廠數量龐大，直接分析所有的蛋白質個體會導致復雜度過高，且至多只能考慮蛋白質對間的相互作用，無法得知蛋白質復合物的具體作用。