Nir Atias
Skip Abstract Section
Abstract
Examining tools that provide valuable insight about molecular components within a cell.
- Aebersold, R., Mann, M. Mass spectrometry-based proteomics. Nature 422 (2003), 198--207.Google Scholar
Cross Ref
- Alon, N., Yuster, R., Zwick, U. Color-coding. J. ACM 42 (July 1995), 844--856. Google ScholarDigital Library
- Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J. Basic local alignment search tool. J. Mol. Biol. 215, 3 (Oct. 1990), 403--410.Google ScholarCross Ref
- Bandyopadhyay, S., Sharan, R., Ideker, T. Systematic identification of functional orthologs based on protein network comparison. Genome Res. 16, 3 (Mar. 2006), 428--435.Google ScholarCross Ref
- Banks, E., Nabieva, E., Peterson, R., Singh, M. Netgrep: fast network schema searches in interactomes. Genome Biol. 9 (2008), R138.Google ScholarCross Ref
- Betzler, N., Fellows, M.R., Komusiewicz, C., Niedermeier, R. Parameterized algorithms and hardness results for some graph motif problems. In Proceedings of the 19th annual symposium on Combinatorial Pattern Matching (Berlin, Heidelberg, 2008), CPM '08, Springer-Verlag, 31--43. Google ScholarDigital Library
- Bruckner, S., Hffner, F., Karp, R.M., Shamir, R., Sharan, R. Topology-free querying of protein interaction networks. J. Comput. Biol. 17, 3 (Mar. 2010), 237--252.Google ScholarCross Ref
- Deng, M., Sun, F., Chen, T. Assessment of the reliability of protein--protein interactions and protein function prediction. In Proceedings of the 8th Pacific Symposium on Biocomputing (2003), 140--151.Google Scholar
- Dost, B., Shlomi, T., Gupta, N., Ruppin, E., Bafna, V., Sharan, R. QNet: a tool for querying protein interaction networks. J. Comput. Biol. 15, 7 (Sep. 2008), 913--925.Google ScholarCross Ref
- Fields, S. High-throughput two-hybrid analysis: the promise and the peril. FEBS J. 272 (2005), 5391--5399.Google ScholarCross Ref
- Garey, M., Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., San Francisco, 1979. Google ScholarDigital Library
- Giot, L., Bader, J., Brouwer, C., Chaudhuri, A., Kuang, B., Li, Y., Hao, Y., Ooi, C., Godwin, B., Vitols, E., Vijayadamodar, G., Pochart, P., Machineni, H., Welsh, M., Kong, Y., Zerhusen, B., Malcolm, R., Varrone, Z., Collis, A., Minto, M., Burgess, S., McDaniel, L., Stimpson, E., Spriggs, F., Williams, J., Neurath, K., Ioime, N., Agee, M., Voss, E., Furtak, K., Renzulli, R., Aanensen, N., Carrolla, S., Bickelhaupt, E., Lazovatsky, Y., DaSilva, A., Zhong, J., Stanyon, C.A., Finley, R.L., Jr, White, K., Braverman, M., Jarvie, T., Gold, S., Leach, M., Knight, J., Shimkets, R., McKenna, M., Chant, J., Rothberg, J. A protein interaction map of Drosophila melanogaster. Science 302, 5651 (2003), 1727--1736.Google ScholarCross Ref
- Hirsh, E., Sharan, R. Identification of conserved protein complexes based on a model of protein network evolution. Bioinformatics 23 (2007), e170--e176. Google ScholarDigital Library
- IBM. IBM ILOG CPLEX V12.1 user's manual for CPLEX, 2009.Google Scholar
- Ideker, T., Sharan, R. Protein networks in disease. Genome Res. 18 (2008), 644--652.Google ScholarCross Ref
- Kalaev, M., Bafna, V., Sharan, R. Fast and accurate alignment of multiple protein networks. J. Comput. Biol. 16 (2009), 989--999.Google ScholarCross Ref
- Kelley, B.P., Sharan, R., Karp, R.M., Sittler, T., Root, D.E., Stockwell, B.R., Ideker, T. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci. U.S.A. 100, 20 (Sep. 2003), 11394--11399.Google ScholarCross Ref
- Kelley, B.P., Yuan, B., Lewitter, F., Sharan, R., Stockwell, B.R., Ideker, T. PathBLAST: a tool for alignment of protein interaction networks. Nucleic Acids Res. 32, Web Server issue (Jul. 2004), W83--W88.Google Scholar
- Klau, G.W. A new graph-based method for pairwise global network alignment. BMC Bioinformatics 10, Suppl 1 (2009), S59.Google ScholarCross Ref
- Li, S., Armstrong, C., Bertin, N., Ge, H., Milstein, S., Boxem, M., Vidalain, P., Han, J.D., Chesneau, A., Hao, T., Goldberg, D., Li, N., Martinez, M., Rual, J., Lamesch, P., Xu, L., Tewari, M., Wong, S., Zhang, L., Berriz, G., Jacotot, L., Vaglio, P., Reboul, J., Hirozane-Kishikawa, T., Li, Q., Gabel, H., Elewa, A., Baumgartner, B., Rose, D., Yu, H., Bosak, S., Sequerra, R., Fraser, A., Mango, S., Saxton, W., Strome, S., Heuvel, S.V.D., Piano, F., Vandenhaute, J., Sardet, C., Gerstein, M., Doucette-Stamm, L., Gunsalus, K., Harper, J., Cusick, M., Roth, F., Hill, D., Vidal, M. A map of the interactome network of the metazoan C. elegans. Science 303, 5657 (2004), 540--543.Google ScholarCross Ref
- Mayrose, I., Shlomi, T., Rubinstein, N.D., Gershoni, J.M., Ruppin, E., Sharan, R., Pupko, T. Epitope mapping using combinatorial phage-display libraries: a graph-based algorithm. Nucleic Acids Res. 35, 1 (2007), 69--78.Google ScholarCross Ref
- Mongioví, M., Sharan, R. Global alignment of protein-protein interaction networks. Data Mining for Systems Biology. H. Mamitsuka, C. DeLisi, and M. Kanehisa, eds. Springer, 2012, in press.Google Scholar
- Ogata, H., Fujibuchi, W., Goto, S., Kanehisa, M. A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res. 28 (2000), 4021--4028.Google ScholarCross Ref
- Pellegrini, M., Marcotte, E., Thompson, M., Eisenberg, D., Yeates, T. Assigning protein functions by comparative genome analysis: protein phylogenetic profiles. Proc. Natl. Acad. Sci. U.S.A. 96 (1999), 4285--4288.Google ScholarCross Ref
- Rain, J., Selig, L., Reuse, H.D., Battaglia, V., Reverdy, C., Simon, S., Lenzen, G., Petel, F., Wojcik, J., Schachter, V., Chemama, Y., Labigne, A., Legrain, P. The protein--protein interaction map of Helicobacter pylori. Nature 409 (2001), 211--215.Google ScholarCross Ref
- Ross, C.A., Tabrizi, S.J. Huntington's disease: from molecular pathogenesis to clinical treatment. Lancet Neurol. 10, 1 (Jan. 2011), 83--98.Google ScholarCross Ref
- Rual, J.-F., Venkatesan, K., Hao, T., Hirozane-Kishikawa, T., Dricot, A., Li, N., Berriz, G.F., Gibbons, F.D., Dreze, M., Ayivi-Guedehoussou, N., Klitgord, N., Simon, C., Boxem, M., Milstein, S., Rosenberg, J., Goldberg, D.S., Zhang, L.V., Wong, S.L., Franklin, G., Li, S., Albala, J.S., Lim, J., Fraughton, C., Llamosas, E., Cevik, S., Bex, C., Lamesch, P., Sikorski, R.S., Vandenhaute, J., Zoghbi, H.Y., Smolyar, A., Bosak, S., Sequerra, R., Doucette-Stamm, L., Cusick, M.E., Hill, D.E., Roth, F.P., Vidal, M. Towards a proteomescale map of the human protein-protein interaction network. Nature 437, 7062 (Oct. 2005), 1173--1178.Google ScholarCross Ref
- Salwinski, L., Miller, C.S., Smith, A.J., Pettit, F.K., Bowie, J.U., Eisenberg, D. The database of interacting proteins: 2004 update. Nucleic Acids Res. 32, Database issue (Jan. 2004), D449--D451.Google Scholar
- Sayers, E.W., Barrett, T., Benson, D.A., Bolton, E., Bryant, S.H., Canese, K., Chetvernin, V., Church, D.M., DiCuccio, M., Federhen, S., Feolo, M., Fingerman, I.M., Geer, L.Y., Helmberg, W., Kapustin, Y., Landsman, D., Lipman, D.J., Lu, Z., Madden, T.L., Madej, T., Maglott, D.R., Marchler-Bauer, A., Miller, V., Mizrachi, I., Ostell, J., Panchenko, A., Phan, L., Pruitt, K.D., Schuler, G.D., Sequeira, E., Sherry, S.T., Shumway, M., Sirotkin, K., Slotta, D., Souvorov, A., Starchenko, G., Tatusova, T.A., Wagner, L., Wang, Y., Wilbur, W.J., Yaschenko, E., Ye, J. Database resources of the national center for biotechnology information. Nucleic Acids Res. 39, Database issue (Jan. 2011), D38--D51.Google Scholar
- Sharan, R., Ideker, T. Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24, 4 (Apr. 2006), 427--433.Google ScholarCross Ref
- Sharan, R., Ideker, T., Kelley, B., Shamir, R., Karp, R. Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. J. Comput. Biol. 12 (2005), 835--846.Google ScholarCross Ref
- Sharan, R., Suthram, S., Kelley, R.M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R.M., Ideker, T. Conserved patterns of protein interaction in multiple species. Proc. Natl. Acad. Sci. U.S.A. 102, 6 (Feb. 2005), 1974--1979.Google ScholarCross Ref
- Shlomi, T., Segal, D., Ruppin, E., Sharan, R. QPath: a method for querying pathways in a protein--protein interaction network. BMC Bioinformatics 7 (2006), 199.Google ScholarCross Ref
- Singh, R., Xu, J., Berger, B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc. Natl. Acad. Sci. U.S.A. 105, 35 (Sep. 2008), 12763--12768.Google ScholarCross Ref
- Stark, C., Breitkreutz, B.-J., Chatr-Aryamontri, A., Boucher, L., Oughtred, R., Livstone, M.S., Nixon, J., Auken, K.V., Wang, X., Shi, X., Reguly, T., Rust, J.M., Winter, A., Dolinski, K., Tyers, M. The BioGRID interaction database: 2011 update. Nucleic Acids Res. 39, Database issue (Jan. 2011), D698--D704.Google Scholar
- Stelzl, U., Worm, U., Lalowski, M., Haenig, C., Brembeck, F., Goehler, H., Stroedicke, M., Zenkner, M., Schoenherr, A., Koeppen, S., Timm, J., Mintzlaff, S., Abraham, C., Bock, N., Kietzmann, S., Goedde, A., Toksoz, E., Droege, A., Krobitsch, S., Korn, B., Birchmeier, W., Lehrach, H., Wanker, E. A human protein--protein interaction network: a resource for annotating the proteome. Cell 122 (2005), 957--968.Google ScholarCross Ref
- Uetz, P., Giot, L., Cagney, G., Mansfield, T., Judson, R., Knight, J., 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., Rothberg, J. A comprehensive analysis of protein--protein interactions in Saccharomyces cerevisiae. Nature 403, 6770 (2000), 623--627.Google ScholarCross Ref
- Yosef, N., Sharan, R., Noble, W.S. Improved network-based identification of protein orthologs. Bioinformatics 24, 16 (Aug. 2008), i200--i206. Google ScholarDigital Library
- Yu, H., Braun, P., Yildirim, M.A., Lemmens, I., Venkatesan, K., Sahalie, J., Hirozane-Kishikawa, T., Gebreab, F., Li, N., Simonis, N., Hao, T., Rual, J.-F., Dricot, A., Vazquez, A., Murray, R.R., Simon, C., Tardivo, L., Tam, S., Svrzikapa, N., Fan, C., de Smet, A.-S., Motyl, A., Hudson, M.E., Park, J., Xin, X., Cusick, M.E., Moore, T., Boone, C., Snyder, M., Roth, F.P., Barabsi, A.-L., Tavernier, J., Hill, D.E., Vidal, M. High-quality binary protein interaction map of the yeast interactome network. Science 322, 5898 (Oct. 2008), 104--110.Google ScholarCross Ref
Index Terms
- Comparative analysis of protein networks: hard problems, practical solutions
Recommendations
Comparative interactomics analysis of protein family interaction networks using PSIMAP (protein structural interactome map)
Motivation: Many genomes have been completely sequenced. However, detecting and analyzing their protein--protein interactions by experimental methods such as co-immunoprecipitation, tandem affinity purification and Y2H is not as fast as genome ...
Reviews
Sara Kalvala
This accessible and topical review article covers algorithmic contributions to the elucidation of protein-protein interactions (PPIs). These interactions present a very interesting application of graph theory, in the face of several complicating matters. We start with a large set of proteins, but the data about their interactions may be incomplete and even inaccurate. Moreover, in trying to build a network of interactions for any one species, we may have to use related information (incomplete or inaccurate) from other species, and the degree of correspondence between the nodes of these different networks is itself not easy to quantify. These challenges underlie the difficulty in developing algorithms that can deal with networks of thousands of nodes in a reasonable time. The article gives a good (albeit brief) introduction to the biological setup. It then provides, in the authors' words, "a roadmap to network comparison techniques." The interplay between heuristic approaches and exact approaches is a theme throughout the article. Other articles on this topic are targeted at biologists and therefore are more likely to provide an introduction to the toolkits available rather than the underlying algorithms. This article, on the other hand, presents the computational challenges and the gist of the approaches that are available, without the distraction of particular implementations and interfaces. The article is accessible to readers of many different backgrounds: it is neither too biological nor too mathematical. The more detailed mathematical concepts are presented as asides and in figures, making the text itself very readable. The whole article is quite short, considering it is a survey, but it provides a good introduction to a very interesting and challenging multi-disciplinary endeavor. The reference list provides a good resource for further study of this scientific challenge. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments