L-GRAAL: Lagrangian graphlet-based network aligner.
BACKGROUND
Discovering and understanding patterns in networks of protein-protein interactions (PPIs) is a central problem in systems biology. Alignments between these networks aid functional understanding as they uncover important information, such as evolutionary conserved pathways, protein complexes and functional orthologs. A few methods have been proposed for global PPI network alignments, but because of NP-completeness of underlying sub-graph isomorphism problem, producing topologically and biologically accurate alignments remains a challenge.


RESULTS
We introduce a novel global network alignment tool, Lagrangian GRAphlet-based ALigner (L-GRAAL), which directly optimizes both the protein and the interaction functional conservations, using a novel alignment search heuristic based on integer programming and Lagrangian relaxation. We compare L-GRAAL with the state-of-the-art network aligners on the largest available PPI networks from BioGRID and observe that L-GRAAL uncovers the largest common sub-graphs between the networks, as measured by edge-correctness and symmetric sub-structures scores, which allow transferring more functional information across networks. We assess the biological quality of the protein mappings using the semantic similarity of their Gene Ontology annotations and observe that L-GRAAL best uncovers functionally conserved proteins. Furthermore, we introduce for the first time a measure of the semantic similarity of the mapped interactions and show that L-GRAAL also uncovers best functionally conserved interactions. In addition, we illustrate on the PPI networks of baker's yeast and human the ability of L-GRAAL to predict new PPIs. Finally, L-GRAAL's results are the first to show that topological information is more important than sequence information for uncovering functionally conserved interactions.


METHODS
L-GRAAL is coded in C++. Software is available at: http://bio-nets.doc.ic.ac.uk/L-GRAAL/.


BACKGROUND
n.malod-dognin@imperial.ac.uk


BACKGROUND
Supplementary data are available at Bioinformatics online.
Department of Computing, Imperial College London, London, UK.
Noël
N
Malod-Dognin
Department of Computing, Imperial College London, London, UK.
Nataša
N
Pržulj
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D030562:Databases, Protein; D006801:Humans; D058977:Molecular Sequence Annotation; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000378:metabolism*; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D012984:Software; D049490:Systems Biology
D011506:Proteins