Field-based similarity search system and method

• US 8,306,755 B2
• Filed: 05/23/2011
• Issued: 11/06/2012
• Est. Priority Date: 03/23/2001
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Pitman, Michael C., Fitch, Blake G., Horn, Hans W., Huber, Wolfgang, Rice, Julia E., Swope, William C.
• Primary Examiner(s): NEGIN, RUSSELL SCOTT
• Application Number:
  US13/113,256
• Publication Number:
  US 20110225148A1
• Time in Patent Office: 533 Days
• Field of Search: None
• US Class Current: 702/19
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/20 Sequence assembly
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis
• CPC Class Codes: G16B 40/30 Unsupervised data analysis
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: G16C 20/40 Searching chemical structures or physicochemical data

Abstract

A similarity search method includes generating a feature database which stores data pertaining to a candidate molecule, as executed by a processor of a computer, the database including a hash table having entries which are generated based on, a set of descriptors generated from conformations of fragment graphs of the candidate molecule, the fragment graphs including plural fragment nodes connected by rotatable bond edges, a specific conformation of the fragment node including a fragment of the candidate molecule, and two neighboring fragments connected by a rotatable bond at a specific dihedral angle including a fragment pair, and a context-adapted descriptor-to-key mapping which maps the set of descriptors to a set of feature keys including indices that label grid cells in discriminant space.

Claims

1. A similarity search method, comprising:

generating a feature database which stores data pertaining to a candidate molecule, as executed by a processor of a computer, said database comprising a hash table having entries which are generated based on;

a set of descriptors generated from conformations of fragment graphs of said candidate molecule, said fragment graphs including plural fragment nodes connected by rotatable bond edges, a specific conformation of said fragment node comprising a fragment of said candidate molecule, and two neighboring fragments connected by a rotatable bond at a specific dihedral angle comprising a fragment pair; and

a context-adapted descriptor-to-key mapping which maps said set of descriptors to a set of feature keys comprising indices that label grid cells in discriminant space;

generating scoops, descriptors and keys for a query molecule;

identifying a match between a query molecule fragment pair feature and a candidate molecule fragment pair feature by comparing said keys of said query molecule to said keys in said feature database, a correspondence comprising a scoop for said candidate molecule stored in said feature database having a same key as a scoop for said query molecule;

using said match to align a fragment pair of said candidate molecule to said query molecule by overlaying internal coordinate axes of said scoops for said candidate and query molecules, said correspondence implying an alignment of said candidate molecule and query molecule fragment pairs;

determining the number of candidate molecule fragment pairs the number of candidate molecule fragment pairs in the set, C_fp, being given by C_fp=(n−

1)·

(C_frag)²·

C_rbe, where n is the number of fragments in said candidate molecule and n−

1 is the number of rotatable bond edges connecting said n fragments, C_frag is the number of conformations in a fragment of said fragments, and C_rbe is the number of steps in which said rotatable bond edges are sampled;

assembling the entirety of the fragment pairs of said candidate molecule to form an alignment thereof onto said query molecule;

retrieving a candidate molecule fragment pair having at least a predetermined number of matching features; and

displaying a result of said retrieving said candidate molecule fragment pair.

2. The method according to claim 1, further comprising:

storing said query molecule fragment pair feature.

3. The method according to claim 1, further comprising:

storing data and instructions to be executed by the processor.

4. The method according to claim 1, wherein said processor identifies said query molecule fragment pair feature.

5. The method according to claim 4, wherein said processor matches a query molecule fragment pair feature with the candidate molecule fragment pair feature.

6. The method according to claim 5, wherein said processor retrieves a candidate molecule fragment pair having at least a predetermined number of matching features.

7. The method according to claim 1, wherein said processor identifies said candidate molecule which is similar to said query molecule by using a context-adaptive descriptor scaling procedure as a basis for similarity.

8. The method according to claim 1, wherein said database stores conformational space representation of said candidate molecule, and an input device inputs a conformational space representation of said query molecule.

9. The method according to claim 1, wherein said processor identifies corresponding features by comparing features of candidate molecule fragment pairs with the features of the query molecule fragment pairs.

10. The method according to claim 1, wherein said scoop of said query molecule comprises a sphere defined by a set of points within or around said query molecule.

11. The method according to claim 1, wherein said features of said candidate molecule fragment pair and query molecule fragment pair comprise generalizations of comparative molecular moment analysis descriptors.

12. The method according to claim 1, wherein an entry of said hash table refers to a fragment pair of said candidate molecule and describes an internal frame associated with a descriptor of said set of descriptors.

13. A method for finding alignments of a flexible molecule to a query molecule. said method comprising:

representing a conformation space of said flexible molecule;

generating an arbitrary description of a three-dimensional property field of said flexible molecule;

characterizing parts of said flexible molecule using said arbitrary description;

generating a feature database which stores data pertaining to said flexible molecule on a processor of a computer, said database comprising a hash table having entries which are generated based on;

a set of descriptors generated from conformations of fragment graphs of said flexible molecule, said fragment graphs including plural fragment nodes connected by rotatable bond edges, a specific conformation of said fragment node comprising a fragment of said flexible molecule, and two neighboring fragments connected by a rotatable bond at a specific dihedral angle comprising a fragment pair; and

a context-adapted descriptor-to-key mapping which maps said set of descriptors to a set of feature keys comprising indices that label grid cells in discriminant space;

representing a query molecule using said arbitrary description for a comparison with molecules represented by said conformation space by generating scoops, descriptors and keys for said query molecule;

identifying a match between a query molecule fragment pair feature and a flexible molecule fragment pair feature by comparing said keys of said query molecule to said keys in said feature database, a correspondence comprising a scoop for said flexible molecule stored in said feature database having a same key as a scoop for said query molecule;

aligning said parts of said flexible molecule to said query molecule by overlaying internal coordinate axes of said scoops for said flexible and query molecules, said correspondence implying an alignment of said flexible molecule and query molecule fragment pairs;

determining the number of said parts of said number of flexible molecule fragment pairs, the number of said parts of said number of flexible molecule fragment pairs in the set, C_fp, being given by C_fp=(n−

1)·

(C_frag)²·

C_rbe, where n is the number of fragments in said candidate molecule and n−

1 is the number of rotatable bond edges connecting said n fragments, C_frag is the number of conformations in a fragment of said fragments, and C_rbe is the number of steps in which said rotatable bond edges are sampled;

assembling said parts of said flexible molecule to form an alignment thereof onto said query molecule;

identifying a flexible molecule which is similar to said query molecule based on a result of said aligning said parts of said flexible and query molecules; and

displaying a result of said assembling said parts.

14. A non-transitory computer-readable storage medium encoded with a computer program executable by a digital processing apparatus to perform a similarity search method, said method comprising:

generating a conformational space representation and an arbitrary description of a three-dimensional property field for a flexible molecule;

generating a feature database which stores data pertaining to a flexible molecule, said database comprising a hash table having entries which are generated based on;

a set of descriptors generated from conformations of fragment graphs of said flexible molecule, said fragment graphs including plural fragment nodes connected by rotatable bond edges, a specific conformation of said fragment node comprising a fragment of said flexible molecule, and two neighboring fragments connected by a rotatable bond at a specific dihedral angle comprising a fragment pair; and

a context-adapted descriptor-to-key mapping which maps said set of descriptors to a set of feature keys comprising indices that label grid cells in discriminant space;

representing a query molecule using said arbitrary description for a comparison with said conformational space representation by generating scoops, descriptors and keys for said query molecule;

identifying a match between a query molecule fragment pair feature and a flexible molecule fragment pair by comparing said keys of said query molecule to said keys in said feature database, a correspondence comprising a scoop for said flexible molecule stored in said feature database having a same key as a scoop for said query molecule;

aligning said parts to said query molecule and assembling said parts to form an alignment onto said query molecule by overlaying internal coordinate axes of said scoops for said flexible and query molecules, said correspondence implying an alignment of said flexible molecule and query molecule fragment pairs;

determining the number of said parts of said number of flexible molecule fragment pairs, the number of said parts of said number of flexible molecule fragment pairs in the set. C_fp, being given by C_fp=(n−

1)·

(C_frag)²·

C_rbe, where n is the number of fragments in said candidate molecule and n−

1 is the number of rotatable bond edges connecting said n fragments, C_frag is the number of conformations in a fragment of said fragments, and C_rbe is the number of steps in which said rotatable bond edges are sampled;

identifying a flexible molecule which is similar to said query molecule based on a result of said aligning; and

displaying a result of said aligning said parts.