MOTIVATION: Alignments of protein-protein interaction networks (PPIN) can be used to predict protein function, study conserved aspects of the interactome, and to establish evolutionary correspondences. Within this problem context, determining multiple network alignments (MNA) is a significant challenge that involves high computational complexity. A limited number of public MNA implementations are available currently and the majority of the pairwise network alignment (PNA) algorithms do not have MNA counterparts. Furthermore, current MNA algorithms do not allow choosing a specific PPIN relative to which an MNA could be constructed. Also, once an MNA is obtained, it cannot easily be modified, such as through addition of a new network, without expensive re-computation of the entire MNA. RESULTS: SMAL (Scaffold-Based Multiple Network Aligner) is a public, open-source, web-based application for determining MNAs from existing PNAs that addresses all the aforementioned challenges. With SMAL, PNAs can be combined rapidly to obtain an MNA. The software also supports visualization and user-data interactions to facilitate exploratory analysis and sensemaking. SMAL is especially useful when multiple alignments relative to a particular PPIN are required; furthermore, SMAL alignments are persistent in that existing correspondences between networks (obtained during PNA or MNA) are not lost as new networks are added. In comparative studies alongside existent MNA techniques, SMAL MNAs were found to be superior per a number of measures, such as the total number of identified homologs and interologs as well as the fraction of all identified correspondences that are functionally similar or homologous to the scaffold. While directed primarily at PPIN-alignment, SMAL is a generic network aligner and may be applied to arbitrary networks.Availability information: The SMAL web server and source code is available at: http://haddock6.sfsu.edu/smal/ CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

BACKGROUND: A wealth of protein interaction data has become available in recent years, creating an urgent need for powerful analysis techniques. In this context, the problem of finding biologically meaningful correspondences between different protein-protein interaction networks (PPIN) is of particular interest. The PPIN of a species can be compared with that of other species through the process of PPIN alignment. Such an alignment can provide insight into basic problems like species evolution and network component function determination, as well as translational problems such as target identification and elucidation of mechanisms of disease spread. Furthermore, multiple PPINs can be aligned simultaneously, expanding the analytical implications of the result. While there are several pairwise network alignment algorithms, few methods are capable of multiple network alignment. RESULTS: We propose SMAL, a MNA algorithm based on the philosophy of scaffold-based alignment. SMAL is capable of converting results from any global pairwise alignment algorithms into a MNA in linear time. Using this method, we have built multiple network alignments based on combining pairwise alignments from a number of publicly available (pairwise) network aligners. We tested SMAL using PPINs of eight species derived from the IntAct repository and employed a number of measures to evaluate performance. Additionally, as part of our experimental investigations, we compared the effectiveness of SMAL while aligning up to eight input PPINs, and examined the effect of scaffold network choice on the alignments. CONCLUSIONS: A key advantage of SMAL lies in its ability to create MNAs through the use of pairwise network aligners for which native MNA implementations do not exist. Experiments indicate that the performance of SMAL was comparable to that of the native MNA implementation of established methods such as IsoRankN and SMETANA. However, in terms of computational time, SMAL was significantly faster. SMAL was also able to retain many important characteristics of the native pairwise alignments, such as the number of aligned nodes and edges, as well as the functional and homologene similarity of aligned nodes. The speed, flexibility and the ability to retain prior correspondences as new networks are aligned, makes SMAL a compelling choice for alignment of multiple large networks.