請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29703完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李瑞庭 | |
| dc.contributor.author | Chia-Ming Hsu | en |
| dc.contributor.author | 許家銘 | zh_TW |
| dc.date.accessioned | 2021-06-13T01:15:29Z | - |
| dc.date.available | 2008-07-23 | |
| dc.date.copyright | 2007-07-23 | |
| dc.date.issued | 2007 | |
| dc.date.submitted | 2007-07-19 | |
| dc.identifier.citation | [1] Asahiro, Y., Iwama, K., Yamaki, H. and Tokuyama, T., “Greedily finding a dense subgraph,” Journal of Algorithms, Vol. 34, pp. 203-221, 2000.
[2] Bader, G.D. and Hogue, C.W., “An automated method for finding molecular complexes in large protein interaction networks,” BMC Bioinformatics, Vol. 4, No. 2, 2003. [3] Barabasi, A.L. and Oltvai, Z.N., “Network biology: understanding the cell’s functional organization,” Nature Reviews Genetics, Vol. 5, pp. 101-113, 2004. [4] Barrat, A., Barthelemy, M., Pastor-Satorras, R. and Vespignani, A., “The architecture of complex weighted networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 101, pp. 3747-3752, 2004. [5] Charikar, M., “Greedy approximation algorithms for finding dense components in a graph,” Lecture Notes in Computer Science, Vol. 1913, pp. 139-152, 2000. [6] Chen, J. and Yuan, B., “Detecting functional modules in the yeast protein-protein interaction network,” Bioinformatics, Vol. 22, pp. 2283-2290, 2006. [7] Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to Algorithms, second edition, MIT Press, Cambridge, MA, 2001. [8] Deane, C.M., Salwiński, Ł., Xenarios, I. and Eisenberg, D., “Protein interactions: two methods for assessment of the reliability of high-throughput observations,” Molecular and Cellular Proteomics, Vol. 1, pp. 349-356, 2002. [9] Dubois, E., Scherens, B., Vierendeels, F., Ho, M.M., Messenguy, F. and Shears, S.B., “In Saccharomyces cerevisiae, the inositol polyphosphate kinase activity of Kcs1p is required for resistance to salt stress, cell wall integrity, and vacuolar morphogenesis,” The Journal of Biological Chemistry, Vol. 277, No. 26, pp. 23755-23763, 2002. [10] Edwards, A.M., Kus, B., Jansen, R., Greenbaum, D., Greenblatt, J. and Gerstein, M., “Bridging structural biology and genomic: assessing protein-protein interaction datasets,” Trends Genetics, Vol. 18, pp. 529-536, 2002. [11] Gagneur, J., Krause, R., Bouwmeester, T. and Casari, G.., “Modular decomposition of protein-protein interaction networks,” Genome Biology, Vol. 5, No. 8, R57, 2004. [12] Gasch, A.P. and Eisen, M.B., “Exploring the conditional coregulation of yeast gene expression through fuzzy k-means clustering,” Genome Biology, Vol. 3, No. 11, R59, 2002. [13] Gavin, A.C., Bosche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.M., Cruciat, C.M., Remor, M., Hofert, C., Schelder, M., Brajenovic, M., Ruffner, H., Merino, A., Klein, K., Hudak, M., Dickson, D., Rudi, T., Gnau1, V., Bauch, A., Bastuck, S., Huhse, B., Leutwein, C., Heurtier, M.A., Copley, R.R., Edelmann, A., Querfurth, E., Rybin, V., Drewes, G., Raida, M., Bouwmeester, T., Bork, P., Seraphin, B., Kuster, B., Neubauer, G. and Superti-Furga, G., “Functional organization of the yeast proteome by systemic analysis of protein complexes,” Nature, Vol. 415, pp. 141-147, 2002. [14] Girvan, M. and Newman, M.E., “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 99, pp. 7821-7826, 2002. [15] Goldberg, D.S. and Roth, F.R., “Assessing experimentally derived interaction in a small world,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 100, pp. 4372-4376, 2003 [16] Hartuv, E. and Shamir, R., “A clustering algorithm based on graph connectivity,” Information Processing Letters, Vol. 76, pp. 175-181, 2000. [17] Hartwell, L.H., Hopfield, J.J., Leibler, S. and Murray, A.W., “From molecular to modular cell biology,” Nature, Vol. 402, pp. c47-c52, 1999. [18] Ho, Y., Gruhler, A., Heilbut, A., Bader, G.D., Moore, L., Adams, S., Millar, A., Taylor, P., Bennett, K., Boutilier, K., Yang, L., Wolting, C., Donaldson, I., Schandorff, S., Shewnarane, J., Vo, M., Taggart, J., Goudreault, M., Muskat, B., Alfarano, C., Dewar, D., Lin, Z., Michalickova, K., Willems, A.R., Sassi, H., Nielsen, P.A., Rasmussen, K.J., Andersen, J.R., Johansen, L.E., Hansen, L.H., Jespersen, H., Podtelejnikov, A., Nielsen, E., Crawford, J., Poulsen, V., Sorensen, B.D., Matthiesen, J., Hendrickson, R.C., Gleeson, F., Pawson, T., Moran, M.F., Durocher, D., Mann, M., Hogue, C.W.V., Figeys, D. and Tyers, M., “Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry,” Nature, Vol. 415, pp. 180-183, 2002. [19] Holland, J.H., Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA, 1975. [20] Hong E.L., Balakrishnan R., Christie K.R., Costanzo M.C., Dwight S.S., Engel S.R., Fisk D.G., Hirschman J.E., Livstone M.S., Nash R., Oughtred R., Park J., Skrzypek M., Starr B., Andrada R., Binkley G., Dong Q., Hitz B.C., Miyasato S., Schroeder M., Weng S., Wong E.D., Zhu K.K., Dolinski K., Botstein D., and Cherry J.M., “Saccharomyces Genome Database,” ftp://ftp.yeastgenome.org/ yeast/, 2007. [21] Hu, H., Yan, X., Huang, Y., Han, J. and Zhou, X.J., “Mining coherent dense subgraphs across massive biological networks for functional discovery,” Bioinformatics, Vol. 21, pp. i213-i221, 2005. [22] Ito, T., Tashiro, K., Muta, S., Ozawa, R., Chiba, T., Nishizawa, M., Yamamoto, K., Kuhara, S. And Sakaki, Y., “Toward a protein-protein interaction map of the budding yeast: a comprehensive system to examine two-hybrid interactions in all possible combinations between the yeast proteins,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 97, pp. 1143-1147, 2000. [23] Jansen, R., Yu, H., Greenbaum, D., Kluger, Y., Krogan, N.J., Chung, S., Emili, A., Snyder, M., Greenblatt, J.F. and Gerstein, M., “A Bayesian networks approach for prediction protein-protein interactions from genomic data,” Science, Vol. 302, pp. 449-453, 2003. [24] King, A.D., Przulj, N. and Jurisica, I., “Protein complex prediction via cost-based clustering,” Bioinformatics, Vol. 20, pp. 3013-3020, 2004. [25] Li, W., Liu, Y., Huang, H.C., Peng, Y., Lin, Y., Ng, W.K. and Ong, K.L., “Dynamical systems for discovering protein complexes and functional modules from biological networks,” IEEE/ACM Transaction on Computational Biology and Bioinformatics (TCBB), to appear. [26] Liu, H., Styles, C.A. and Fink, G.R., “Elements of the yeast pheromone response pathway required for filamentous growth of diploids,” Science, Vol. 262, pp. 1741-1744, 1993. [27] Marcotte, E.M., Pellegrini, M., Hg, H.L., Rice, D.W., Yeates, T.O., Eisenberg, D., “Detecting protein function and protein-protein interactions from genome sequences,” Science, Vol. 285, pp. 751-753, 1999. [28] Newman, M.E., “Scientific collaboration networks II. Shortest paths, weighted networks, and centrality,” Physical Review E, Vol. 64, 016132, 2001. [29] Patil, A. and Nakamure, H., “Filtering high-throughput protein-protein interaction data using a combination of genomic features,” BMC Bioinformatics, Vol. 6, 100, 2005. [30] Pereira-Leal, J.B., Enright, A.J. and Ouzounis, C.A., “Detection of functional modules from protein interaction networks,” Proteins, Vol. 54, pp. 49-57, 2004. [31] Spirin, V. and Mirny, L.A., “Protein complexes and functional modules in molecular networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 100, pp. 12123-12128, 2003. [32] Tong, A.H., Drees, B., Nardell, G., Bader G.D., Brannetti, B., Castagnoli L., Evangelista, M., Ferracuti, S., Nelson, B., Paoluzi, S., Quondam, M., Zucconi, A., Hogue C.W., Fields, S., Boone, C. and Cesareni, G.,”A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules,” Science, Vol. 295, pp. 321-324, 2002. [33] Tornow, S. and Mewes, H.W., “Functional modules by relating protein interaction networks and gene expression,” Nucleic Acid Research, Vol. 31, No. 21, pp. 6283-6289, 2003. [34] Uetz, P., Giot, L., Cagney, G., Mansfield, T.A., Judson, R.S., Knight, J.R., Lockshon, D., Narayan, V., Srinivasan, M., Pochart, P., Qureshi-Emili, A., Li,Y., Godwin, B., Conover, D., Kalbfleisch, T., Vijayadamodar, G.., Yang, M., Johnston, M., Fields, S. and Rothberg, J.M., “A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae,” Nature, Vol. 403, pp. 623-627, 2000. [35] Van Dongen, S., “Graph clustering by flow simulation,” PhD thesis, University of Utrecht, The Netherlands, 2000. [36] Wu, L.F., Hughes, T.R., Davierwala, A.P., Robinson, M.D., Stoughton, R. and Altschuler, S.J., “Large-scale prediction of Saccharomyces cerevisiae gene function using overlapping transcriptional clusters,” Nature Genetic, Vol. 31, pp. 255-265, 2002. [37] Xenarios, I., Salwinski, L., Duan, X.J., Higney, P., Kim S. and Eisenberg, D., “DIP, the database of interacting proteins: a research tool for studying cellular networks of protein interactions,” Nucleic Acids Research, Vol.30, pp. 303-305, 2002. [38] The Yeast Protein Complex Database, http://yeast.cellzome.com/, 2007. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29703 | - |
| dc.description.abstract | 近來有許多高輸出的實驗可以幫我們偵測蛋白質之間的互動關係，利用這些資料，生物學家可以建立起蛋白質交互網路。如果可以從這些網路中找出蛋白質複合體將有助於我們瞭解生物的運作機制；因此，本論文提出了一個新的方法，這個方法包含了四個步驟。首先，我們計算網路中每個節點的加權連線數，並且選擇最高的那個節點當成種子；在第二個步驟，我們利用貪婪演算法找到一個密集的子網路；在第三個步驟裡，我們調整網路中連線的權重並且重新計算各個節點的加權連線數以及加權連線數的比例；在最後一個步驟，我們重複第一到第三步驟直到我們找不出任何密集的子網路為止。在我們的方法中，我們並不移除網路中任何的節點與連線，因此我們可以找出比CODENSE方法更多的重疊子網路，除此之外，實驗結果亦說明我們可以比CODENSE找到更多的蛋白質複合體。 | zh_TW |
| dc.description.abstract | Many high throughput experiments have been used to detect protein interactions which can be used to a protein-protein interaction network. To recognize the protein complexes in a protein-protein interaction network can help us understand the mechanisms of the biological processes. In this thesis, we proposed a novel method with four phases to mine the protein complexes in the protein-protein interaction network. First, we calculate the weighted degree for each vertex in the network and pick the vertex with the highest weighted degree as the seed vertex. Second, we find a dense subgraph based on the greedy algorithm. Third, we modify the edge weights in the network and compute the weighted degree and the ratio of weighted degree for each vertex in the network. Finally, we repeat the above phases until no more dense subgraph can be found. Our proposed method does not remove any vertex and edge as a subgraph has been found. Therefore our method can mine more overlapping subgraphs than the CODENSE method. The experiment results show that our proposed method can find more protein complexes than the CODENSE method. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T01:15:29Z (GMT). No. of bitstreams: 1 ntu-96-R94725031-1.pdf: 415420 bytes, checksum: e7c753f18a4e3c931f8eb0a46c50c955 (MD5) Previous issue date: 2007 | en |
| dc.description.tableofcontents | Tables of Contents i
List of Figures ii List of Tables iii Chapter 1 Introduction 1 Chapter 2 Preliminaries and Problem Definitions 4 Chapter 3 Our Proposed Method 7 3.1 The procedure of finding a dense subgraph 7 3.2 The procedure of choosing a seed vertex 7 3.3 The procedure of growing a subgraph 9 3.4 Weight modification 11 3.5 The ratio of weighted degree 12 3.6 The proposed method 13 3.7 An example 14 Chapter 4 Performance Analysis 17 4.1 Dataset and parameter settings 17 4.2 Performance evaluation for the first experiment 18 4.3 Performance evaluation for the second experiment 21 4.4 Discovering biological function modules 22 Chapter 5 Concluding Remarks 24 References 25 | |
| dc.language.iso | en | |
| dc.subject | 重疊的密集子網路 | zh_TW |
| dc.subject | 蛋白質交互網路 | zh_TW |
| dc.subject | 蛋白質複合體 | zh_TW |
| dc.subject | 貪婪演算法 | zh_TW |
| dc.subject | protein-protein interaction network | en |
| dc.subject | overlapping dense subgraph | en |
| dc.subject | greedy algorithm | en |
| dc.subject | protein complex | en |
| dc.title | 由蛋白質交互網路中探勘可重疊之密集子網路 | zh_TW |
| dc.title | Mining Dense Overlapping Subgraphs in Weighted Protein-Protein Interaction Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 呂永和,苑守慈 | |
| dc.subject.keyword | 蛋白質交互網路,蛋白質複合體,貪婪演算法,重疊的密集子網路, | zh_TW |
| dc.subject.keyword | protein-protein interaction network,protein complex,greedy algorithm,overlapping dense subgraph, | en |
| dc.relation.page | 29 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2007-07-20 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-96-1.pdf 未授權公開取用 | 405.68 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。