Fast and Accurate Alignment of Multiple Protein Networks
Comparative analysis of protein networks has proven to be a powerful approach for elucidating network structure and predicting protein function and interaction. A fundamental challenge for the successful application of this approach is to devise an effici
- PDF / 497,868 Bytes
- 11 Pages / 430 x 660 pts Page_size
- 62 Downloads / 235 Views
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel {kalaevma,roded}@post.tau.ac.il 2 CSE, University of California San Diego, USA [email protected]
Abstract. Comparative analysis of protein networks has proven to be a powerful approach for elucidating network structure and predicting protein function and interaction. A fundamental challenge for the successful application of this approach is to devise an efficient multiple network alignment algorithm. Here we present a novel framework for the problem. At the heart of the framework is a novel representation of multiple networks that is only linear in their size as opposed to current exponential representations. Our alignment algorithm is very efficient, being capable of aligning 10 networks with tens of thousands of proteins each in minutes. We show that our algorithm outperforms a previous strategy for the problem that is based on progressive alignment, and produces results that are more in line with current biological knowledge.
1
Introduction
Recent technological advances enable the systematic characterization of proteinprotein interaction (PPI) networks across multiple species. Procedures such as yeast two-hybrid ([1]) and protein co-immunoprecipitation ([2]) are routinely employed nowadays to generate large-scale protein interaction networks for human and most model species ([3,4,5,6,7]). Key to interpreting these data is the inference of cellular machineries. As in other biological domains, a comparative approach provides a powerful basis for addressing this challenge, calling for algorithms for protein network alignment. In the network alignment problem one has to identify network regions that are conserved in their sequence and interaction pattern across two or more species. While the general problem is hard, generalizing subgraph isomorphism, heuristic methods have been devised to tackle it. One heuristic approach for the problem creates a merged representation of the networks being compared, called a network alignment graph, facilitating the search for conserved subnetworks. In a network alignment graph, the nodes represent sets of proteins, one from each species, and the edges represent conserved PPIs across the investigated species. The network alignment paradigm has been applied successfully by a number of authors to search for conserved pathways [8] and complexes [9,10,11]. However, M. Vingron and L. Wong (Eds.): RECOMB 2008, LNBI 4955, pp. 246–256, 2008. c Springer-Verlag Berlin Heidelberg 2008
Fast and Accurate Alignment of Multiple Protein Networks
247
its extension to more than a few (3) networks proved difficult due to the exponential growth of the alignment graph with the number of species. Recently, an algorithm was suggested to overcome this difficulty, proposing the idea of imitating progressive sequence alignment techniques [12]. The latter algorithm was successfully applied to align up to 10 microbial networks. Very recently, Dutkowsky and Tiuryn [13] proposed another framework for efficient alignment of multiple network
Data Loading...
