An integrated model for visualizing biclusters from gene expression data and PPI networks

ABSTRACT

We provide a model to integrate the visualization of biclusters extracted from gene expresion data and the underlying PPI networks. Such an integration conveys the biologically relevant interconnection between these two structures inferred from biological experiments. We model the reliabilities of the structures using directed graphs with vertex and edge weights. The resulting graphs are drawn using appropriate weighted modifications of the algorithms necessary for the layered drawings of directed graphs. We provide applications of the proposed visualization model on the S. cerevisiae dataset.

References

1. Mips. http://mips.gsf.de/genre/proj/mpact/yeast.
2. S. Barkow, S. Bleuler, A. Prelic, P. Zimmermann, and E. Zitzler. Bicat: a biclustering analysis toolbox. Bioinformatics, 22(10):1282--1283, 2006.
3. O. Bastert and C. Matuszewski. Layered drawings of digraphs. pages 87--120, 2001.
4. U. Brandes and B. Köpf. Fast and simple horizontal coordinate assignment. In Proc. of 9th International Symposium on Graph Drawing, pages 31--44, London, UK, 2002. Springer-Verlag.
5. B.-J. Breitkreutz, C. Stark, and M. Tyers. Osprey: A network visualization system. Genome Biology, 3(12):1--6, 2002.
6. O. A. Çakiroglu, C. Erten, Ö. Karatas, and M. Sözdinler. Crossing minimization in weighted bipartite graphs. Journal of Discrete Algorithms, doi:10.1016/j.jda.2008.08.003, 2008.
7. Y. Cheng and G. Church. Biclustering of expression data. In Proc. of the 8th Int. Conf. on Intelligent Systems for Molecular Biology, pages 93--103, 2000.
8. E. Coffman and R. L. Graham. Optimal scheduling for two-processor systems. Acta Informatica, 1:200--213, 1972.
9. Consortium. Gene ontology: tool for the unification of biology. the gene ontology consortium. Nature Genetics, 25(1):25--29, 2000.
10. C. Demetrescu and I. Finocchi. Combinatorial algorithms for feedback problems in directed graphs. Inf. Process. Lett., 86(3):129--136, 2003.
11. T. M. Ebbels, B. F. Buxton, and D. T. Jones. Springscape: visualisation of microarray and contextual bioinformatic data using spring embedding and an Śinformation landscapeŠ. Bioinformatics, 22(14):e99--e107, 2006.
12. C. Erten and M. Sözdinler. Biclustering expression data based on expanding localized substructures. In Proceedings of BICoB 2009, pages 224--235, 2009.
13. E. Gansner, E. Koutsofios, S. North, and K. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19(3):214--230, 1993.
14. J. P. Gonçalves, S. C. Madeira, and A. L. Oliveira. Biggests: integrated environment for biclustering analysis of time series gene expression data. BMC Research Notes, 2(124), 2009.
15. J. Hartigan. Direct clustering of a data matrix. Journal of the American Statistical Association, 67(337):123--129, 1972.
16. F. Iragne, M. Nikolski, B. Mathieu, D. Auber, and D. Sherman. Proviz: protein interaction visualization and exploration. Bioinformatics, 21(2):272--274, 2005.
17. R. Jansen, D. Greenbaum, and M. Gerstein. Relating whole-genome expression data with protein-protein interactions. Genome Research, 12(1):37--46, 2002.
18. R. M. Karp. Reducibility among combinatorial problems. pages 85--103, 1972.
19. X. Lin, M. Liu, and W. Chen. Assessing reliability of protein-protein interactions by integrative analysis of data in model organisms. BMC Bioinformatics, 10:S5, 2009.
20. S. Madeira and A. Oliveira. Biclustering algorithms for biological data analysis: A survey. IEEE/ACM Trans. on Comp. Biol. and Bioinformatics, 1(1):24--45, 2004.
21. N. Nikolov, A. Tarassov, and J. Branke. In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes. Journal Experimental Algorithmics, 10:2.7, 2005.
22. A. Prelic, S. Bleuler, P. Zimmermann, A. Wille, P. Buhlmann, W. Gruissem, L. Hennig, L. Thiele, and E. Zitzler. A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics, 22:1122--1129, 2006.
23. R. Santamaría, R. Therón, and L. Quintales. Bicoverlapper. Bioinformatics, 24(9):1212--1213, 2008.
24. P. Shannon, A. Markiel, O. Ozier, N. S. Baliga, J. T. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker. Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks. Genome Research, 13(11):2498--2504, 2003.
25. R. Sharan, A. Maron-katz, and R. Shamir. Click and expander: A system for clustering and visualizing gene expression data. Bioinformatics, 19:1787--1799, 2003.
26. K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. Systems, Man and Cybernetics, IEEE Transactions on, 11(2):109--125, Feb. 1981.
27. S. Suthram, T. Shlomi, E. Ruppin, R. Sharan, and T. Ideker. A direct comparison of protein interaction confidence assignment schemes. BMC Bioinformatics, 7(1):360, 2006.
28. J. Vlasblom, S. Wu, S. Pu, M. Superina, G. Liu, C. Orsi, and S. J. Wodak. Genepro: a cytoscape plug-in for advanced visualization and analysis of interaction networks. Bioinformatics, 22(17):2178--2179, 2006.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation theory

      • Systems theory

• Human-centered computing

• Mathematics of computing

  • Information theory