本文關鍵詞：復雜網絡中關鍵節(jié)點的查找方法研究

  更多相關文章： 中點 直徑路徑 先驗蛋白質 PPI網絡 復雜網絡

【摘要】：復雜網絡中的關鍵節(jié)點對整個網絡的結構具有重要作用。對于真實網絡而言,能夠有效地定位到關鍵節(jié)點對網絡的維護與網絡性質的研究等方面都具有重要意義。本文從網絡拓撲結構出發(fā),并結合PPI (Protein-Protein Interaction)網絡的生物信息特征,給出兩個關鍵節(jié)點查找算法。直徑在各種類型的網絡中都是極其重要的拓撲結構參數。然而,直徑很少被用于關鍵節(jié)點的查找。本文定義直徑所在路徑的中點為整個網絡的中點,并給出搜索中點的DCD算法。該算法被用在小世界網絡、無標度網絡、星形長尾網絡和五個真實網絡中,實驗結果表明,通過DCD算法搜索到的中點在網絡中心性指標如介數中心性(BC)接近中心性(CC)、度中心性(DC)、肛核分解上比整個網絡的平均情況具有優(yōu)勢。此外,刪除中點后,網絡結構如直徑和最大連通分支都發(fā)生很大變化。本文還基于DCD算法提出了有效的刪邊策略,該策略能夠實現只刪除少量邊而使網絡節(jié)點對在很大程度上不連通。DCD算法不需要找到所有可能的直徑所在路徑,而是基于廣度優(yōu)先和Bellman準則,因此其時間復雜度對于稀疏網絡而言要優(yōu)于Floyd算法。對于PPI網絡而言,結合生物信息的關節(jié)蛋白質搜索方法被證明比單純從拓撲結構出發(fā)的方法準確率更高。然而,現有的大多數搜索方法只包含一類生物學信息。PPI網絡固有的由假陽性及假陰性交互關系引起的噪音也對重要蛋白質預測的準確性有很大影響。本文對此提出了一個有效的重要蛋白質搜索方法IDSSP,該方法首先結合STRING數據庫的多種生物學信息對每個蛋白質進行評分,評分高的蛋白質被用作先驗蛋白質。然后,對先驗蛋白質的鄰居節(jié)點進行權重計算以選出候選重要蛋白質,權值的計算過程通過對DIP和STRING數據庫的整合實現。整合后的蛋白質交互關系具有高可信性。在釀酒酵母菌上進行的實驗結果表明IDSSP方法在絕大多數情況下比現有的準確率較高的方法CPPK、CEPPK和UDoNC準確率更高。除此之外,本文中所使用的先驗蛋白質不需要是重要蛋白質。
【關鍵詞】：中點 直徑路徑 先驗蛋白質 PPI網絡 復雜網絡
【學位授予單位】：大連理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-9
• 1 緒論9-13
• 1.1 研究背景及意義9-10
• 1.2 研究現狀10-12
• 1.3 本文內容組織結構12-13
• 2 復雜網絡關鍵節(jié)點搜索概述13-23
• 2.1 復雜網絡中心性指標簡介13-14
• 2.1.1 介數中心性13
• 2.1.2 接近中心性13-14
• 2.1.3 度中心性14
• 2.1.4 k-核分解14
• 2.2 直徑與網絡連通性14-15
• 2.3 PPI網絡中的關鍵節(jié)點搜索15-22
• 2.3.1 “中心性—致命性”法則15-17
• 2.3.2 PPI相關數據庫17-18
• 2.3.3 重要蛋白質搜索算法18-22
• 2.4 小結22-23
• 3 基于直徑的重要節(jié)點搜索方法23-39
• 3.1 基于直徑的重要節(jié)點搜索方法23-25
• 3.2 數據集25-27
• 3.2.1 確定性網絡25-26
• 3.2.2 由Pajek生成的小世界網絡模型和無標度網絡模型26-27
• 3.2.3 實際網絡27
• 3.3 實驗結果27-37
• 3.3.1 確定性網絡27-28
• 3.3.2 星形長尾網絡28-29
• 3.3.3 小世界網絡和無標度網絡29-32
• 3.3.4 實際網絡32-35
• 3.3.5 基于DCD算法的刪邊策略35-37
• 3.4 DCD算法時間復雜度37
• 3.5 結論37-39
• 4 基于先驗知識的重要蛋白質搜索方法39-50
• 4.1 基于先驗知識的重要蛋白質搜索方法39-42
• 4.1.1 STRING中的組合分數39-40
• 4.1.2 IDSSP中的蛋白質評分40-41
• 4.1.3 候選重要蛋白質41-42
• 4.2 數據集42
• 4.3 實驗結果42-48
• 4.3.1 綜合比較42-43
• 4.3.2 先驗蛋白質個數43-44
• 4.3.3 重要與非重要先驗蛋白質44-45
• 4.3.4 IDSSP方法的隨機性45-47
• 4.3.5 F_1 Score47-48
• 4.3.6 高分先驗蛋白質的普適性48
• 4.4 結論48-50
• 結論50-52
• 參考文獻52-58
• 附錄A DCD算法偽代碼58-61
• 附錄B S.cere中評分前40名的蛋白質61-62
• 攻讀碩士學位期間發(fā)表學術論文情況62-63
• 致謝63-64

【相似文獻】

中國期刊全文數據庫 前5條

1 李忠學,童根樹,嚴慧;節(jié)點連接剛性對門式剛架結構承載能力的影響[J];力學季刊;2001年02期

2 孫偉;李平;;全預制砼框架結構節(jié)點連接[J];科技信息;2009年23期

3 譚躍進;吳俊;鄧宏鐘;;復雜網絡中節(jié)點重要度評估的節(jié)點收縮方法[J];系統(tǒng)工程理論與實踐;2006年11期

4 王蕾蕾;林中材;潘佳慶;楊孔慶;鄒衛(wèi)東;;利用節(jié)點效率評估地理網格網絡的魯棒性[J];湖北科技學院學報;2013年02期

5 ;[J];;年期

中國重要會議論文全文數據庫 前1條

1 查曉雄;鐘建偉;;節(jié)點對集裝箱房性能影響的研究[A];'2011全國鋼結構學術年會論文集[C];2011年

中國重要報紙全文數據庫 前1條

1 ;為電網“充電”[N];網絡世界;2002年

中國博士學位論文全文數據庫 前3條

1 王家林;非節(jié)點連接有限元理論及其軟件實現[D];重慶大學;2008年

2 劉軍;物聯網可靠感知節(jié)點部署優(yōu)化理論與方法研究[D];廣東工業(yè)大學;2015年

3 劉亞志;延遲容忍網中數據傳輸關鍵技術研究[D];北京郵電大學;2013年

中國碩士學位論文全文數據庫 前10條

1 鄭曉欣;城市供水管網節(jié)點混合規(guī)律研究[D];哈爾濱工業(yè)大學;2015年

2 任卓明;復雜網絡中的節(jié)點重要性度量研究[D];上海理工大學;2013年

3 楊文靜;Tarax Node節(jié)點在線調試平臺的設計與實現[D];電子科技大學;2015年

4 王倩;影響信息流行為的節(jié)點間關系模型與控制策略的研究[D];石家莊鐵道大學;2015年

5 陸兆龍;鋼筋混凝土寬柱雙梁節(jié)點的抗震性能研究[D];揚州大學;2015年

6 雷雨潼;林中有向傳感器節(jié)點確定性部署的研究[D];北京林業(yè)大學;2016年

7 南棟卿;復雜網絡中關鍵節(jié)點的識別研究[D];吉林大學;2016年

8 謝昆;多溫度工況冷彎薄壁鋼貨架梁-柱節(jié)點疲勞性能試驗研究[D];東南大學;2016年

9 關雅文;復雜網絡中關鍵節(jié)點的查找方法研究[D];大連理工大學;2016年

10 毛一帆;含時二分網絡中重要節(jié)點的識別研究[D];深圳大學;2017年

，

本文編號：930192