Discovering 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.
The objective of a multiple network alignment is to create clusters of nodes
that are evolutionarily conserved and functionally consistent across all
networks. Unfortunately, the alignment methods proposed thus far do not fully
meet this objective, as they are guided by pairwise scores that do not utilize
the entire functional and topological information across all networks. To
overcome this weakness, we propose FUSE, a multiple network aligner that
utilizes all functional and topological information in all PPI networks. It
works in two steps. First, it computes novel similarity scores of proteins
across the PPI networks by fusing from all aligned networks both the protein
wiring patterns and their sequence similarities. It does this by using
Non-negative Matrix Tri-Factorization (NMTF). When we apply NMTF on the five
largest and most complete PPI networks from BioGRID, we show that NMTF finds a
larger number of protein pairs across the PPI networks that are functionally
conserved than can be found by using protein sequence similarities alone. This
demonstrates complementarity of protein sequence and their wiring patterns in
the PPI networks. In the second step, FUSE uses a novel maximum weight
k-partite matching approximation algorithm to find an alignment between
multiple networks. We compare FUSE with the state of the art multiple network
aligners and show that it produces the largest number of functionally
consistent clusters that cover all aligned PPI networks. Also, FUSE is more
computationally efficient than other multiple network aligners.