View in EDS

Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR.

Saved in:
Bibliographic Details
Title: Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR.
Authors: Pierre Baldi, Daniel S. Hirschberg, Ramzi J. Nasr
Source: Journal of Chemical Information & Modeling. Jun2008, Vol. 48 Issue 7, p1367-1378. 12p.
Subjects: Cheminformatics, Database searching, Molecular structure, Graph theory, Chemical structure, Physical & theoretical chemistry research
Abstract: In many large chemoinformatics database systems, molecules are represented by long binary fingerprint vectors whose components record the presence or absence in the molecular graphs of particular functional groups or combinatorial features, such as labeled paths or labeled trees. To speed up database searches, we propose to store with each fingerprint a small header vector containing primarily the result of applying the logical exclusive OR (XOR) operator to the fingerprint vector after modulo wrapping to a smaller number of bits, such as 128 bits. From the XOR headers of two molecules, tight bounds on the intersection and union of their fingerprint vectors can be rapidly obtained, yielding tight bounds on derived similarity measures, such as the Tanimoto measure. During a database search, every time these bounds are unfavorable, the corresponding molecule can be rapidly discarded with no need for further inspection. We derive probabilistic models that allow us to estimate precisely the behavior of the XOR headers and the level of pruning under different conditions in terms of similarity threshold and fingerprint density. These theoretical results are corroborated by experimental results on a large set of molecules. For a Tanimoto threshold of 0.5 (respectively 0.9), this approach requires searching less than 50% (respectively 10%) of the database, leading to typical search speedups of 2 to 3 times over the previous state-of-the-art. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Chemical Information & Modeling is the property of American Chemical Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 44636563
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Pierre+Baldi%22">Pierre Baldi</searchLink><br /><searchLink fieldCode="AR" term="%22Daniel+S%2E+Hirschberg%22">Daniel S. Hirschberg</searchLink><br /><searchLink fieldCode="AR" term="%22Ramzi+J%2E+Nasr%22">Ramzi J. Nasr</searchLink>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Chemical+Information+%26+Modeling%22">Journal of Chemical Information & Modeling</searchLink>. Jun2008, Vol. 48 Issue 7, p1367-1378. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Cheminformatics%22">Cheminformatics</searchLink><br /><searchLink fieldCode="DE" term="%22Database+searching%22">Database searching</searchLink><br /><searchLink fieldCode="DE" term="%22Molecular+structure%22">Molecular structure</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Chemical+structure%22">Chemical structure</searchLink><br /><searchLink fieldCode="DE" term="%22Physical+%26+theoretical+chemistry+research%22">Physical & theoretical chemistry research</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In many large chemoinformatics database systems, molecules are represented by long binary fingerprint vectors whose components record the presence or absence in the molecular graphs of particular functional groups or combinatorial features, such as labeled paths or labeled trees. To speed up database searches, we propose to store with each fingerprint a small header vector containing primarily the result of applying the logical exclusive OR (XOR) operator to the fingerprint vector after modulo wrapping to a smaller number of bits, such as 128 bits. From the XOR headers of two molecules, tight bounds on the intersection and union of their fingerprint vectors can be rapidly obtained, yielding tight bounds on derived similarity measures, such as the Tanimoto measure. During a database search, every time these bounds are unfavorable, the corresponding molecule can be rapidly discarded with no need for further inspection. We derive probabilistic models that allow us to estimate precisely the behavior of the XOR headers and the level of pruning under different conditions in terms of similarity threshold and fingerprint density. These theoretical results are corroborated by experimental results on a large set of molecules. For a Tanimoto threshold of 0.5 (respectively 0.9), this approach requires searching less than 50% (respectively 10%) of the database, leading to typical search speedups of 2 to 3 times over the previous state-of-the-art. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Chemical Information & Modeling is the property of American Chemical Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=44636563
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1021/ci800076s
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 1367
    Subjects:
      – SubjectFull: Cheminformatics
        Type: general
      – SubjectFull: Database searching
        Type: general
      – SubjectFull: Molecular structure
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Chemical structure
        Type: general
      – SubjectFull: Physical & theoretical chemistry research
        Type: general
    Titles:
      – TitleFull: Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Pierre Baldi
      – PersonEntity:
          Name:
            NameFull: Daniel S. Hirschberg
      – PersonEntity:
          Name:
            NameFull: Ramzi J. Nasr
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 11
              M: 06
              Text: Jun2008
              Type: published
              Y: 2008
          Identifiers:
            – Type: issn-print
              Value: 15499596
          Numbering:
            – Type: volume
              Value: 48
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: Journal of Chemical Information & Modeling
              Type: main
ResultId 1