Method and apparatus for determining multi-dimensional structure

• US 6,345,235 B1
• Filed: 05/29/1998
• Issued: 02/05/2002
• Est. Priority Date: 05/30/1997
• Status: Expired due to Fees

• Current Assignee: Kenneth E. Edgecombe
• Original Assignee: Queen's University At Kingston
• Inventors: Ableson, Alan D., Edgecombe, Kenneth E.
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): TSAI, CAROL S W
• Application Number:
  US09/086,593
• Time in Patent Office: 1,348 Days
• Field of Search: 702/27, 702/21, 702/28, 702/32, 702/179, 702/180, 395/500.32, 395/500.33, 395/500.23, 703/1, 703/7, 703/11, 703/12
• US Class Current: 702/27
• CPC Class Codes: G16B 15/00 ICT specially adapted for analysing two-dimensional or three-dimensional molecular structures, e.g. structural or functional relations or structure alignment
• CPC Class Codes: G16B 15/20 Protein or domain folding
• CPC Class Codes: G16C 20/30 Prediction of properties of chemical compounds, compositions or mixtures

Abstract

This invention relates to methods and apparatus for determining the multi-dimensional topology of a substance (system) within a volume (space). A method according to a preferred embodiment of the invention comprises the steps of: acquiring a set of relative values for the density (scalar properties) of the volume, each value for a given location (point) within the volume; interpolating a set of functions to generate a continuous relative density for the volume; identifying critical points of the continuous relative density by using an eigenvector following method; and associating critical points with one another by following a gradient path of the continuous relative density between the critical points, The method is applicable to a wide range of data relating to fields such as crystallography, fluid dynamics, edge detection, and financial markets, to determine the topology of structures contained therein.

Claims

1. A method of determining the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of functions to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method;

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points; and

e) generating a representation of the topology according to the associated critical points.

5. The method of claim 1, 2 or 3, wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex.

2. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method;

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points; and

d) generating a representation of the topology according to the associated critical points.

3. A method of determining the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method;

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points; and

c) generating a representation of the topology according to the associated critical points.

4. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume; and

c) identifying critical points of the continuous relative density by using an eigenvector following method;

wherein the step of identifying critical points is performed in 3 dimensions.

6. A method of determining the multi-dimensional topology of a system within a space, the method comprising the steps of:

a) acquiring a set of relative values for scalar properties of the space, each value for a given point within the space;

b) interpolating a set of functions to generate continuous relative values for the scalar properties;

c) identifying critical points of the continuous relative values by using an eigenvector following method;

d) associating critical points with one another by following a gradient path of the continuous relative values between the critical points; and

e) generating a representation of the topology according to the associated critical points.

10. The method of claim 6, 7 or 8 wherein the system is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex.

11. The method of claim 6, wherein the system is the flow of a fluid over a surface.

12. The method of claim 6, wherein the system is the reaction and/or folding of a protein or protein complex.

13. The method of claim 6, wherein the system is an edge portion of a graphical image.

14. The method of claim 6, wherein the system is one or more extremal points within a scalar field.

15. The method of claim 6, wherein the system is a trend or energy surface within a set of data.

7. A method of determining the multi-dimensional topology of a system within a space from a set of relative values for scalar properties of the space, each value for a given point within the space, the method comprising the steps of:

a) interpolating a set of functions to generate continuous relative values for the scalar properties;

b) identifying critical points of the continuous relative values by using an eigenvector following method;

c) associating critical points with one another by following a gradient path of the continuous relative values between the critical points; and

d) generating a representation of the topology according to the associated critical points.

8. A method of determining the multi-dimensional topology of a system within a space, having continuous relative values of scalar properties for the space generated from a set of functions interpolating a set of acquired relative values of the scalar properties, each value for a given location within the space, the method comprising the steps of:

a) identifying critical points of the continuous relative values by using an eigenvector following method;

b) associating critical points with one another by following a gradient path of the continuous relative values between the critical points; and

c) generating a representation of the topology according to the associated critical points.

9. A method of identifying critical points in the multi-dimensional topology of a system within a space, the method comprising the steps of:

a) acquiring a set of relative values for properties of the space, each value for a given point within the space;

b) interpolating a set of functions to generate continuous relative values for the space; and

c) identifying critical points of the continuous relative values by using an eigenvector following method;

wherein the steps of identifying critical points is performed in 3 dimensions.

16. A method of determining the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of functions to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

17. A method of determining the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of functions to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

18. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume; and

c) identifying critical points of the continuous relative density by using an eigenvector following method;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

19. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation.

20. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume; and

c) identifying critical points of the continuous relative density by using an eigenvector following method;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation.

21. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation using third order splines.

22. A method of identifying critical points in the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of function to generate a continuous relative density for the volume; and

c) identifying critical points of the continuous relative density by using an eigenvector following method;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation using third order splines.

23. A method of determining the multi-dimensional topology of a substance within a volume, the method comprising the steps of:

a) acquiring a set of relative density values for the volume, each value for a given location within the volume;

b) interpolating a set of functions to generate a continuous relative density for the volume;

c) identifying critical points of the continuous relative density by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.

24. A method of determining the multi-dimensional topology of a system within a space, the method comprising the steps of:

a) acquiring a set of relative values for scalar properties of the space, each value for a given point within the space;

b) interpolating a set of functions to generate continuous relative values for the scalar properties;

c) identifying critical points of the continuous relative values by using an eigenvector following method; and

d) associating critical points with one another by following a gradient path of the continuous relative values between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.

25. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

26. A method of determining the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

27. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

28. A method of determining the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein, as part of the step of associating critical points, critical points that are passes are each associated with two, and only two, critical points that are peaks.

29. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation.

30. A method of determining the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation.

31. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation using third order splines.

32. A method of determining in the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the substance is a protein or a protein complex, and the relative density values are electron density values generated by x-ray diffraction through a crystal of the protein or protein complex; and

wherein the step of interpolating a set of functions includes a global fitting of a polynomial approximation using third order splines.

33. A method of determining the multi-dimensional topology of a substance within a volume from a set of relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) interpolating a set of functions to generate a continuous relative density for the volume;

b) identifying critical points of the continuous relative density by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.

34. A method of determining the multi-dimensional topology of a substance within a volume, having a continuous relative density for the volume generated from a set of functions interpolating a set of acquired relative density values for the volume, each value for a given location within the volume, the method comprising the steps of:

a) identifying critical points of the continuous relative density by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative density between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.

35. A method of determining the multi-dimensional topology of a system within a space from a set of relative values for scalar properties of the space, each value for a given point within the space, the method comprising the steps of:

a) interpolating a set of functions to generate continuous relative values for the scalar properties;

b) identifying critical points of the continuous relative values by using an eigenvector following method; and

c) associating critical points with one another by following a gradient path of the continuous relative values between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.

36. A method of determining the multi-dimensional topology of a system within a space, having continuous relative values of scalar properties for the space generated from a set of functions interpolating a set of acquired relative values of the scalar properties, each value for a given location within the space, the method comprising the steps of:

a) identifying critical points of the continuous relative values by using an eigenvector following method; and

b) associating critical points with one another by following a gradient path of the continuous relative values between the critical points;

wherein the steps of identifying critical points and associating critical points are performed in 3 dimensions.