FIELD-BASED SIMILARITY SEARCH SYSTEM AND METHOD

• US 20110225148A1
• Filed: 05/23/2011
• Published: 09/15/2011
• Est. Priority Date: 03/23/2001
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Huber, Wolfgang, Rice, Julia E., Pitman, Michael C., Horn, Hans W., Fitch, Blake G., Swope, William C.
• Granted Patent: US 8,306,755 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• 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;

assembling 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 a 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 features of 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. 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;

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.

12. 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 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 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;

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.