Divide, align and full-search for discovering conserved protein complexes

Pavol Jancura, Jaap Heringa, Elena Marchiori

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

5 Citations (Scopus)


Advances in modern technologies for measuring protein-protein interaction (PPI) has boosted research in PPI networks analysis and comparison. One of the challenging problems in comparative analysis of PPI networks is the comparison of networks across species for discovering conserved modules. Approaches for this task generally merge the considered networks into one new weighted graph, called alignment graph, which describes how interaction between each pair of proteins is preserved in different networks. The problem of finding conserved protein complexes across species is then transformed into the problem of searching the alignment graph for subnetworks whose weights satisfy a given constraint. Because the latter problem is computationally intractable, generally greedy techniques are used. In this paper we propose an alternative approach for this task. First, we use a technique we recently introduced for dividing PPI networks into small subnets which are likely to contain conserved modules. Next, we perform network alignment on pairs of resulting subnets from different species, and apply an exact search algorithm iteratively on each alignment graph, each time changing the constraint based on the weight of the solution found in the previous iteration. Results of experiments show that this method discovers multiple accurate conserved modules, and can be used for refining state-of-the-art algorithms for comparative network analysis.

Original languageEnglish
Title of host publicationEvolutionary Computation, Machine Learning and Data Mining in Bioinformatics - 6th European Conference, EvoBIO 2008, Proceedings
EditorsE. Marchiori, J. Moore
Place of PublicationBerlin
Number of pages12
ISBN (Electronic)978-3-540-78757-0
ISBN (Print)978-3-540-78756-3
Publication statusPublished - 21 Jul 2008
Externally publishedYes
Event6th European Conference on Evolutionary Computation, Machine Learning, and Data Mining in Bioinformatics, EvoBIO 2008 - Naples, Italy
Duration: 26 Mar 200828 Mar 2008

Publication series

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


Conference6th European Conference on Evolutionary Computation, Machine Learning, and Data Mining in Bioinformatics, EvoBIO 2008


  • Biological networks alignment
  • Optimization


Dive into the research topics of 'Divide, align and full-search for discovering conserved protein complexes'. Together they form a unique fingerprint.

Cite this