Torque: Topology-Free Querying of Protein Interaction Networks

TitleTorque: Topology-Free Querying of Protein Interaction Networks
Publication TypeConference Paper
Year of Publication2009
AuthorsBruckner, S., Hüffner F., Karp R. M., Shamir R., & Sharan R.
Page(s)74-89
Other Numbers3249
Abstract

In the network querying problem, one is given a protein complexor pathway of species A and a protein{protein interaction networkof species B; the goal is to identify subnetworks of B that are similarto the query. Existing approaches mostly depend on knowledge of theinteraction topology of the query in the network of species A; however,in practice, this topology is often not known. To combat this problem,we develop a topology-free querying algorithm, which we call Torque.Given a query, represented as a set of proteins, Torque seeks a matchingset of proteins that are sequence-similar to the query proteins and spana connected region of the network, while allowing both insertions anddeletions. The algorithm uses alternatively dynamic programming andinteger linear programming for the search task. We test Torque withqueries from yeast,y, and human, where we compare it to the QNettopology-based approach, and with queries from less studied species,where only topology-free algorithms apply. Torque detects many morematches than QNet, while in both cases giving results that are highlyfunctionally coherent.

Bibliographic Notes

Proceedings of the 13th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2009), Tucson, Arizona, pp. 74-89

Abbreviated Authors

S. Bruckner, F. Hüffner, R. M. Karp, R. Shamir, and R. Sharan

ICSI Research Group

Algorithms

ICSI Publication Type

Article in conference proceedings