NetCoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks

Abstract

Motivation: Owing to recent advancements in high-throughput technologies, protein–protein interaction networks of more and more species become available in public databases. The question of how to identify functionally conserved proteins across species attracts a lot of attention in computational biology. Network alignments provide a systematic way to solve this problem. However, most existing alignment tools encounter limitations in tackling this problem. Therefore, the demand for faster and more efficient alignment tools is growing. Results: We present a fast and accurate algorithm, NetCoffee, which allows to find a global alignment of multiple protein–protein interaction networks. NetCoffee searches for a global alignment by maximizing a target function using simulated annealing on a set of weighted bipartite graphs that are constructed using a triplet approach similar to T-Coffee. To assess its performance, NetCoffee was applied to four real datasets. Our results suggest that NetCoffee remedies several limitations of previous algorithms, outperforms all existing alignment tools in terms of speed and nevertheless identifies biologically meaningful alignments. Availability: The source code and data are freely available for download under the GNU GPL v3 license at https://code.google.com/p/netcoffee/.