Universität zu Köln

Kolar, Michal ORCID: 0000-0002-4593-1525, Meier, Joern, Mustonen, Ville ORCID: 0000-0002-7270-1792, Laessig, Michael and Berg, Johannes (2012). GraphAlignment: Bayesian pairwise alignment of biological networks. BMC Syst. Biol., 6. LONDON: BMC. ISSN 1752-0509

Full text not available from this repository.

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. The simplicity and generality of GraphAlignment edge scoring makes the algorithm an appropriate choice for global alignment of networks.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Kolar, Michal UNSPECIFIED orcid.org/0000-0002-4593-1525 UNSPECIFIED Meier, Joern UNSPECIFIED UNSPECIFIED UNSPECIFIED Mustonen, Ville UNSPECIFIED orcid.org/0000-0002-7270-1792 UNSPECIFIED Laessig, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Berg, Johannes UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-478523
DOI:	10.1186/1752-0509-6-144
Journal or Publication Title:	BMC Syst. Biol.
Volume:	6
Date:	2012
Publisher:	BMC
Place of Publication:	LONDON
ISSN:	1752-0509
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language PROTEIN-INTERACTION NETWORKS; GLOBAL ALIGNMENT; DATABASE; PATHWAYS; YEAST; IDENTIFICATION Multiple languages Mathematical & Computational Biology Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/47852