Inferring Mechanisms of Compensation from E-MAP and SGA Data Using Local Search Algorithms for Max Cut

1. Adams, C., Kamakaka, R.: Chromatin assembly: biochemical identities and genetic redundancy. Current Opinion in Genetics and Development 9, 185–190 (1999)

   Article  Google Scholar 

2. Bandyopadhyay, S., Kelley, R., Krogan, N.: Functional maps of protein complexes from quantitative genetic interaction data. PLoS Computational Biology (January 2008)

   Google Scholar 

3. Berriz, G.F., King, O.D., Bryant, B., Sander, C., Roth, F.P.: Characterizing gene sets with FuncAssociate. Bioinformatics 19(18), 2502–2504 (2003)

   Article  Google Scholar 

4. Boone, C., Bussey, H., Andrews, B.J.: Exploring genetic interactions and networks with yeast. Nature Reviews Genetics 8, 437–449 (2007)

   Article  Google Scholar 

5. Brady, A., Maxwell, K., Daniels, N., Cowen, L.: Fault tolerance in protein interaction networks: Stable bipartite subgraphs and redundant pathways. PLoS ONE 4(4), e5364 (2009)

   Article  Google Scholar 

6. Callebaut, I., Mornon, J.-P.: From BRCA1 to RAP1: A widespread BRCT module closely associated with DNA repair. FEBS Letters 400, 25–30 (1997)

   Article  Google Scholar 

7. Carr, A.: DNA structure dependent checkpoints as regulators of DNA repair. DNA Repair 1, 983–994 (2002)

   Article  Google Scholar 

8. Collins, S., Miller, K., Maas, N., Roguev, A.: Functional dissection of protein complexes involved in yeast chromosome biology using a genetic interaction map. Nature (January 2007)

   Google Scholar 

9. Costanzo, M., Baryshnikova, A., Bellay, J., Kim, Y., Spear, E.D., Sevier, C.S., Ding, H., Koh, J.L.Y., Toufighi, K., Mostafavi, S., Prinz, J., Onge, R.P.S., VanderSluis, B., Makhnevych, T., Vizeacoumar, F.J., Alizadeh, S., Bahr, S., Brost, R.L., Chen, Y., Cokol, M., Deshpande, R., Li, Z., Lin, Z., Liang, W., Marback, M., Paw, J., Luis, B.S., Shuteriqi, E., Tong, A.H.Y., van Dyk, N., Wallace, I.M., Whitney, J.A., Weirauch, M.T., Zhong, G., Zhu, H., Houry, W.A., Brudno, M., Ragibizadeh, S., Papp, B., Pál, C., Roth, F.P., Giaever, G., Nislow, C., Troyanskaya, O.G., Bussey, H., Bader, G.D., Gingras, A., Morris, Q.D., Kim, P.M., Kaiser, C.A., Myers, C.L., Andrews, B.J., Boone, C.: The genetic landscape of a cell. Science 327(5964), 425–431 (2010)

   Article  Google Scholar 

10. D’Amours, D., Jackson, S.: The MRE11 complex: at the crossroads of DNA repair and checkpoint signalling. Nature Reviews Molecular Cell Biology 3, 317–327 (2002)

    Article  Google Scholar 

11. Fiedler, D., Braberg, H., Mehta, M., Chechik, G., Cagney, G.: Functional organization of the S. cerevisiae phosphorylation network. Cell (January 2009)

    Google Scholar 

12. Green, E., Antcsak, A., Bailey, A., Franco, A., Wu, K., Yates, J., Kaufman, P.: Replication-independent histone deposition by the HIR complex and asf1. Current Biology 15, 2044–2049 (2005)

    Article  Google Scholar 

13. Hescott, B.J., Leiserson, M.D.M., Slonim, D.K., Cowen, L.J.: Evaluating between-pathway models with expression data. Journal of Computational Biology 17(3), 477–487 (2010)

    Article  Google Scholar 

14. Jaccard, P.: Nouvelles recherches sur la distribution florale. Bull. Soc. Vaudoise Sci. Nat. 44, 223–270 (1908)

    Google Scholar 

15. Jaimovich, A., Rinott, R., Schuldiner, M., Margalit, H., Friedman, N.: Modularity and directionality in genetic interaction maps. Bioinformatics 26(12), i228–i236 (2010)

    Article  Google Scholar 

16. Kelley, D., Kingsford, C.: Extracting between-pathway models from E-MAP interactions using expected graph compression. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol. 6044, pp. 248–262. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

17. Kelley, R., Ideker, T.: Systematic interpretation of genetic interactions using protein networks. Nature Biotechnology 23(5), 561–566 (2005), doi:10.1038/nbt1096 PMID:15877074

    Article  Google Scholar 

18. Krogan, N., Keogh, M.-C., Datta, N., Sawa, C., Ryan, O., Ding, H., Haw, R., Pootoolal, J., Tong, A., Canadien, V., Richards, D., Wu, X., Emili, A., Hughes, T., Buratowski, S., Greenblatt, J.: A Snf2 family ATPase complex required for the recruitment of the histone H2A variant Htz1. Molecular Cell 12, 1565–1576 (2003)

    Article  Google Scholar 

19. Loebl, M.: Efficient maximal cubic graph cuts. In: Leach Albert, J., Monien, B., Rodríguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 351–362. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

20. Ma, X., Tarone, A., Li, W.: Mapping genetically compensatory pathways from synthetic lethal interactions in yeast. PLoS One 3(4), e1922 (2008), doi:10.1371/journal.pone.0001922 PMCID: PMC2275788

    Article  Google Scholar 

21. Pan, X., Ye, P., Tuan, D., Wang, X., Bader, J., Boeke, J.: A DNA integrity network in the yeast Saccharomyces cerevisiae. Cell 124, 1069–1081 (2006)

    Article  Google Scholar 

22. Poljak, S.: Integer linear programs and local search for max-cut. SIAM J. Comput. 24(4), 822–839 (1995)

    Article  MathSciNet  MATH  Google Scholar 

23. Real, R., Vargas, J.: The probabilistic basis of Jaccard’s index of similarity. Syst. Biol. 45(3), 380–385 (1996)

    Article  Google Scholar 

24. Roguev, A., Bandyopadhyay, S., Zofall, M., Zhang, K., Fischer, T., Collins, S.R., Qu, H., Shales, M., Park, H., Hayles, J., Hoe, K., Kim, D., Ideker, T., Grewal, S.I., Weissman, J.S., Krogan, N.J.: Conservation and rewiring of functional modules revealed by an epistasis map in fission yeast. Science 322(5900), 405–410 (2008)

    Article  Google Scholar 

25. Schäffer, A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20, 56–87 (1991)

    Article  MathSciNet  MATH  Google Scholar 

26. Schuldiner, M., Collins, S.R., Thompson, N.J., Denic, V., Bhamidipati, A., Punna, T., Ihmels, J., Andrews, B., Boone, C., Greenblatt, J.F., Weissman, J.S., Krogan, N.J.: Exploration of the function and organization of the yeast early secretory pathway through an epistatic miniarray profile. Cell 123(3), 507–519 (2005)

    Article  Google Scholar 

27. Stark, C., Breitkreutz, B.-J., Reguly, T., Boucher, L., Breitkreutz, A., Tyers, M.: BioGRID: a general repository for interaction datasets. Nucleic Acids Research 34(suppl 1), D535–D539 (2005)

    Google Scholar 

28. Taipale, M., Jarosz, D., Lindquist, S.: HSP90 at the hub of protein homeostasis: emerging mechanistic insights. Nature Reviews Molecular Cell Biology 11, 515–528 (2010)

    Article  Google Scholar 

29. Tong, A.H.Y., Lesage, G., Bader, G.D., Ding, H., Xu, H., Xin, X., Young, J., Berriz, G.F., Brost, R.L., Chang, M., Chen, Y., Cheng, X., Chua, G., Friesen, H., Goldberg, D.S., Haynes, J., Humphries, C., He, G., Hussein, S., Ke, L., Krogan, N., Li, Z., Levinson, J.N., Lu, H., Menard, P., Munyana, C., Parsons, A.B., Ryan, O., Tonikian, R., Roberts, T., Sdicu, A.-M., Shapiro, J., Sheikh, B., Suter, B., Wong, S.L., Zhang, L.V., Zhu, H., Burd, C.G., Munro, S., Sander, C., Rine, J., Greenblatt, J., Peter, M., Bretscher, A., Bell, G., Roth, F.P., Brown, G.W., Andrews, B., Bussey, H., Boone, C.: Global mapping of the yeast genetic interaction network. Science 303(5659), 808–813 (2004)

    Article  Google Scholar 

30. Ulitsky, I., Krogan, N., Shamir, R.: Towards accurate imputation of quantitative genetic interactions. Genome Biology (January 2009)

    Google Scholar 

31. Ulitsky, I., Shamir, R.: Pathway redundancy and protein essentiality revealed in the S. cerevisiae interaction networks. Molecular Systems Biology 3(104) (2007), PMCID: PMC1865586

    Google Scholar 

32. Ulitsky, I., Shlomi, T., Kupiec, M., Shamir, R.: From E-MAPs to module maps: dissecting quantitative genetic interactions using physical interactions. Molecular Systems Biology (January 2008)

    Google Scholar 

Download references