Indexing a protein-protein interaction network expedites network alignment.

ABSTRACT:

Background

Network query problem aligns a small query network with an arbitrarily large target network. The complexity of this problem grows exponentially with the number of nodes in the query network if confidence in the optimality of result is desired. Scaling this problem to large query and target networks remains to be a challenge.

Results

In this article, we develop a novel index structure that dramatically reduces the cost of the network query problem. Our index structure maintains a small set of reference networks where each reference network is a small, carefully chosen subnetwork from the target network. Along with each reference, we also store all of its non-overlapping and statistically significant alignments with the target network. Given a query network, we firs

SUBMITTER: Hasan MM 

PROVIDER: S-EPMC4600321 | biostudies-literature | 2015 Oct

REPOSITORIES: biostudies-literature