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 versus accuracy of our method for different reference selection strategies. Experiments are repeated for different number of references. Average query processing time is presented as running time. Accuracy is calculated over all test queries. Lower running time and higher accuracy indicates better performance. The running time of exhaustive search is over 2 days (not shown in figure).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 3: Running time versus accuracy of our method for different reference selection strategies. Experiments are repeated for different number of references. Average query processing time is presented as running time. Accuracy is calculated over all test queries. Lower running time and higher accuracy indicates better performance. The running time of exhaustive search is over 2 days (not shown in figure).

Mentions: Figure 3 shows the results for three reference selection strategies. We also measured the running time of exhaustively searching the database without using our index. The running time of exhaustive search was over 2 days. The experiments demonstrate that reference based indexing is significantly faster than exhaustive search. It improves the running time by a factor of five over exhaustive search. Creating candidate references by following the three rules (see Section 3.2.1) alone improves the running time by up to 5%. Finally, carefully selecting references using Algorithm 1 results in up to 10% additional improvement. In summary, the results suggest that the reference selection strategy of RINQ indeed helps in improving the performance of our method. It also demonstrates that RINQ makes similarity searches in biological network databases practical.Fig. 3.


RINQ: Reference-based Indexing for Network Queries.

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

Running time versus accuracy of our method for different reference selection strategies. Experiments are repeated for different number of references. Average query processing time is presented as running time. Accuracy is calculated over all test queries. Lower running time and higher accuracy indicates better performance. The running time of exhaustive search is over 2 days (not shown in figure).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 3: Running time versus accuracy of our method for different reference selection strategies. Experiments are repeated for different number of references. Average query processing time is presented as running time. Accuracy is calculated over all test queries. Lower running time and higher accuracy indicates better performance. The running time of exhaustive search is over 2 days (not shown in figure).
Mentions: Figure 3 shows the results for three reference selection strategies. We also measured the running time of exhaustively searching the database without using our index. The running time of exhaustive search was over 2 days. The experiments demonstrate that reference based indexing is significantly faster than exhaustive search. It improves the running time by a factor of five over exhaustive search. Creating candidate references by following the three rules (see Section 3.2.1) alone improves the running time by up to 5%. Finally, carefully selecting references using Algorithm 1 results in up to 10% additional improvement. In summary, the results suggest that the reference selection strategy of RINQ indeed helps in improving the performance of our method. It also demonstrates that RINQ makes similarity searches in biological network databases practical.Fig. 3.

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