成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林育甫 Lin, Yu-Fu
論文名稱：	利用K條最短路徑預測未知新陳代謝途徑 Using k-shortest paths to predict unknown metabolic pathways
指導教授：	王惠嘉 Wang, Hei-Chia
學位類別：	碩士 Master
系所名稱：	管理學院 - 資訊管理研究所 Institute of Information Management
論文出版年：	2006
畢業學年度：	94
語文別：	中文
論文頁數：	44
中文關鍵詞：	圖形理論、K條最短路徑、新陳代謝途徑
外文關鍵詞：	Metabolic Pathway, Graph Theory, K-shortest paths
相關次數：	點閱：76 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　在後基因體時代，我們不僅僅要了解序列（sequence）中所隱含的意義，進一步探索基因與基因間互相作用所形成的新陳代謝途徑（metabolic pathway），更是另一項重大挑戰。

　　由於電腦科技快速蓬勃發展，使得生物相關資訊及實驗結果呈現指數性成長，有越來越多的公用資料庫提供免費且大量的生物相關資料，供生物研究人員使用，近年來，有許多學者開始利用公用資料庫所提供的生物資料建置新陳代謝網路圖形，並且透過圖形理論進行新陳代謝途徑推論；但這些研究往往忽略了對於起始節點及目標節點的選擇，而是由生物人員進行手動輸入，如此可能會導致推論結果不甚正確，因此在本研究中所提出的方法是藉由擷取現存資料庫相同新陳代謝圖形節點，以確保所有節點是屬於相同新陳代謝，接著再利用K條最短路徑演算法，對事先利用公用資料庫所建置的化合物（compounds）及反應（reactions）網路圖形進行新陳代謝途徑推論，挑選出候補的新陳代謝途徑，以供研究人員繼續後續分析工作。

　　In the post-genomic era, we not only hope to understand the information of biological sequence, and further, a greater challenge is to explore the metabolic pathway formed by interactive reactions between genes.

　　Since the computer technique improves rapidly, the computer generated biological data and experimental results increased exponentially. There are more and more public databases provided free and huge amount of biological data for biological researchers. In recent years, many researchers utilize the data source provided by there public databases, to construct metabolic pathway, and to infer the metabolic pathway by graph theory. But these researches usually ignored the choice of start and end nodes. The biological researchers must input these nodes manually, but it may cause the fault of inferring results. Hence, the method we propose in this research is to retrieve the nodes of reference pathway of KEGG pathway database, to ensure the nodes we retrieved are all in the similar function. We utilize k-shortest paths to infer the metabolic pathway in the metabolic pathway network which constructed by compounds and reactions. Finally, the candidated metabolic pathways we inferred are provided for the biological researcher to further analyze.

第一章 緒論..................................................................................................................1
第一節 研究背景與動機......................................................................................1
第二節 研究目的..................................................................................................3
第三節 研究範圍與限制......................................................................................4
第四節 論文大綱..................................................................................................4
第二章 文獻探討..........................................................................................................6
第一節 生物相關資訊..........................................................................................6
2.1.1 Reaction .............................................................................................6
2.1.2 EC（Enzyme Commission） ............................................................7
2.1.3 KEGG ................................................................................................7
2.1.4 NCBI..................................................................................................8
第二節 最短路徑問題..........................................................................................9
第三節 新陳代謝途徑相關研究........................................................................11
第三章 研究方法........................................................................................................16
第一節 研究架構................................................................................................16
第二節 建構新陳代謝圖形-Metabolic Network Graph Constructing..............17
3.2.1 Compound 及Reaction 資料集擷取...............................................18
3.2.2 文字剖析工作..................................................................................19
3.2.3 定義Compounds 成本....................................................................20
第三節 擷取新陳代謝路徑節點- Extracting Pathway Nodes.........................23
第四節 推論新陳代謝途徑- Pathway Finding ................................................25
第四章 實作驗證........................................................................................................28
第一節 系統建構................................................................................................28
V
4.1.1 系統架構..........................................................................................28
第二節 系統驗證................................................................................................30
第三節 實驗結果與分析....................................................................................32
第四節 討論........................................................................................................40
第五章 結論與未來研究方向....................................................................................41
第一節 研究結果與貢獻....................................................................................41
第二節 未來研究方向........................................................................................42
參考文獻......................................................................................................................43
                                    

Arita, M. (2000). Metabolic reconstruction using shortest paths. Simulation Practice and Theory, 8(1-2), 109-125.
Altermann, E., & Klaenhammer, T.R. (2005). PathwayVoyager: pathway mapping using the Kyoto Encyclopedia of Genes and Genomes (KEGG) database. BMC Genomics, 6(1), 60-66.
Baeza-Yates, R., & Ribeiro-Neto, B. (1999) Modern Information Retrieval. New York: The ACM Press.
Chen, M., & Hofestadt, R. (2004). Web-based information retrieval system for the prediction of metabolic pathways. IEEE transactions on NanoBioscience, 3(3), 192-199.
Cores, D., Couche, F., Wodak, S.J., & van Helden, J. (2005). Metabolic PathFinding: inferring relevant pathways in biochemical networks. Nucleic Acids Research, 33, W326-W330.
Doom, T., Raymer, M., & Krane, D. (2004). Bioinformatics. Potentials IEEE, 23(1), 24-27.
Goesmann, A., Haubrock, M., Meyer, F., Kalinowski, J., & Giegerich, R. (2002). PathFinder: reconstruction and dynamic visualization of metabolic pathways. Bioinformatics, 18(1), 124-129.
Kanehisa, M., Goto, S., Kawashima, S., & Nakaya, A. (2002). The KEGG databases at GenomeNet. Nucleic Acids Research, 30, 42-46.
Kanehisa, M., Goto, S., Kawashima, S., Okuno, Y., & Hattori, M. (2004). The KEGG resources for deciphering the genome. Nucleic Acids Research, 32, 277-280.
Kim, W., Aronson, A.R., & Wilbur, W.J. (2001). Automatic MeSH term assignment and quality assessment. Journal of the American Medical Informatics Association, suppl., 319-323.
Kuffer, R., Zimmer, R., & Lengauer, T. (2000). Pathway analysis in metabolic databases via differential metabolic display (DMD). Bioinformatics, 16(9), 825-836.
McShan, D.C., Rao, S., & Shah, I. (2003). PathMiner: predicting metabolic pathways by heuristic search. Bioinformatics, 19(13), 1692-1698.
Paley, S.M., & Karp P.D. (2002). Evaluation of computational metabolic-pathway predictions for Helicobacter pylori. Bininformatics, 18(5), 715-724.
Shatkay, H., Edwards, S., & Boguski, M. (2002). Information retrieval meets gene analysis. IEEE Intelligent Systems, Special Issue on Intelligent Systems in Biology, 17(2), 45-53.
Simeonidis, E., Rison, S.C.G., Thornton, J.M., Bogle, I.D.L., & Papageorgiou, L.G. (2003). Analysis of metabolic networks using a pathway distance metric through linear programming. Metabolic Engineering, 5(3), 211-219.
Schomburg, D., Rahman, S.A., Advani, P., Schunk, R., & Schrader R. (2005). Metabolic pathway analysis web service (Path Hunter Tool at CUBIC). Bioinformatics, 21(7), 1189-1193.
Tao, Y.C., & Leibel, R.L. (2002). Identifying functional relationships among human genes by systematic analysis of biological literature. BMC Bioinformatics, 3(16), 1-9.
Yen, J.Y. (1971). Finding the K shortest loopless paths in a network. Management Science, 17(11), 712-716.

校內：2007-06-27公開
校外：2007-06-27公開

簡易檢索 / 詳目顯示

相關論文