BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks
Loading...
Date
2014
Authors
Alkan, Ferhat
Erten, Cesim
Journal Title
Journal ISSN
Volume Title
Publisher
Oxford University Press
Abstract
Motivation: Global many-to-many alignment of biological networks has been a central problem in comparative biological network studies. Given a set of biological interaction networks the informal goal is to group together related nodes. For the case of protein-protein interaction networks such groups are expected to form clusters of functionally orthologous proteins. Construction of such clusters for networks from different species may prove useful in determining evolutionary relationships in predicting the functions of proteins with unknown functions and in verifying those with estimated functions. Results: A central informal objective in constructing clusters of orthologous proteins is to guarantee that each cluster is composed of members with high homological similarity usually determined via sequence similarities and that the interactions of the proteins involved in the same cluster are conserved across the input networks. We provide a formal definition of the global many-to-many alignment of multiple protein-protein interaction networks that captures this informal objective. We show the computational intractability of the suggested definition. We provide a heuristic method based on backbone extraction and merge strategy (BEAMS) for the problem. We finally show through experiments based on biological significance tests that the proposed BEAMS algorithm performs better than the state-of-the-art approaches. Furthermore the computational burden of the BEAMS algorithm in terms of execution speed and memory requirements is more reasonable than the competing algorithms.
Description
Keywords
Turkish CoHE Thesis Center URL
Citation
54
WoS Q
Q1
Scopus Q
N/A
Source
Volume
30
Issue
4
Start Page
531
End Page
539