Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T03:42:18.621Z Has data issue: false hasContentIssue false
  • English
  • Français

Discovering bipartite substructure in directed networks

Part of: Discrete mathematics in relation to computer science Mathematical biology in general

Published online by Cambridge University Press:  01 February 2011

Alan Taylor ,
J. Keith Vass  and
Desmond J. Higham
Alan Taylor
Affiliation:
Department of Mathematics and Statistics, University of Strathclyde, Glasgow, G1 1XH, United Kingdom (email: [email protected])
J. Keith Vass
Affiliation:
Translational Medical Research Collaboration, The Sir James Black Centre, University of Dundee, Dundee, DD1 5EH, United Kingdom (email: [email protected])
Desmond J. Higham
Affiliation:
Department of Mathematics and Statistics, University of Strathclyde, Glasgow, G1 1XH, United Kingdom (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Bipartivity is an important network concept that can be applied to nodes, edges and communities. Here we focus on directed networks and look for subnetworks made up of two distinct groups of nodes, connected by ‘one-way’ links. We show that a spectral approach can be used to find hidden substructures of this form. Theoretical support is given for the idealized case where there is limited overlap between subnetworks. Numerical experiments show that the approach is robust to spurious and missing edges. A key application of this work is in the analysis of high-throughput gene expression data, and we give an example where a biologically meaningful directed bipartite subnetwork is found from a cancer microarray dataset.

MSC classification

Secondary: 68R10: Graph theory (including graph drawing) 92B05: General biology and biomathematics
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 14 , 2011 , pp. 72 - 86
Copyright
Copyright © London Mathematical Society 2011

References

[1]Barash, D., ‘Second eigenvalue of the Laplacian matrix for predicting RNA conformational switch by mutation’, Bioinformatics 20 (2004) 1861–1869.CrossRefGoogle ScholarPubMed
[2]de Silva, E. and Stumpf, M. P. H., ‘Complex networks and simple models in biology’, J. R. Soc. Interface 2 (2005) 419–430.CrossRefGoogle ScholarPubMed
[3]Estrada, E., ‘Protein bipartivity and essentiality in the yeast protein–protein interaction network’, J. Proteome Res. 5 (2006) 2177–2184.CrossRefGoogle ScholarPubMed
[4]Estrada, E. and Hatano, N., ‘Communicability in complex networks’, Phys. Rev. E 77 (2008) 036111.CrossRefGoogle ScholarPubMed
[5]Estrada, E., Higham, D. J. and Hatano, N., ‘Communicability and multipartite structures in complex networks at negative absolute temperatures’, Phys. Rev. E 78 (2008) 026102.CrossRefGoogle ScholarPubMed
[6]Estrada, E. and Rodríguez-Velázquez, J., ‘Spectral measures of bipartivity in complex networks’, Phys. Rev. E 72 (2005) 046105.CrossRefGoogle ScholarPubMed
[7]Golub, G. H. and Van Loan, C. F., Matrix computations, 3rd edn (Johns Hopkins University Press, Baltimore, 1996).Google Scholar
[8]Grindrod, P. and Kibble, M., ‘Review of uses of network and graph theory concepts within proteomics’, Expert Rev. Proteom. 1 (2004) 229–238.CrossRefGoogle ScholarPubMed
[9]Holme, P., Liljeros, F., Edling, C. R. and Kim, B. J., ‘Network bipartivity’, Phys. Rev. E 68 (2003) 056107.CrossRefGoogle ScholarPubMed
[10]Hu, Y. and Scott, J. A., HSL_MC73: a fast multilevel Fiedler and profile reduction code, RAL-TR-2003-36, Numerical Analysis Group, Computational Science and Engineering Department, Rutherford Appleton Laboratory, 2003.Google Scholar
[11]Morrison, J. L., Breitling, R., Higham, D. J. and Gilbert, D. R., ‘A lock-and-key model for protein–protein interactions’, Bioinformatics 2 (2006) 2012–2019.CrossRefGoogle Scholar
[12]Spence, A., Stoyanov, Z. and Vass, J. K., ‘The sensitivity of spectral clustering applied to gene expression data’, Proceedings of the 1st International Conference on Bioinformatics and Biomedical Engineering, 2007, 1343–1346.CrossRefGoogle Scholar
[13]Taylor, A. J., ‘Computational tools for complex networks’, PhD Thesis, University of Strathclyde, 2009.Google Scholar
[14]Thomas, A., Cannings, R., Monk, N. A. M. and Cannings, C., ‘On the structure of protein–protein interaction networks’, Biochem. Soc. Trans. 31 (2003) 1491–1496.CrossRefGoogle ScholarPubMed
[15]Valk, P. J., Verhaak, R. G., Beijen, M. A., Erpelinck, C. A., van Waalwijk van Doorn-Khosrovani, S. B., Boer, J. M., Beverloo, H. B., Moorhouse, M. J., van der Spek, P. J., Lüwenberg, B. and Delwel, R., ‘Prognostically useful gene-expression profiles in acute myeloid leukemia’, New Engl. J. Med. 16 (2004) 1617–1628.CrossRefGoogle Scholar
[16]Vass, J. K., Higham, D. J., Mao, X. and Crowther, D., ‘New controls of TCA-cycle genes revealed in networks built by discretization or correlation’, Technical Report, Department of Mathematics, University of Strathclyde, Glasgow, UK, 2009, 10.Google Scholar
[17]Walshaw, C. and Cross, M., ‘JOSTLE: parallel multilevel graph-partitioning software – an overview’, Mesh partitioning techniques and domain decomposition techniques (ed. Magoules, F.; Saxe-Coburg Publications, Stirling, UK, 2007) 27–58.Google Scholar