A robust network alignment algorithm for detecting evolutionarily conserved networks and protein complexes across species

Due to the complexity of the biological networks, it is difficult to extract the conserved modules across species with graphical representation. One of the arising challenges is to compare different networks in order to analyze and discover common sub-networks, especially cliqued structure of protein complexes that may share similar biological functions. We combine sequence alignment and ontology-based semantic similarity score to cluster potential orthologous proteins and use depth-first search for network comparison to discover the conserved networks and protein complexes across species. This method allows the biological evolutions such as duplication and divergence to be tolerated in the network alignment process under a user specified value ε. We apply network alignment for two large protein-protein interactions (Saccharomyces cerevisiae and Caenorhabditis elegans) as our test data. We detect a large number of conserved networks and true complexes that match in the yeast MIPS database.