蛋白質交互作用網路之視覺化系統

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：3.128.199.88

姓名

林俊吉(Jun-Ji Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

蛋白質交互作用網路之視覺化系統
(Protein - Protein Interaction Network Visualization System)

相關論文

★ 一種減輕LEO衛星網路干擾的方案	★ 萃取駕駛人在不同環境之駕駛行為方法
★ 非地面網路中基於位置的隨機接入分配方法	★ TrustFADE: 針對可程式化邏輯區塊之安全認證方法
★ 捷徑問題在特殊圖形上之演算研究	★ 行動電腦教室與其管理系統的設計與建置
★ 蛋白質體視覺化系統之實作	★ 最小切割樹群聚演算法極端情形之研究
★ 教室內應用無線科技之一對一數位學習模式	★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作
★ 蛋白質註解的三維視覺化工具	★ Joyce 2：一個在一對一數位教室環境下之小組競爭遊戲
★ 同儕計算網路上內文散佈演算法之實作與效能評估	★ 在直角多邊形上使用基因演算法畫樹之研究
★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測	★ 從生物文件中萃取出蛋白質或基因之名稱

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在蛋白質交互作用網路中，通常包含有數以千計的蛋白質，甚至是更多。目前雖然有不少用來觀察分析的工具，例如InterViewer、Cytoscape、…等，但多數都只適用於複雜度較小的網路圖。因此當遇到複雜度較高的資料時，這些工具便無法將整個網路圖清楚地表現出來。
由於上述的問題，我們提出一套方法來降低網路圖顯示的複雜度，包括有將網路圖收縮、將網路圖切割成數個連通的網路子圖，並依此來建立成階層式架構，並以階層式表示方式來顯示整個網路圖。所謂的網路圖收縮是指將網路圖中的樹狀圖及團塊圖收縮到一個代表節點上；而網路圖分割主要是利用解決點連通問題的演算法來找出切點集，藉此將網路圖分割開來，如此遞迴分解下去，直到遇到適當的停止條件。透過上述兩種方式，可降低原來網路圖的複雜度。當建立出階層式架構，我們必須把網路圖清楚地繪製出來。在這裡處理網路圖的配置分兩部分：一是收縮的網路圖配置方法，讓每個收縮的網路圖在有限的空間內伸展出來；二是整體網路圖的配置，我們利用彈簧嵌入演算法，並適當加入不同性質的彈簧來配置階層式表示的網路圖。
因為研究上的需要，我們實作出一套系統，除了基本網路圖操作功能之外，我們利用上述方法將網路圖收縮及分割，藉此降低複雜度並建立階層式架構來表示整個網路圖；收縮配置法及彈簧嵌入演算法讓系統自動為使用者調整顯示的網路圖，讓最後的網路配置圖能清楚表示每個節點之間的關係。透過自動的網路圖配置，使網路圖不至於太凌亂，再以互動方式輔助使用者，讓使用者能方便檢視與分析整個網路圖，以利於發現在生物界中未知的事實。

摘要(英)

Protein-protein interaction network usually have thousand of proteins. Today there have several visualization tools, for example, Interviewer、Cytoscape、...etc., but they are only suitable for simple graphs.
Because of this problem, we bring up some methods to reduce graph’’s complexity, including of sub-graph contraction、graph partition, and to establish hierarchial structure. About of graph’’s layout, We use two methods to handle it, including of special layout algorithm (contracted graph) and Spring-Embedder Method(general graph).
We use these methods to establish hierarchical structure, and use some automatic layout methods to layout graph, and let user easy to analyse graph, and discover new unknown fact.

關鍵字(中)

★ 階層式表示
★ 蛋白質交互作用
★ 網路圖配置

關鍵字(英)

★ hierarchical visualization
★ protein-protein interaction
★ graph layout

論文目次

目錄...........................................I
圖目錄........................................II
表目錄........................................IV
第一章緒論................................... 1
第二章網路圖配置之背景知識及相關研究......... 5
2.1 現有方法.......................... 5
2.1.1 一般網路圖的演算法......... 6
2.1.2 特殊條件的網路圖的演算法...10
2.2 現有視覺化工具....................13
第三章系統描述...............................16
3.1 網路圖收縮........................18
3.2 網路圖分割........................19
3.3 收縮子圖的配置方法................25
3.4 整體網路圖的配置方法..............30
第四章系統實作...............................34
4.1 輸入與輸出........................34
4.2 縮圖模組..........................36
4.3 分析模組..........................38
4.4 配置模組..........................39
4.5 功能操作介面......................40
第五章系統測試...............................46
5.1 網路圖分割........................46
5.2 以階層式表示顯示網路圖............52
第六章結論與未來工作.........................57
參考文獻......................................60
附錄一........................................62

參考文獻

[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, “Network Flows, Theory, Algorithms, and Applications”, Pearson Education 1 edition, pp. 864, 1993.
[2] G. D. Battista, P. Eades, R. Tamassia, I.G. Tollis, “Graph Drawing Algorithms for the Visualization of Graphs”, Prentice-Hall, pp. 432, 1999.
[3] R. Davidson and D. Harel, “Drawing Graphs Nicely Using Simulated Annealing”, ACM Trans. Graphics, vol. 15, no. 4, pp. 301-331, 1996.
[4] P. Eades, “A Heuristic for Graph Drawing”, Congr. Numer., vol. 42, pp. 149-160, 1984.
[5] T. Fruchterman and E. Reingold, “Graph Drawing by Force-Directed Placement”. Softw. – Pract. Exp., vol. 21, no. 11, pp. 1129-1164, 1991.
[6] A. Gibbons, “Algorithmic Graph Theory”, Cambridge University Press, pp. 271, 1985.
[7] R.E. Gomory, T.C Hu, “Multi-Terminal Network Flows”, Journal of SIAM, vol. 9, no. 4, pp. 551-570, 1961.
[8] J. L. Gross and J. Yellen, “Graph Theory and Its Applications”, CRC Press, pp. 600, 1998.
[9] T. Kamada and S. Kawai, “An Algorithm for Drawing General Undirected Graph”, Inform. Processing Lett., vol. 31, no. 1, pp. 7-15, 1989.
[10] C. Keskin, V. Vogelmann, “Effective Visualization of Hierarchical Graphs with the Cityscape Metaphor”, Proceedings of the ACM Conference on Information and Knowledge Management (CIKM97), Las Vegas, Nevada, USA, pp. 52-57, 1997.
[11] S. Kirkpatrick, C.D. Gerlatt Jr., M.P. Vecchi, “Optimization by Simulated Annealing”, Science, vol. 220, pp. 671-680, 1983.
[12] M. Lewenstein and M. Sviridenko, “A 5/8 Approximation Algorithm for the Asymmetric Maximum TSP”, SIAM J. Discrete Math. vol. 17, no. 2, pp. 237-248, 2003.
[13] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller, “Equations of State Calculations by Fast Computing Machines”, J. Chem. Phys., vol. 21, pp. 1087-1092, 1958.
[14] M. Pincus, “A Monte Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems”, Oper. Res., vol. 18, pp. 1225-1228, 1970.
[15] N. R. Quinn Jr. and M. A. Breuer, “A Forced Directed Component Placement Procedure for Printed Circuit Boards”, IEEE Trans. CAS, vol. 26, no. 6, pp. 377-388, 1979.
[16] S. S. Skiena, “The Algorithm Design Manual”, Springer-Verlag, pp. 504, 1997.
[17] K. Sugiyama, S. Tagawa, and M. Toda., “Methods for Visual Understanding of Hierarchical Systems”, IEEE Trans. Syst. Man Cybern., SMC, vol. 11, no. 2, pp. 109-125, 1981.
[18] R. Tamassia, “On Embedding a Graph in the Grid with the Minimum Number of Bends”, SIAM J. Comput., vol. 16, no. 3, pp. 421-444, 1987.
[19] C. Walshaw, “A Multilevel Algorithm for Force Directed Graph Drawing”, Lecture Notes in Computer Science archive Proceedings of the 8th International Symposium on Graph Drawing table of contents, pp. 171-182, 2000.
[20] K. Yee, D. Fisher, R. Dhamija, M. Hearst, “Animated Exploration of Graphs With Radial Layout”, Proceedings of the 2001 Symposium on IEEE Information Visualization, pp. 43-50, 2001.

指導教授

何錦文、高明達
(Chin-Wen Ho、Ming-Tat Ko)

審核日期

2004-7-27

推文