http://www.bioinformatics.org/alignnemo/site/Fig1.jpg

First, the input networks are processed to assess reliability of protein-protein interactions. A relia- bility score is associated to each experimental procedure that detected the PPIs.

Second, the input networks are merged into an alignment graph. Nodes are weighted using scores given to proteins pairs by Inparanoid ; edges are weighted by properly combining the reliability scores assigned to the original PPIs in the previous step. Third, we extract from the alignment graph all connected k-subgraphs (here k = 4) and score them given node and edge weights. Top ranking fully connected k-subgraphs will be used as seeds for the alignment solution.

Fourth, each seed is expanded in a iteratively fashion by exploring the local neighborhood of the current solution beyond its immediate neighbors.

AlignNemo aims to identify conserved modules in PPI networks. A module is defined as a subset of nodes that are densely connected.

AlignNemo builds at first an alignment graph matching corresponding nodes pairs. Then it scores are assigned to both the protein pairs that constitute the nodes of the graph and to its edges, reflecting the reliability of the interactions in the input PPI networks. Different reliabilities are assigned according to the experimental evidences supporting each interaction.

Second, the method identifies a set of solution called seeds, i.e. small subgraphs with a large number of high scoring links and nodes.

Third, each seed is expanded in a greedy fashion, by including small subgraphs that are relatively well connected to it with reliable links. Each module is thus extracted by expanding iteratively a subgraph till specific conditions are satisfied. Details on the these steps are provided below.