Semi-bipartite Graph Visualization for Gene Ontology Networks

Xu, Kai and Williams, Rohan and Hong, Seok-Hee and Liu, Qing and Zhang, Ji (2010) Semi-bipartite Graph Visualization for Gene Ontology Networks. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 244-255 (Official URL:

Full text not available from this repository.


In this paper we propose three layout algorithms for semibipartite graphs—bipartite graphs with edges in one partition—that emerge from microarray experiment analysis. We also introduce a method that effectively reduces visual complexity by removing less informative nodes. The drawing quality and running time are evaluated with five real-world datasets, and the results show significant reduction in crossing number and total edge length. All the proposed methods are available in visualization package GEOMI [1], and are well received by domain users.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_24
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:1114

Repository Staff Only: item control page


Ahmed, A., Dwyer, T., Forster, M., Fu, X., Ho, J., Hong, S.H., Koschützki, D., Murray, C., Nikolov, N.S., Taib, R., Tarassov, A., Xu, K.: GEOMI: Geometry for maximum insight. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 468–479. Springer, Heidelberg (2006)

Schena, M., Shalon, D., Davis, R.W., Brown, P.O.: Quantitative monitoring of gene expression patterns with a complementary dna microarray. Science 270(5235), 467– 470 (1995)

Ashburner, M., Ball, C.A., Blake, J.A., Botstein, D., Butler, H., Cherry, J.M., Davis, A.P., Dolinski, K., Dwight, S.S., Eppig, J.T., Harris, M.A., Hill, D.P., IsselTarver, L., Kasarskis, A., Lewis, S., Matese, J.C., Richardson, J.E., Ringwald, M., Rubin, G.M., Sherlock, G.: Gene ontology: tool for the unification of biology. Nature Genetics 25(1), 25–29 (2000)

Khatri, P., Draghici, S.: Ontological analysis of gene expression data: current tools, limitations, and open problems. Bioinformatics 21(18), 3587–3595 (2005)

Maere, S., Heymans, K., Kuiper, M.: Bingo: a cytoscape plugin to assess overrepresentation of gene ontology categories in biological networks. Bioinformatics 21(16), 3448–3449 (2005)

Baehrecke, E.H., Dang, N., Babaria, K., Shneiderman, B.: Visualization and analysis of microarray and gene ontology data with treemaps. BMC Bioinformatics 5, 84 (2004)

Shneiderman, B.: Tree visualization with treemaps: A 2d space-filling approach. ACM Transactions on Graphics 11(1), 92–99 (1992)

Lee, J.S.M., Katari, G., Sachidanandam, R.: GObar: A gene ontology based analysis and visualization tool for gene sets. BMC Bioinformatics 6, 189 (2005)

Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Software Practice and Experience 30(11), 1203–1233 (2000)

Joslyn, C.A., Mniszewski, S.M., Smith, S.A., Weber, P.M.: Spindleviz: A three dimensional, order theoretical visualization environment for the gene ontology. In: Proceedings of Joint BioLINK and 9th Bio-Ontologies Meeting (2006)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

Katifori, A., Halatsis, C., Lepouras, G., Vassilakis, C., Giannopoulou, E.: Ontology visualization methods—a survey. ACM Comput. Surv. 39(4), 10 (2007)

Xu, K., Huang, X.X., Cotsapas, C., Hong, S.H., McCaughan, G., Gorrell, M., Little, P., Williams, R.: Combined visualisation and analysis of gene ontology annotations using multivariate representations of annotations and bipartite networks. Technical Report 09/166, CSIRO (2009)

Robinson, P.N., Wollstein, A., Bohme, U., Beattie, B.: Ontologizing geneexpression microarray data: characterizing clusters with gene ontology. Bioinformatics 20(6), 979–981 (2004)

Alterovitz, G., Xiang, M., Mohan, M., Ramoni, M.F.: GO PaD: the gene ontology partition database. Nucleic Acids Research 35, D322–D327 (2007)

Shannon, P., Markiel, A., Ozier, O., Baliga, N.S., Wang, J.T., Ramage, D., Amin, N., Schwikowski, B., Ideker, T.: Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Research 13, 2498–2504 (2003)

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs, Methods and Models. LNCS, vol. 2025. Springer, Heidelberg (2001)

Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic and Discrete Methods 4(3), 312–316 (1983)

Nagamochi, H.: An improved bound on the one-sided minimum crossing number in two-layered drawings. Discrete & Computational Geometry 33(4), 569–591 (2005)

Xu, K., Williams, R., Hong, S.H., Liu, Q., Zhang, J.: Semi-bipartite graph visualization for gene ontology networks. Technical Report EP091883, CSIRO (2009), gene-ontology-layout.pdf

Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.P.: A technique for drawing directed graphs. IEEE Transactions on Software Engineering 19(3), 214–230 (1993)

Chvatal, V.: Linear Programming. W.H. Freeman, New York (1983)

Purchase, H.C.: Which aesthetic has the greatest effect on human understanding? In: Proceedings of the 5th International Symposium on Graph Drawing, London, UK, pp. 248–261. Springer, Heidelberg (1997)

Cowley, M.J., Cotsapas, C.J., Williams, R.B.H., Chan, E.K.F., Pulvers, J.N., Liu, M.Y., Luo, O.J., Nott, D.J., Little, P.F.R.: Intra- and inter-individual genetic differences in gene expression. Nature Proceedings (2008),