A dividing-and-matching algorithm to detect conserved protein complexes via local network alignment

Local network alignment is an effective way to comparatively analyze a pair of protein-protein interaction (PPI) networks so as to identify the common subnetworks (conserved protein complexes) across species, which helps us better understand the structure, function and evolution of biological cells. In this work, we propose a new dividing-and-matching method named by DAMAlign to detect conserved protein complexes via local network alignment. DAMAlign firstly partitions one of PPI network into subnetworks and then these subnetworks are mapped to the other PPI network to find common connected components. In the course of finding common connected components, DAMAlign adopts a lenient criteria that is we locally extend a pair of homologous proteins if there exists at least one path of length not larger than 2 to connect one of node in the homologous protein pair in its corresponding network. We implement network alignment between S. cerevisiae and D. melanogaster. The experimental results show that DAMAlign outperforms other existing methods in recovering known protein complexes. Moreover, the conserved protein complexes that are detected by DAMAlign from different PPI networks are also functional similar in terms of their GO semantic similarity.