Torque: Topology-Free Querying of Protein Interaction Networks

TitleTorque: Topology-Free Querying of Protein Interaction Networks
Publication TypeJournal Article
Year of Publication2010
AuthorsBruckner, S., Hüffner F., Karp R. M., Shamir R., & Sharan R.
Published inJournal of Computational Biology
Volume17
Issue3
Page(s)237-252
Other Numbers3250
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

Journal of Computational Biology, Vol. 17, Issue 3, pp. 237-252

Abbreviated Authors

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

ICSI Research Group

Algorithms

ICSI Publication Type

Article in journal or magazine