2013 SuccinctIntervalSplittingTreefo

• (Tabei et al., 2013) ⇒ Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, and Yoshihiro Yamanishi. (2013). “Succinct Interval-splitting Tree for Scalable Similarity Search of Compound-protein Pairs with Property Constraints.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487637

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Succinct+Interval-splitting+Tree+for+Scalable+Similarity+Search+of+Compound-protein+Pairs+with+Property+Constraints
• http://dl.acm.org/citation.cfm?id=2487575.2487637&preflayout=flat#citedby

Quotes

Author Keywords

• Indexing methods; similarity search; succinct data structure; wavelet tree

Abstract

Analyzing functional interactions between small compounds and proteins is indispensable in genomic drug discovery. Since rich information on various compound-protein inter-actions is available in recent molecular databases, strong demands for making best use of such databases require to invent powerful methods to help us find new functional compound-protein pairs on a large scale. We present the succinct interval-splitting tree algorithm (SITA) that efficiently performs similarity search in databases for compound-protein pairs with respect to both binary fingerprints and real-valued properties. SITA achieves both time and space efficiency by developing the data structure called interval-splitting trees, which enables to efficiently prune the useless portions of search space, and by incorporating the ideas behind wavelet tree, a succinct data structure to compactly represent trees. We experimentally test SITA on the ability to retrieve similar compound-protein pairs / substrate-product pairs for a query from large databases with over 200 million compound-protein pairs / substrate-product pairs and show that SITA performs better than other possible approaches.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 SuccinctIntervalSplittingTreefo	Yasuo Tabei Akihiro Kishimoto Masaaki Kotera Yoshihiro Yamanishi			Succinct Interval-splitting Tree for Scalable Similarity Search of Compound-protein Pairs with Property Constraints				10.1145/2487575.2487637		2013