University of California, Riverside

Department of Electrical and Computer Engineering

Scalable Partitioning and Exploration of Chemical Spaces Using Geometric Hashing

Scalable Partitioning and Exploration of Chemical Spaces Using Geometric Hashing
Debojyoti Dutta
Joint work with Dr. Rajarshi Guha (PSU), Dr. Peter Jurs (PSU) and Dr. Ting Chen (USC)
Department of Computational and Molecular Biology, USC

Date: Monday, May 22, 2006
Time: 11:00 am
Location: Bourns A265

Virtual screening (VS) has become a preferred tool to augment high-throughput screening and determine new leads in the drug discovery process. The core of a VS informatics pipeline includes several data mining algorithms that work on huge databases of chemical compounds containing millions of molecular structures and their associated data. Thus, scaling traditional applications such as classification, partitioning, and outlier detection for huge chemical data sets without a significant loss in accuracy is very important. In this paper, we introduce a data mining framework built on top of a recently developed fast approximate nearest-neighbor-finding algorithm called locality-sensitive hashing (LSH) that can be used to mine huge chemical spaces in a scalable fashion using very modest computational resources. The core LSH algorithm hashes chemical descriptors so that points close to each other in the descriptor space are also close to each other in the hashed space. Using this data structure, one can perform approximate nearest-neighbor searches very quickly, in sublinear time. We validate the accuracy and performance of our framework on three real data sets of sizes ranging from 4337 to 249 071 molecules. Results indicate that the identification of nearest neighbors using the LSH algorithm is at least 2 orders of magnitude faster than the traditional /k/-nearest-neighbor method and is over 94% accurate for most query parameters. We also apply our framework to detect outlying (diverse) compounds in a given chemical space; this algorithm is extremely rapid in determining whether a compound is located in a sparse region of chemical space or not, and it is quite accurate when compared to results obtained using principal-component-analysis-based heuristics.

About the speaker:

Debojyoti Dutta is currently a postdoc at USC computational biology and works with Ting Chen. He got his PhD in computer science at USC in 2004, and an undergrad degree in computer science from IIT Kharagpur. His current research interests are in Chemoinformatics, Bioinformatics, Data Mining, and Networking.
More in Colloquia

More Information 

General Campus Information

University of California, Riverside
900 University Ave.
Riverside, CA 92521
Tel: (951) 827-1012

Department Information

Electrical and Computer Engineering
Suite 343 Winston Chung Hall
University of California, Riverside
Riverside, CA 92521-0429

Tel: (951) 827-2484
Fax: (951) 827-2425
E-mail: E-mail/Questions