Dividing protein interaction networks by growing orthologous articulations

Pavol Jancura, Jaap Heringa, Elena Marchiori

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


The increasing growth of data on protein-protein interaction (PPI) networks has boosted research on their comparative analysis. In particular, recent studies proposed models and algorithms for performing network alignment, the comparison of networks across species for discovering conserved modules. Common approaches for this task construct a merged representation of the considered networks, called alignment graph, and search the alignment graph for conserved networks of interest using greedy techniques. In this paper we propose a modular approach to this task. First, each network to be compared is divided into small subnets which are likely to contain conserved modules. To this aim, we develop an algorithm for dividing PPI networks that combines a graph theoretical property(articulation) with a biological one (orthology). Next, network alignment is performed on pairs of resulting subnets from different species. We tackle this task by means of a state-of-the-art alignment graph model for constructing alignment graphs, and an exact algorithm for searching in the alignment graph. Results of experiments show the ability of this approach to discover accurate conserved modules, and substantiate the importance of the notions of orthology and articulation for performing comparative network analysis in a modular fashion.

Original languageEnglish
Title of host publication3rd IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2008
EditorsM. Chetty, S. Ahmad, A. Ngom
Place of PublicationBerlin
Number of pages14
ISBN (Electronic)978-3-540-88436-1
ISBN (Print)978-3-540-88434-7
Publication statusPublished - 5 Dec 2008
Externally publishedYes
Event3rd IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2008 - Melbourne, VIC, Australia
Duration: 15 Oct 200817 Oct 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5265 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference3rd IAPR International Conference on Pattern Recognition in Bioinformatics, PRIB 2008
CityMelbourne, VIC


  • Modular network alignment
  • Protein network dividing


Dive into the research topics of 'Dividing protein interaction networks by growing orthologous articulations'. Together they form a unique fingerprint.

Cite this