System and method for confirmationally-flexible molecular identification

• US 5,752,019 A
• Filed: 12/22/1995
• Issued: 05/12/1998
• Est. Priority Date: 12/22/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rigoutsos, Isidore, Califano, Andrea
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/577,759
• Time in Patent Office: 872 Days
• Field of Search: 395/615, 395/603, 395/606, 364/496, 364/497
• US Class Current: 1/1
• CPC Class Codes: G16C 20/40 Searching chemical structures or physicochemical data
• CPC Class Codes: G16C 20/90 Programming languages; Computing architectures; Database systems; Data warehousing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A reference storage process populates a data structure so that the data structure contains all of the molecular structures and/or rigid substructures in the database classified according to attributes of tuples. In a preferred embodiment, the tuples are derived from sites (e.g. atomic sites) of the molecular structures and the attributes can be derived from geometric (and other) information related to the tuples. The attributes are used to define indices in the data structure that are associated with invariant vector information (e.g. information about rotatable bond(s) in skewed local coordinate frames created from tuples). These representations are invariant with respect to the rotation and translation of molecular structures and/or the rotation of substructures about attached rotatable bond(s). Accordingly, the invariant vector information is classified in the data structure with the respective tuple attributes in locations determined by the index derived from the respective tuple. A matching process creates one or more tuples, skewed local reference frames, and indices (called test frame tuple indices) for the structure (substructures) of a test molecule using the same technique that was used to populate the data structure. The test frame tuple index accesses the invariant vector information and tallies the frequency of matching in order to determine the identity of molecules/substructures in the database that are structurally similar to the test molecule. This identification can be achieved even in the presence of conformationally flexible molecules in the database.

Claims

1. A method for storing a representation of one or more reference molecules in a memory in a computer system, the method executed on a computer system and comprising the steps of:

a. identifying either one or more rigid substructures of the reference molecule, each of the rigid substructures having one or more atomic sites, each of the atomic sites being connected to zero or more atomic sites in the rigid substructure with a non-rotatable bond, each rigid substructure having a global position and a global orientation in a global coordinate frame;

b. defining a vector with a magnitude and direction with a fixed position and orientation with respect to the rigid substructure;

c. selecting a set of three or more sites, the set of sites forming a frame tuple, at least one of the sites being non-colinear with the remaining sites, the sites being in a fixed position with respect to the rigid substructure, and the frame tuple defining a three-dimensional skewed local coordinate frame;

d. selecting one or more of the frame tuples and generating a frame tuple field with information associated with each of the selected frame tuples; and

e. storing a record in a data structure, the data structure having a plurality of records, each record containing the frame tuple field and a vector field, the vector field containing vector information relating to the vector as well as information about the identities of the molecule and rigid substructure having the sites forming the frame tuple.

2. A method, as in claim 1, where the information in the frame tuple field is an index.

3. A method, as in claim 2, where the index is derived from physical information that is characteristic, of one or more of the sites of the frame tuple.

4. A method, as in claim 3, where the index is derived from chemical information that is characteristic of one or more of the sites of the frame tuple.

5. A method, as in claim 2, where the index is derived from geometric information relating to zero or more of the sites of the frame tuple, physical information that is characteristic of zero or more of the sites of the frame tuple, and chemical information that is characteristic of zero or more of the sites of the frame tuple.

6. A method, as in claim 3, where the index is derived from geometric information relating to the set of sites.

7. A method, as in claim 3, where the index is derived from one or more of the distances between any two sites in the set of sites.

8. A method, as in claim 3, where the index is derived from one or more of the angles in one or more of the triangles formed by any 3 sites in the set of sites.

9. A method, as in claim 3, where the index is derived from a combination of zero or more angles in one or more of the triangles formed by any three sites in the set of sites and zero or more distances between any two sites of the set of sites.

10. A method, as in claim 3, where the index is derived from areas formed by using at least three sites in the subset of sites.

11. A method, as in claim 3, where the index is derived from ratios of areas formed by using at least three sites in the subset of sites.

12. A method, as in claim 1, where the vector information further includes other information.

13. A method as in claim 12, where the other information includes any one or more of the following:

molecular identity, substructure identity, atomic site information, and non-atomic site information, and information about the cardinality and identity of the vector.

14. A method as in claim 13, where the other information further includes any one or more of the following:

physical properties, and chemical properties.

15. A method, as in claim 14, where one or more of the sites in the set of sites is an atomic site rigidly connected to the rigid substructure.

16. A method, as in claim 15, where one or more of the sites is a non-atomic site.

17. A method, as in claim 16, where one of the sites is a first site on a first rigid substructure and another site is a second site on a second rigid substructure, and the first and second rigid substructures are connected via a rotatable bond.

18. A method, as in claim 17, where the first and second sites can be any of the following:

an atomic site and a non-atomic site.

19. A method, as in claim 18, where the first site is a first atomic site, the second site is a second atomic site, and the vector has the position, magnitude and orientation of a rotatable bond connecting the first and second atomic sites.

20. A method, as in claim 19, comprising the further step of:

f. repeating steps d and e for one or more of the unselected frame tuples.

21. A method, as in claim 20, where steps d and e are repeated for all of the unselected frame tuples.

22. A method, as in claim 20, comprising the further step of:

g. repeating steps c-f for one or more of the unselected set of sites.

23. A method, as in claim 22, where steps c-f are repeated for all of the unselected sets of sites.

24. A method, as in claim 21, comprising the further step of:

h. repeating steps b-g for the remaining rigid substructure in the case where a pair of substructures was selected.

25. A method, as in claim 24, where steps b-g are repeated for all of the unselected pairs of substructures that are connected with a rotatable bond.

26. A method, as in claim 24, comprising the further step of:

i. repeating steps a-h for one or more unselected molecules.

27. A method, as in claim 26, where steps a-i are repeated for all unselected molecules.

28. A method, as in claim 19, where the vector information uniquely identifies the vector in the skewed local coordinate frame and the vector information remains invariant under any rotation and translation of the set of sites defining the skewed local coordinate frame.

29. A method, as in claim 28, where the vector information is information about an identity, a position, a vector magnitude and a vector orientation of each of the vectors represented in the local skewed coordinate frame.

30. A method, as in claim 29, where the vector information contains the projection of the vector on one or more axes of the local skewed coordinate frame.

31. A method as in claim 29 where two or more of the sites are atomic sites of the molecule including a first and second atomic site and the first and second atomic site define the position, magnitude and orientation of the vector.

32. A method as in claim 29, where the vector information includes a point position of a fixed point along the length of the vector, the vector magnitude, and the vector orientation.

33. A method as in claim 29, where the vector information includes the position being determined by two vector sites, the vector sites being sites in the set of sites, and the vector information further including the magnitude and the orientation of the vector.

34. A method as in claim 33, where one or more of the vector sites is an atomic site.

35. A method as in claim 34, where one or more of the vector sites is a non-atomic site.

36. A method as in claim 29, where the position, magnitude and orientation of the vector are represented by a matrix.

37. A method for storing a representation of one or more reference molecules in the memory of a computer system, the method executed on a computer system and comprising the steps of:

a. identifying one or more rigid substructures of the reference molecule, each of the rigid substructures having one or more atomic sites, each of the atomic sites being connected to zero or more atomic sites with a non-rotatable bond, and each rigid substructure having a global position and a global orientation in a global coordinate frame;

b. defining a vector with a vector magnitude and a vector direction, the vector being fixed in position and orientation with respect to the rigid substructure;

c. selecting a set of three or more sites, the sites being in a fixed position with respect to the rigid substructure and any set of sites being a frame tuple that defines a skewed local coordinate frame, the skewed local coordinate frame having two or more sides, with an angle between one or more pairs of the sides;

d. selecting one or more frame tuples and generating one or more indices from information about each of the selected frame tuples; and

e. storing a record in a data structure stored in the memory, the data structure having a plurality of records, and each of the records containing vector information associated with one of the indices and accessible by using the index.

38. A method, as in claim 37, where the index is generated from information from two of the sides, being a first side and a second side, and a first angle being the angle between the first and second sides.

39. A method, as in claim 38, where either the first or the second side has a magnitude above a length threshold.

40. A method, as in claim 38, where the first side is the longest side in the triangle formed by the three members of the frame tuple, and the second side is the second longest side of the triangle formed by the three members of the frame tuple.

41. A method, as in claim 40, where the first angle has a magnitude above an angle threshold.

42. A method, as in claim 41, where the angle threshold is 10 degrees.

43. A method, as in claim 37, where the first angle is the largest angle in the triangle formed by the three members of the frame tuple.

44. A method, as in claim 37, where the index is generated from information that further includes the chemical characteristics of one or more of the atomic sites participating in the frame tuple.

45. A method for determining the identity of one or more reference molecules that are structurally similar to a test molecule, the method executed on a computer system and comprising the steps of:

a. identifying one or more rigid test substructures of the test molecule, each of the rigid test substructures having one or more atomic sites, each of the atomic sites being connected to zero or more atomic sites in the rigid test substructure with a non-rotatable bond, each rigid test substructure having a certain position and a certain orientation in a three-dimensional global reference frame;

b. selecting a set of three or more test sites, the set of test sites being a test frame tuple, at least one of the test sites being non-colinear with the remaining test sites, the test sites being in a fixed position with respect to the rigid test substructure, and each of the test frame tuples defining a three-dimensional skewed local test coordinate frame;

c. selecting one or more of the test frame tuples and generating a test frame tuple index from information associated with the selected test frame tuple;

d. using the test frame tuple index, accessing one or more records in a data structure stored in the memory, the data structure having a plurality of records, each of the records containing a reference frame tuple field and a reference vector information field, the reference frame tuple field having a reference frame tuple index generated from a reference frame tuple defined by three or more reference sites on a rigid reference substructure of one of the reference molecules, the reference vector field having one or more entries, each entry containing reference vector information about the reference vector having a magnitude and direction and a fixed position and a fixed orientation with respect to one or more rigid reference substructures, each entry further having reference frame tuple information about the reference frame tuple, reference molecule identity information, and reference frame rigid substructure information;

e. for each entry in each record with a reference frame tuple index matching the test frame tuple index, constructing a test vector for each reference vector in the skewed local test coordinate frame in order to place the test vector in the global coordinate frame;

f. for each entry in each record with a reference frame tuple index matching the test frame tuple index, producing a voting record in a voting data structure, the voting record containing the reference molecule identity information, the rigid reference substructure identity information, a test vector position field with a position value and test vector orientation field with an orientation value, the position value matching the test vector positions the orientation value matching the test vector orientation, the molecule identity information matching the reference molecule identity, and the rigid reference substructure information field matching the reference substructure identity.

46. A method as in claim 45, where the reference frame tuple index is generated from the reference frame tuple and the test frame tuple index is generated from the selected test frame tuple by the same method.

47. A method as in claim 45, comprising the further step of:

g. repeating steps c-f for one or more of the unselected test frame tuples.

48. A method, as in claim 45, where steps c-f are repeated for all of the unselected test frame tuples.

49. A method, as in claim 47, comprising the further step of:

h. repeating steps b-g for one or more of the unselected set of test sites.

50. A method, as in claim 49, where steps b-g are repeated for all of the unselected sets of sites.

51. A method, as in claim 49, comprising the further step of:

i. repeating steps a-g for one or more of the unselected rigid test substructures.

52. A method, as in claim 51, where steps a-g are repeated for all of the unselected test substructures.

53. A method as in claim 51, where a multiplicity of occurrence is determined for one or more identical voting records, for each of one or more sets of identical voting records.

54. A method, as in claim 53, where the sets of voting records having a multiplicity value below a threshold are eliminated.

55. A method, as in claim 53, where the voting table record having the highest multiplicity of occurrence contains the identity of the reference molecule matching the test molecule, and the identity of the rigid reference substructure matching one or more of the test molecule rigid substructures.

56. A computer system for storing a representation of one or more reference molecules in a memory in the computer system and for comparing one or more of the reference molecules to a test molecule, comprising:

a. a database stored in the memory, the database having a representation of one or more rigid substructures of each of the reference molecules, each of the rigid substructures having one or more atomic sites, each of the atomic sites being connected to zero or more atomic sites in the rigid substructure with a non-rotatable bond, each rigid substructure having a global position and a global orientation in a global coordinate frame;

b. a set of three or more sites, the set of sites being in a selected rigid substructure, the set of sites forming a frame tuple, at least one of the sites being non-colinear with the remaining sites, the sites being in a fixed position with respect to the selected rigid substructure, and the frame tuple defining a three-dimensional skewed local coordinate frame; and

c. a data structure, having a plurality of records, each record containing a frame tuple field and a vector field, the vector field containing vector information relating to each of one or more vectors as well as information about the identities of one or more of the molecules and one or more of the rigid substructures, each of the vectors having a magnitude and a direction, and a fixed position and orientation with respect to the selected rigid substructure and the selected rigid substructure being one of the rigid substructures.

57. A computer system, as in claim 56, further having a voting data structure, the voting data structure having a plurality of voting records, each of the voting records containing information including a reference molecule identity, a reference frame rigid substructure identity, and a placement information for each of one or more test vectors in the global coordinate frame having a test frame tuple index that is the same as a reference frame tuple index associated with the frame tuple field and the vector field, the test frame tuple index generated for each of one or more selected test frame tuples of the text molecule and from information associated with the selected test frame tuple, each of the selected test frame tuples being formed from a set of three or more test sites of the test molecule, at least one of the test sites being non-colinear with the remaining test sites, the test sites being in a fixed position with respect to the rigid test substructure on the test molecule, and each of the test frame tuples defining a three-dimensional skewed local test coordinate frame.

58. A system, as in claim 57, where a multiplicity of occurrence is determined for one or more identical voting records, for each of one or more sets of identical voting records.

59. A system, as in claim 58, where the sets of voting records having a multiplicity value below a threshold are eliminated.

60. A computer system for storing a representation of one or more reference molecules in a memory in the computer system and for comparing one or more of the reference molecules to a test molecule, comprising:

a. a database means stored in the memory, the database means for representing one or more rigid substructure means of each of the reference molecules, each of the rigid substructure means having one or more atomic site means, each of the atomic site means being connected to zero or more atomic site means in the rigid substructure means with a non-rotatable bond, each rigid substructure means having a global position and a global orientation in a global coordinate frame;

b. a set of three or more site means, the set of sites being in a selected rigid substructure means, the set of site means forming a frame tuple means, at least one of the site means being non-colinear with the remaining site means, the site means being in a fixed position with respect to the selected rigid substructure means, and the frame tuple means defining a three-dimensional skewed local coordinate frame means; and

c. a data structure means for storing, a plurality of record means, each record means containing a frame tuple field and a vector field, the vector field containing vector information relating to each of two or more rectors as well as information about the identities of one or more of the molecules and one or more of the rigid substructure means, each of the vectors having a magnitude and a direction with a fixed position and orientation with respect to the selected rigid substructure means and the selected rigid substructure means being one of the rigid substructure means.