Projects
Abstract.
In the network querying problem, one is given a protein complex
or pathway of species A and a protein-protein
interaction network of species B; the goal is to
identify subnetworks of B that are similar to the
query. Existing approaches mostly depend on knowledge of the
interaction 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 matching set of
proteins that are sequence-similar to the query proteins and
span a connected region of the network, while allowing both
insertions and deletions. The algorithm uses alternatively
dynamic programming and integer linear programming for the
search task. We test Torque with queries
from yeast, fly, and human, where we compare it to the QNet
topology-based approach, and with queries from less studied
species, where only topology-free algorithms apply. Torque detects many more matches than QNet,
while in both cases giving results that are highly functionally
coherent.