GraphAlignment: Bayesian pairwise alignment of biological networks

Abstract:

ABSTRACT: BACKGROUND: With increased experimental availability and accuracy of bio-molecular networks, tools for their comparative and evolutionary analysis are needed. A key component for such studies is the alignment of networks. RESULTS: 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, Graemlin 2.0.On simulated data, GraphAlignment outperforms Graemlin 2.0 in several benchmarks except for computational complexity. When there is little or no noise in the data, GraphAlignment is slower than Graemlin 2.0. It is faster than Graemlin 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 Graemlin 2.0 with respect to coverage and specificity, albeit by a small margin. On large eukaryotic PIN, Graemlin 2.0 outperforms GraphAlignment. CONCLUSIONS: 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.

SEEK ID: https://fairdomhub.org/publications/184

PubMed ID: 23171476

Projects: Noisy-Strep

Publication type: Not specified

Journal: BMC Syst Biol

Citation:

Date Published: 21st Nov 2012

Registered Mode: Not specified

Authors: Michal Kolar, Jörn Meier, Ville Mustonen, Michael Lässig,

help Submitter
Activity

Views: 5413

Created: 18th Dec 2012 at 17:06

Last updated: 8th Dec 2022 at 17:26

help Tags

This item has not yet been tagged.

help Attributions

None

Powered by
(v.1.14.2)
Copyright © 2008 - 2023 The University of Manchester and HITS gGmbH