Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints

Yasuo Tabei; Akihiro Kishimoto; Masaaki Kotera; Yoshihiro Yamanishi

doi:10.1145/2487575.2487637

Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints

Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, Yoshihiro Yamanishi

Institute for Advanced Study

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

Analyzing functional interactions between small compounds and proteins is indispensable in genomic drug discovery. Since rich information on various compound-protein interactions 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 compoundprotein 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 compoundprotein pairs/substrate-product pairs and show that SITA performs better than other possible approaches.

Original language	English
Title of host publication	KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Editors	Rajesh Parekh, Jingrui He, Dhillon S. Inderjit, Paul Bradley, Yehuda Koren, Rayid Ghani, Ted E. Senator, Robert L. Grossman, Ramasamy Uthurusamy
Publisher	Association for Computing Machinery
Pages	176-184
Number of pages	9
ISBN (Electronic)	9781450321747
DOIs	https://doi.org/10.1145/2487575.2487637
Publication status	Published - Aug 11 2013
Event	19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 - Chicago, United States Duration: Aug 11 2013 → Aug 14 2013

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	Part F128815

Other

Other	19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013
Country/Territory	United States
City	Chicago
Period	8/11/13 → 8/14/13

All Science Journal Classification (ASJC) codes

Software
Information Systems

Access to Document

10.1145/2487575.2487637

Cite this

Tabei, Y., Kishimoto, A., Kotera, M., & Yamanishi, Y. (2013). Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. In R. Parekh, J. He, D. S. Inderjit, P. Bradley, Y. Koren, R. Ghani, T. E. Senator, R. L. Grossman, & R. Uthurusamy (Eds.), KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 176-184). Article 2487637 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F128815). Association for Computing Machinery. https://doi.org/10.1145/2487575.2487637

Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. / Tabei, Yasuo; Kishimoto, Akihiro; Kotera, Masaaki et al.
KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ed. / Rajesh Parekh; Jingrui He; Dhillon S. Inderjit; Paul Bradley; Yehuda Koren; Rayid Ghani; Ted E. Senator; Robert L. Grossman; Ramasamy Uthurusamy. Association for Computing Machinery, 2013. p. 176-184 2487637 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F128815).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Tabei, Y, Kishimoto, A, Kotera, M & Yamanishi, Y 2013, Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. in R Parekh, J He, DS Inderjit, P Bradley, Y Koren, R Ghani, TE Senator, RL Grossman & R Uthurusamy (eds), KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining., 2487637, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. Part F128815, Association for Computing Machinery, pp. 176-184, 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, United States, 8/11/13. https://doi.org/10.1145/2487575.2487637

Tabei Y, Kishimoto A, Kotera M, Yamanishi Y. Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. In Parekh R, He J, Inderjit DS, Bradley P, Koren Y, Ghani R, Senator TE, Grossman RL, Uthurusamy R, editors, KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2013. p. 176-184. 2487637. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/2487575.2487637

Tabei, Yasuo ; Kishimoto, Akihiro ; Kotera, Masaaki et al. / Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints. KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. editor / Rajesh Parekh ; Jingrui He ; Dhillon S. Inderjit ; Paul Bradley ; Yehuda Koren ; Rayid Ghani ; Ted E. Senator ; Robert L. Grossman ; Ramasamy Uthurusamy. Association for Computing Machinery, 2013. pp. 176-184 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{ff3da8d5c7ed45b69dfc5d26ff4a12f8,

title = "Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints",

abstract = "Analyzing functional interactions between small compounds and proteins is indispensable in genomic drug discovery. Since rich information on various compound-protein interactions 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 compoundprotein 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 compoundprotein pairs/substrate-product pairs and show that SITA performs better than other possible approaches.",

author = "Yasuo Tabei and Akihiro Kishimoto and Masaaki Kotera and Yoshihiro Yamanishi",

note = "Publisher Copyright: Copyright {\textcopyright} 2013 ACM.; 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 ; Conference date: 11-08-2013 Through 14-08-2013",

year = "2013",

month = aug,

day = "11",

doi = "10.1145/2487575.2487637",

language = "English",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "176--184",

editor = "Rajesh Parekh and Jingrui He and Inderjit, {Dhillon S.} and Paul Bradley and Yehuda Koren and Rayid Ghani and Senator, {Ted E.} and Grossman, {Robert L.} and Ramasamy Uthurusamy",

booktitle = "KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

TY - GEN

T1 - Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints

AU - Tabei, Yasuo

AU - Kishimoto, Akihiro

AU - Kotera, Masaaki

AU - Yamanishi, Yoshihiro

PY - 2013/8/11

Y1 - 2013/8/11

N2 - Analyzing functional interactions between small compounds and proteins is indispensable in genomic drug discovery. Since rich information on various compound-protein interactions 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 compoundprotein 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 compoundprotein pairs/substrate-product pairs and show that SITA performs better than other possible approaches.

AB - Analyzing functional interactions between small compounds and proteins is indispensable in genomic drug discovery. Since rich information on various compound-protein interactions 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 compoundprotein 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 compoundprotein pairs/substrate-product pairs and show that SITA performs better than other possible approaches.

UR - http://www.scopus.com/inward/record.url?scp=85016184606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016184606&partnerID=8YFLogxK

U2 - 10.1145/2487575.2487637

DO - 10.1145/2487575.2487637

M3 - Conference contribution

AN - SCOPUS:85016184606

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 176

EP - 184

BT - KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

A2 - Parekh, Rajesh

A2 - He, Jingrui

A2 - Inderjit, Dhillon S.

A2 - Bradley, Paul

A2 - Koren, Yehuda

A2 - Ghani, Rayid

A2 - Senator, Ted E.

A2 - Grossman, Robert L.

A2 - Uthurusamy, Ramasamy

PB - Association for Computing Machinery

T2 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013

Y2 - 11 August 2013 through 14 August 2013

ER -

Succinct interval-splitting tree for scalable similarity search of compound-protein pairs with property constraints

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this