GraphAlignment: Bayesian pairwise alignment of biological networks

We introduce the Bioconductor package GraphAlignment for pairwise alignment of bio-molecular networks. The alignment incorporates information both from network vertices and network edges and is based on an explicit evolutionary model, allowing inference of all scoring parameters directly from empirical data. We compare the performance of our algorithm to an alternative algorithm, Gr？mlin 2.0.On simulated data, GraphAlignment outperforms Gr？mlin 2.0 in several benchmarks except for computational complexity. When there is little or no noise in the data, GraphAlignment is slower than Gr？mlin 2.0. It is faster than Gr？mlin 2.0 when processing noisy data containing spurious vertex associations. Its typical case complexity grows approximately as O ( N 2 . 6 ) .On empirical bacterial protein-protein interaction networks (PIN) and gene co-expression networks, GraphAlignment outperforms Gr？mlin 2.0 with respect to coverage and specificity, albeit by a small margin. On large eukaryotic PIN, Gr？mlin 2.0 outperforms GraphAlignment.The GraphAlignment algorithm is robust to spurious vertex associations, correctly resolves paralogs, and shows very good performance in identification of homologous vertices defined by high vertex and/or interaction similarity. The simplicity and generality of GraphAlignment edge scoring makes the algorithm an appropriate choice for global alignment of networks.The advent of high-throughput techniques has generated new types of large-scale molecular interaction data, conveniently represented by graphs or networks. Examples include metabolic networks formed by enzymes and metabolites [1], gene co-expression networks with edges between pairs of genes indicating a certain correlation between their expression levels [2], residue contact maps as representations of protein structures [3,4], and protein-protein interaction networks, where edges between vertices indicate a physical interaction between proteins [5]. For an introduction, see reference [6