A Review on Applications of Graph Theory in Network Analysis of Biological Processes

References

• Adamcsek, B., Palla, G., Farkas, I. J., Derenyi, I., & Vicsek, T. (2006). CFinder: locating cliques and overlapping modules in biological networks. Bioinformatics, 22, 1021–1023.
   PubMed Web of Science ®Google Scholar
• Albert, R., Jeong, H., & Barabási, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406, 378–382.
   PubMed Web of Science ®Google Scholar
• Aluru, M., Zola, J., Nettleton, D., & Aluru, S. (2013). Reverse engineering and analysis of large genome-scale gene networks. Nucleic Acids Research, 41, e24.
   PubMed Web of Science ®Google Scholar
• Babu, M. M., Luscombe, N. M., Aravind, L., Gerstein, M., & Teichmann, S. A. (2004). Structure and evolution of transcriptional regulatory networks. Current opinion in structural biology, 14, 283–291.
   PubMed Web of Science ®Google Scholar
• Barabási, A.-L., & Oltvai, Z. N. (2004). Network biology: understanding the cell's functional organization. Nature Reviews Genetics, 5, 101–113.
   PubMed Web of Science ®Google Scholar
• Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509–512.
   PubMed Web of Science ®Google Scholar
• Borate, B. R., Chesler, E. J., Langston, M. A., Saxton, A. M., & Voy, B. H. (2009). Comparison of threshold selection methods for microarray gene co-expression matrices. BMC Research Notes, 2, 240.
   PubMedGoogle Scholar
• Brandes, U. (2001). A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25, 163–177.
   Web of Science ®Google Scholar
• Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70, 066111.
   PubMed Web of Science ®Google Scholar
• Dandekar, T., Snel, B., Huynen, M., & Bork, P. (1998). Conservation of gene order: A fingerprint of proteins that physically interact. Trends in Biochemical Sciences, 23, 324–328.
   PubMed Web of Science ®Google Scholar
• del Sol, A., & O'Meara, P. (2005). Small-world network approach to identify key residues in protein-protein interaction. Proteins: Structure, Function, and Bioinformatics, 58, 672–682.
   PubMed Web of Science ®Google Scholar
• Dongen, S., & Abreu-Goodger, C. (2012). Using MCL to Extract Clusters from Networks. In J.Helden, A.Toussaint, & D.Thieffry (Eds.), Bacterial Molecular Networks (Vol. 804, pp. 281–295). New York: Springer.
   Google Scholar
• Dongen, S. V. (2000). Graph clustering by flow simulation (PhD thesis). University of Utrecht.
   Google Scholar
• Enright, A. J., Van Dongen, S., & Ouzounis, C. A. (2002). An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research, 30, 1575–1584.
   PubMed Web of Science ®Google Scholar
• Erdos, P., & Rényi, A. (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17–61.
   Google Scholar
• Fortunato, S. (2010). Community detection in graphs. Physics Reports-Review Section of Physics Letters, 486, 75–174.
   Web of Science ®Google Scholar
• Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40, 35–41.
   Google Scholar
• Freeman, L. C., Borgatti, S. P., & White, D. R. (1991). Centrality in valued graphs: A measure of betweenness based on network flow. Social Networks, 13, 141–154.
   Web of Science ®Google Scholar
• Gabr, H., Dobra, A., & Kahveci, T. (2012). From uncertain protein interaction networks to signaling pathways through intensive color coding. Pacific Symposium Biocomputing, 111–122.
   Google Scholar
• Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99, 7821–7826.
   PubMed Web of Science ®Google Scholar
• Goh, K.-I., Cusick, M. E., Valle, D., Childs, B., Vidal, M., & Barabasi, A.-L. (2007). The human disease network. Proceedings of the National Academy of Sciences, 104, 8685–8690.
   PubMed Web of Science ®Google Scholar
• Guare, J. (1990). Six degrees of separation: A play. Random House LLC.
   Google Scholar
• Hahn, M. W., & Kern, A. D. (2005). Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks. Molecular Biology and Evolution, 22, 803–806.
   PubMed Web of Science ®Google Scholar
• Hintze, A., & Adami, C. (2008). Evolution of complex modular biological networks. PLOS Computational Biology, 4, e23.
   PubMed Web of Science ®Google Scholar
• Holme, P., Kim, B. J., Yoon, C. N., & Han, S. K. (2002). Attack vulnerability of complex networks. Physical Review E, 65, 056109.
   Web of Science ®Google Scholar
• Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000). The large-scale organization of metabolic networks. Nature, 407, 651–654.
   PubMed Web of Science ®Google Scholar
• Jeong, H., Oltvai, Z. N., & Barabási, A.-L. (2002). Prediction of protein essentiality based on genomic data. ComPlexUs, 1, 19–28.
   Google Scholar
• Jiang, W., Li, X., Rao, S., Wang, L., Du, L., Li, C., … Yang, B. (2008). Constructing disease-specific gene networks using pair-wise relevance metric: application to colon cancer identifies interleukin 8, desmin and enolase 1 as the central elements. BMC Systems Biology, 2, 72.
   PubMed Web of Science ®Google Scholar
• Joy, M. P., Brock, A., Ingber, D. E., & Huang, S. (2005). High-betweenness proteins in the yeast protein interaction network. BioMed Research International, 2005, 96–103.
   Google Scholar
• Kochen, M. (1989). The small world. Norwood: NJAblex.
   Google Scholar
• Koschützki, D., & Schreiber, F. (2004). Comparison of Centralities for Biological Networks. In German Conference on Bioinformatics (pp. 199–206)
   Google Scholar
• Krzywinski, M., Birol, I., Jones, S. J., & Marra, M. A. (2012). Hive plots—rational approach to visualizing networks. Briefings in Bioinformatics, 13, 627–644.
   PubMed Web of Science ®Google Scholar
• Lancichinetti, A., & Fortunato, S. (2009a). Community detection algorithms: a comparative analysis. Physical Review E Statistical Nonlinear and Soft Matter Physics, 80, 056117.
   PubMed Web of Science ®Google Scholar
• Lancichinetti, A., & Fortunato, S. (2009b). Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E Statistical Nonlinear and Soft Matter Physics, 80, 016118.
   Web of Science ®Google Scholar
• Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E Statistical Nonlinear and Soft Matter Physics, 78, 046110.
   Web of Science ®Google Scholar
• Liu, G., Wong, L., & Chua, H. N. (2009). Complex discovery from weighted PPI networks. Bioinformatics, 25, 1891–1897.
   PubMed Web of Science ®Google Scholar
• Luce, R. D., & Perry, A. D. (1949). A method of matrix analysis of group structure. Psychometrika, 14, 95–116.
   PubMed Web of Science ®Google Scholar
• Managbanag, J. R., Witten, T. M., Bonchev, D., Fox, L. A., Tsuchiya, M., Kennedy, B. K., … Lehner, B. (2008). Shortest-path network analysis is a useful approach toward identifying genetic determinants of longevity. PLoS ONE, 3, e3802.
   PubMed Web of Science ®Google Scholar
• Manfield, I. W., Jen, C.-H., Pinney, J. W., Michalopoulos, I., Bradford, J. R., Gilmartin, P. M., & Westhead, D. R. (2006). Arabidopsis Co-expression Tool (ACT): web server tools for microarray-based gene expression analysis. Nucleic Acids Research, 34, W504–W509.
   PubMed Web of Science ®Google Scholar
• Maslov, S., & Sneppen, K. (2002). Specificity and stability in topology of protein networks. Science Signaling, 296, 910.
   Google Scholar
• Merris, R. (1994). Laplacian matrices of graphs: A survey. Linear Algebra and Its Applications, 197–198, 143–176.
   Web of Science ®Google Scholar
• Milgram, S. (1967). The small world problem. Psychology Today, 2, 60–67.
   Google Scholar
• Mohyedinbonab, E., Ghasemi, O., Jamshidi, M., & Yu-Fang, J. (2013). Time delay estimation in gene regulatory networks. In System of Systems Engineering (SoSE), 2013 8th International Conference on (pp. 302–307)
   Google Scholar
• Nabieva, E., Jim, K., Agarwal, A., Chazelle, B., & Singh, M. (2005). Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics, 21, i302–i310.
   PubMed Web of Science ®Google Scholar
• Nepusz, T., Yu, H., & Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature methods, 9, 471–472.
   PubMed Web of Science ®Google Scholar
• Newman, M. (2008). The mathematics of networks. The new palgrave encyclopedia of economics, 2, 1–12.
   Google Scholar
• Newman, M. E. (2002). Assortative mixing in networks. Physical Review Letters, 89, 208701.
   PubMed Web of Science ®Google Scholar
• Newman, M. E. (2004). Fast algorithm for detecting community structure in networks. Physical Review E, 69, 066133.
   PubMed Web of Science ®Google Scholar
• Newman, M. E., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69, 026113.
   PubMed Web of Science ®Google Scholar
• Newman, M. E. J. (2001). Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E, 64, 016132.
   Google Scholar
• Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103, 8577–8582.
   PubMed Web of Science ®Google Scholar
• Newman, M. J. (2005). A measure of betweenness centrality based on random walks. Social Networks, 27, 39–54.
   Web of Science ®Google Scholar
• Ozgur, A., Vu, T., Erkan, G., & Radev, D. R. (2008). Identifying gene-disease associations using centrality on a literature mined gene-interaction network. Bioinformatics, 24, i277–i285.
   PubMed Web of Science ®Google Scholar
• Perkins, A. D., & Langston, M. A. (2009). Threshold selection in gene co-expression networks using spectral graph theory techniques. BMC Bioinformatics, 10, S4.
   PubMed Web of Science ®Google Scholar
• Pinney, J. W., & Westhead, D. R. (2006). Betweenness-based decomposition methods for social and biological networks. Interdisciplinary Statistics and Bioinformatics, 87–90.
   Google Scholar
• Pons, P., & Latapy, M. (2005). Computing communities in large networks using random walks. In P.Yolum, T.Güngör, F.Gürgen, & C.Özturan (Eds.), Computer and Information Sciences-ISCIS 2005 (pp. 284–293). Springer Berlin Heidelberg.
   Google Scholar
• Potapov, A. P., Voss, N., Sasse, N., & Wingender, E. (2005). Topology of mammalian transcription networks. Genome Informatics Series, 16, 270.
   PubMedGoogle Scholar
• Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 101, 2658–2663.
   PubMed Web of Science ®Google Scholar
• Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., & Barabási, A.-L. (2002). Hierarchical organization of modularity in metabolic networks. Science, 297, 1551–1555.
   PubMed Web of Science ®Google Scholar
• Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105, 1118–1123.
   PubMed Web of Science ®Google Scholar
• Schmith, J. C., Lemke, N., Mombach, J., Benelli, P., Barcellos, C. K., & Bedin, G. B. (2005). Damage, connectivity and essentiality in protein-protein interaction networks. Physica A: Statistical Mechanics and its Applications, 349, 675–684.
   Web of Science ®Google Scholar
• Sedgewick, R. (1988). Algorithms (2nd ed.). Reading, MA: Addison-Wesley.
   Google Scholar
• Shannon, P., Markiel, A., Ozier, O., Baliga, N. S., Wang, J. T., Ramage, D., et al. (2003). Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Research, 13, 2498–2504.
   PubMed Web of Science ®Google Scholar
• Shlomi, T., Segal, D., Ruppin, E., & Sharan, R. (2006). QPath: A method for querying pathways in a protein-protein interaction network. BMC Bioinformatics, 7, 199.
   PubMed Web of Science ®Google Scholar
• Spielman, D. A., The adjacency matrix and the nth eigenvalue. [Online]. Retrieved from: http://www.cs.yale.edu/homes/spielman/561/lect03-12.pdf.
   Google Scholar
• Tong, A. H. Y., Lesage, G., Bader, G. D., Ding, H., Xu, H., Xin, X., et al. (2004). Global mapping of the yeast genetic interaction network. Science Signaling, 303, 808.
   Google Scholar
• Vendruscolo, M., Dokholyan, N., Paci, E., & Karplus, M. (2002). Small-world view of the amino acids that play a key role in protein folding. Physical Review E, 65, 061910.
   Web of Science ®Google Scholar
• Vlasblom, J., & Wodak, S. J. (2009). Markov clustering versus affinity propagation for the partitioning of protein interaction graphs. BMC Bioinformatics, 10, 99.
   PubMed Web of Science ®Google Scholar
• Vogelstein, B., Lane, D., & Levine, A. J. (2000). Surfing the p53 network. Nature, 408, 307–310.
   PubMed Web of Science ®Google Scholar
• Voy, B. H., Scharff, J. A., Perkins, A. D., Saxton, A. M., Borate, B., Chesler, E. J., … Langston, M. A. (2006). Extracting Gene Networks for Low-Dose Radiation Using Graph Theoretical Algorithms. PLOS Computational Biology, 2, e89.
   PubMed Web of Science ®Google Scholar
• Wagner, A. (2001a). How to reconstruct a large genetic network from n gene perturbations in fewer than n2 easy steps. Bioinformatics, 17, 1183–1197.
   PubMed Web of Science ®Google Scholar
• Wagner, A. (2001b). The yeast protein interaction network evolves rapidly and contains few redundant duplicate genes. Molecular Biology and Evolution, 18, 1283–1292.
   PubMed Web of Science ®Google Scholar
• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.
   PubMed Web of Science ®Google Scholar
• Witten, T. M., & Bonchev, D. (2007). Predicting aging/longevity-related genes in the nematodecaenorhabditis elegans. Chemistry & Biodiversity, 4, 2639–2655.
   PubMed Web of Science ®Google Scholar
• Wolfe, C. J., Kohane, I. S., & Butte, A. J. (2005). Systematic survey reveals general applicability of “guilt-by-association” within gene coexpression networks. BMC Bioinformatics, 6, 227.
   PubMed Web of Science ®Google Scholar
• Wuchty, S. (2001). Scale-free behavior in protein domain networks. Molecular Biology and Evolution, 18, 1694–1702.
   PubMed Web of Science ®Google Scholar
• Yook, S. H., Oltvai, Z. N., & Barabási, A. L. (2004). Functional and topological characterization of protein interaction networks. Proteomics, 4, 928–942.
   PubMed Web of Science ®Google Scholar
• Yoon, J., Blumer, A., & Lee, K. (2006). An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality. Bioinformatics, 22, 3106–3108.
   PubMed Web of Science ®Google Scholar
• Yu, H., & Gerstein, M. (2006). Genomic analysis of the hierarchical structure of regulatory networks. Proceedings of the National Academy of Sciences, 103, 14724–14731.
   PubMed Web of Science ®Google Scholar
• Yu, H., Greenbaum, D., Lu, H. X., Zhu, X., & Gerstein, M. (2004). Genomic analysis of essentiality within protein networks. RNA, 71, 817–846.
   Google Scholar
• Yu, H., Kim, P. M., Sprecher, E., Trifonov, V., & Gerstein, M. (2007). The importance of bottlenecks in protein networks: Correlation with gene essentiality and expression dynamics. PLOS Computational Biology, 3, e59.
   PubMed Web of Science ®Google Scholar
• Zaslavskiy, M., Bach, F., & Vert, J.-P. (2009). Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics, 25, i259–1267.
   PubMed Web of Science ®Google Scholar
• Zhang, B., & Horvath, S. (2005). A general framework for weighted gene co-expression network analysis. Statistical Applications in Genetics and Molecular Biology, 4, 1128.
   Web of Science ®Google Scholar
• Zhang, H., Song, X., Wang, H., & Zhang, X. (2010). MIClique: an algorithm to identify differentially coexpressed disease gene subset from microarray data. BioMed Research International, 2009, 9.
   Google Scholar
• Zhou, H. J. (2003). Distance, dissimilarity index, and network community structure. Physical Review E, 67, 061901.
   Web of Science ®Google Scholar
• Zhou, H. J., & Lipowsky, R. (2004). Network Brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities. Computational Science - Iccs 2004, Pt 3, Proceedings, 3038, 1062–1069.
   Google Scholar