Limits...
RINQ: Reference-based Indexing for Network Queries.

Gülsoy G, Kahveci T - Bioinformatics (2011)

Bottom Line: We perform pairwise alignment only for the remaining networks.We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks.Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.

View Article: PubMed Central - PubMed

Affiliation: Computer and Information Sciences and Engineering Department, University of Florida, Gainesville, FL 32611, USA. ggulsoy@cise.ufl.edu

ABSTRACT
We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.

Show MeSH
Running time and accuracy of RINQ for different query selectivity values. These results are calculated using 32 references.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3117351&req=5

Figure 5: Running time and accuracy of RINQ for different query selectivity values. These results are calculated using 32 references.

Mentions: Effects of query selectivity: following from our previous experiments, we fix the number of references to 32 and vary the query selectivity. Figure 5 plots the results. As the selectivity increases, the size of the result set, and thus the number of networks we need to align with the query increases. As a result, the running time of RINQ grows. We observe that running time of our method does not increase linearly. This is expected as the size of the actual result set grows, it gets harder to place database networks into the filter set. The small gap between Oracle and RINQ indicates that our method is very successful in filtering unpromising database networks. It also shows that our method leaves little room for improvement particularly for small selectivity values. For instance, when the selectivity is 3%, our method's running time is almost that of the smallest number of alignments needed for that selectivity.Fig. 5.


RINQ: Reference-based Indexing for Network Queries.

Gülsoy G, Kahveci T - Bioinformatics (2011)

Running time and accuracy of RINQ for different query selectivity values. These results are calculated using 32 references.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3117351&req=5

Figure 5: Running time and accuracy of RINQ for different query selectivity values. These results are calculated using 32 references.
Mentions: Effects of query selectivity: following from our previous experiments, we fix the number of references to 32 and vary the query selectivity. Figure 5 plots the results. As the selectivity increases, the size of the result set, and thus the number of networks we need to align with the query increases. As a result, the running time of RINQ grows. We observe that running time of our method does not increase linearly. This is expected as the size of the actual result set grows, it gets harder to place database networks into the filter set. The small gap between Oracle and RINQ indicates that our method is very successful in filtering unpromising database networks. It also shows that our method leaves little room for improvement particularly for small selectivity values. For instance, when the selectivity is 3%, our method's running time is almost that of the smallest number of alignments needed for that selectivity.Fig. 5.

Bottom Line: We perform pairwise alignment only for the remaining networks.We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks.Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.

View Article: PubMed Central - PubMed

Affiliation: Computer and Information Sciences and Engineering Department, University of Florida, Gainesville, FL 32611, USA. ggulsoy@cise.ufl.edu

ABSTRACT
We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.

Show MeSH