<< Chapter < Page Chapter >> Page >

From the Delaunay triangulation the α-shape is computed by removing all edges, triangles, and tetrahedra that have circumscribing spheres withradius greater than α. Formally, the α-complex is the part of the Delaunay triangulation that remains after removing edges longer than α. The α-shape is the boundary of the α-complex.

Pockets can be detected by comparing the α-shape to the whole Delauney triangulation. Missing tetrahedra represent indentations, concavity, and generally negative space in the overall volume occupied by the protein. Particularly large or deep pockets may indicate a substrate binding site.

Weighted alpha shapes

Regular α-shapes can be extended to deal with varying weights (i.e., spheres with different radii, such as different types of atoms) . The formal definitions become complicated, but the key idea is to use a pseudo distance measure that uses the weights.Suppose we have two atoms at positions p1 and p2 with weights w1 and w2. Then the pseudo distance is defined as the square of the Euclidean distance minus the weights. The pseudo distanceis zero if and only if two spheres centered at p1 and p2 with radii equal to sqrt(w1) and sqrt(w2) are just touching.

Pseudo distance to account for atoms of different sizes.

Calculating molecular volume using α-shapes

The volume of a molecule can be approximated using the space-filling model, in which each atom is modeled as a ball whose radius is α, where α is selected depending on the model being used: Van der Waals surface, molecular surface, solvent accessible surface, etc. Unfortunately, calculating the volume is not as simple as taking the sum of the ball volumes because they may overlap. Calculating the volume of a complex of overlapping balls is non-trivial because of the overlaps. If two spheres overlap, the volume is the sum of the volumes of the spheres minus the volume of the overlap, which was counted twice. If three overlap, the volume is the sum of the ball volumes, minus the volume of each pairwise overlap, plus the volume of the three-way overlap, which was subtracted one too many times in accounting for the pairwise overlaps. In the general case, all pairwise, three-way, four-way and so on to n-way intersections (assuming there are n atoms) must be considered. Proteins generally have thousands or tens of thousands of atoms, so the general n-way case may be computationally expensive and may introduce numerical error.

Three overlapping discs (balls if three dimensional). Calculating the total area (volume if three dimensional) of the balls requires summing the areas of each ball, then subtracting out the pairwise intersection areas, since each was counted once for each ball it is inside. Then the intersection area of the three balls must be added back because, although it was added three times initially, it was also subtracted once in each of the three pairwise intersections. In the general case, with n balls, all of which may overlap, intersections of odd numbers of balls are added, and intersections of even numbers of balls subtracted, to calculate the total area or volume.

α-shapes provide a way around this undesirable combinatorial complexity , and this issue has been one of the motivating factors for introducing α-shapes. To calculate the volume of a protein, we take the sum of all ball volumes, then subtract only those pairwise intersections for which a corresponding edge exists in the α-complex. Only those three-way intersections for which the corresponding triangle is in the α-complex must then be added back. Finally, only four-way intersections corresponding to tetrahedra in the α-complex need to be subtracted. No higher-order intersections are necessary, and the number of volume calculations necessary corresponds directly to the complexity of the α-complex, which is O(n log n) in the number of atoms.

An example of how this approach works is given on page 4 of the Liang et al. article in the Recommended Reading section below. A proof of correctness and derivation is also provided in the article. Surface area calculations, such as solvent-accessible surface area, which is often used to estimate the strength of interactions between a protein and the solvent molecules surrounding it, are made by a similar use of the α-complex.

  • H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. [PDF] . "On the Shape of a Set of Points in the Plane." IEEE Transactions on Information Theory, 29(4):551-559, 1983. This is the original α-shapes paper (caution: the definition of α is different from that used in later papers--it is the negative reciprocal of α as presented above).
  • H. Edelsbrunner and E.P. Mucke. [PDF] . "Three-dimensional Alpha Shapes." Workshop on Volume Visualization, Boston, MA. pp 75-82. 1992. This article shows how to extend α-shapes to three-dimensional point sets.
  • J. Liang, H. Edelsbrunner, P. Fu, P.V. Sudhakar, and S. Subramaniam. [PDF] . Analytical shape computation of macromolecules: I. molecular area and volume through alpha shape. Proteins: Structure, Function, and Genetics, 33:1-17, 1998. This is a paper on using α-shapes to speed up volume and surface area calculations for molecular models.
  • H. Edelsbrunner, M.Facello and Jie Liang. [PDF] . On the definition and the construction of pockets in macromolecules. Discrete and Applied Mathematics, 88:83-102, 1998.


Questions & Answers

If potatoes cost Jane $1 per kilogram and she has $5 that could possibly spend on potatoes or other items. If she feels that the first kilogram of potatoes is worth $1.50, the second kilogram is worth$1.14, the third is worth $1.05 and subsequent kilograms are worth $0.30, how many kilograms of potatoes will she purchase? What if she only had $2 to spend?
Susan Reply
cause of poverty in urban
DAVY Reply
QI: (A) Asume the following cost data are for a purely competitive producer: At a product price Of $56. will this firm produce in the short run? Why Why not? If it is preferable to produce, what will be the profit-maximizing Or loss-minimizing Output? Explain. What economic profit or loss will the
Falak Reply
what is money
DAVY Reply
what is economic
Stephen Reply
economics is the study of ways in which people use resources to satisfy their wants
what is Price mechanism
Dhany Reply
introduction to economics
Uday Reply
welfare definition of economics
examine the wealth and welfare definitions of economics
read book by ml jhingan
What do we mean by Asian tigers
Aeesha Reply
Dm me I will tell u
What is Average revenue
How are u doing
it is so fantastic
it is a group of 4 countries named Singapore, South Korea, Taiwan and Hong Kong because their economies are growing very faster
what's a demand
Edward Reply
it is the quantity of commodities that consumers are willing and able to purchase at particular prices and at a given time
quantity of commodities dgat consumers are willing to pat at particular price
demand depends upon 2 things 1wish to buy 2 have purchasing power of that deserving commodity except any from both can't be said demand.
Demand is a various quantity of a commodities that a consumer is willing and able to buy at a particular price within a given period of time. All other things been equal.
State the law of demand
The desire to get something is called demand.
what is the use of something should pay for its opportunity foregone to indicate?
Random Reply
Why in monopoly does the firm maximize profits when its marginal revenue equals marginal cost
astrid Reply
different between economic n history
Falma Reply
If it is known that the base change of RM45 million, the statutory proposal ratio of 7 per cent, and the public cash holding ratio of 5 per cent, what is the proposed ratio of bank surplus to generate a total deposit of RM 300 million? 
Jeslyne Reply
In a single bank system, a bank can create a deposit when it receives a new deposit in cash. If a depositor puts a cash deposit of RM10,000 into the bank, assume the statutory reserve requirement is 7% and the bank adopts a surplus reserve of 8%. a. Calculate the amount of deposits made at the end o
the part of marginal revenue product curve lies in the _ stage of production is called form demand curve for variable input.
Bashir Reply
The cost associated with the inputs owned by the farmer is termed as
the cost associated with inputs owned by the farmer is termed as ____
why do we study economic
Nwobodo Reply
we study economics to know how to manage our limited resources
we study economics the know how to use our resources and where to put it
what is end
we study economics to make rational decision
we study economics only to know how to effectively and efficiently allocate our limited resource in other to meet our unlimited wants
We study economics inorder for us to know the difference of the needs and wants and aslo how to use the limited resources that are available
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play

Source:  OpenStax, Geometric methods in structural computational biology. OpenStax CNX. Jun 11, 2007 Download for free at http://cnx.org/content/col10344/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Geometric methods in structural computational biology' conversation and receive update notifications?