BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks

Loading...
Thumbnail Image

Date

2014

Authors

Alkan, Ferhat
Erten, Cesim

Journal Title

Journal ISSN

Volume Title

Publisher

Oxford University Press

Research Projects

Organizational Units

Journal Issue

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