Chapter 50Computational Topology and Protein Structure
Topology
Protein biochemists sometimes use the word “geometry” to describe the local geometric structure of a protein, and the word “topology” to describe more global, shapelike features. Strictly speaking, this is an abuse of notation, since the term topology refers to properties that are invariant under any embedding into any space. Nevertheless, the rigorous mathematical notions of topological invariance are quite useful to analyze protein structure.
The term homology has precise meanings in both biology and mathematics. While the meanings are related, they are different. In this chapter, we use the term in its mathematical sense. We will start with some basic definitions, to build intuition.
Suppose we are given the structure coordinates of a protein. Such a protein can be represented by a triangulation, in which the atomic positions are taken to be a set of vertices , and these vertices are connected by edges. Next, the edges form triangles. The triangles then make up the faces of tetrahedra. Alternatively, a Delaunay triangulation of the set of points representing atomic nuclei could be constructed. Or, the surface of the protein might be triangulated. In all three cases, the basic object of study is a triangulation, which is used as an approximation to the protein shape and structure. The Delaunay triangulation is the geometric dual of the Voronoi diagram. Triangulations arise in a wide variety of settings in computational science, and so we will discuss them somewhat generally. In computational structural biology, as well as other applications, the value proposition is that the detailed geometric and topological properties of the triangulation can be studied to understand the mechanism and function of the biological macromolecule.
In a triangulation (which mathematicians call a complex), triangles have an orientation (intuitively, clockwise or counterclockwise), which defines their sign (+1 or -1). This notion can be generalized to an orientation for tetrahedra. Moreover, the triangles and tetrahedra in a complex can either be filled (solid), or empty (holes). Homology groups are sometimes introduced as a measure of “counting these holes” (where their signs can be positive or negative) in each dimension. Although this intuition is reasonable, it is highly simplified, and does not describe the algebraic power of homology groups to compute and compare the topology of complicated geometric objects such as proteins.
We describe an algorithm for computing the homology type of a triangulation. By triangulation we mean a finite simplicial complex; its homology type is given by its homology groups (with integer coefficients). The algorithm could be used in structural biology to tell whether two finite-element meshes or Bézier-spline surfaces representing solvent accessible protein surfaces are of the same “topological type.” Finally, if a triangulation is defined by a network of NOEs, we might ask, using topological methods, whether it can be embedded in . Homology computation is also a purely combinatorial problem of considerable intrinsic interest.
Homology
In this chapter, we study computing all the homology groups of a triangulation. In protein structure analysis and computer-aided design (CAD), many geometric objects are triangulations. For example, finite-element methods use 2D and 3D triangulations of solids, called finite-element meshes. Triangular parametric surfaces such as rational Bézier surfaces are widely used in geometric modeling systems [41]. A collection of these objects is, topologically, a triangulation (a 3D finite-element tetrahedralization is simply a 3D triangulation). Furthermore, algorithms exist for triangulating polygons and tetrahedra, and the problem of triangulating algebraic varieties has been studied by Hironaka, McCallum, and others [14, 31].
Intuitively, a -simplex is a convex hull of linearly (affinely) independent points, called the vertices of the simplex. A set of these simplices, with appropriate adjacency conditions, is called a simplicial complex. In this chapter we will adopt the following:
Definition 50.1 A triangulation is a finite simplicial complex.
Thus, a triangular parametric surface will be regarded as a homeomorph of a triangulation. Since homology type is a topological invariant, it is the same for all homeomorphs of a triangulation, and for all other triangulations of the same geometric object.
In structural biology and NOE network analysis, we might construct triangulations (either by machine or by hand), and then modify them incrementally in the protein design or NOE assignment process. These modifications can involve adding new triangles and tetrahedra, identifying edges and vertices, and so on. We wish to ask, when are two triangulations “topologically equivalent”? For example, we may wish to compute whether two protein designs have the same “topological type.” Alternatively, after modifying a design, we wish to know whether its “topology” has been altered. Indeed, the topological type of a design may be taken as a design specification, or as an invariant, which no modeling operation should violate. Finally, we are interested in the physical realizability of a geometric protein design. One basic question we may ask is, “Can the design be embedded in Euclidean space ()?” In general these questions are very hard [13]. One way to attack this problem is to search for computable topological invariants. For example, one topological invariant we might consider is the fundamental group. Given a simplicial complex it is possible to “effectively compute” its fundamental group, in the sense that one may compute a presentation for that group. However, deciding the isomorphism of two groups from their presentations is uncomputable. Indeed, by showing that any finitely presented group can be the fundamental group of a compact 4-manifold [36], it has been shown that there exists no algorithm for deciding the topological equivalence (homeomorphism) of two compact, orientable, triangulable 4-manifolds [29].1 Fast algorithms would also be useful for computing cohomology groups. One motivation is that cohomology group computation is a vital subroutine called in the construction of Postnikov complexes, which calculates the higher homotopy groups.
We develop the basic concepts of triangulations, and the basic algorithmic structure of the resulting matrices representing the boundary homomorphisms.
Simplicial Complexes
A triangulation or tetrahedralization of a solid is a geometric realization of a simplicial complex. This object contains 0-simplices (vertices), 1-simplices (edges), 2-simplices (triangles), 3-simplices (tetrahedra), and so on. The set of these simplices is called a simplicial complex. The intersection of any two simplices must be another simplex of lower dimension. Clearly, we can represent a -simplex by its vertices . We wish to treat a simplicial complex as a purely combinatorial object. We do this by treating the simplices of a complex as combinatorial objects “independent of their coordinates.” We define the following:
Definition 50.2 An abstract simplicial complex consists of a set of vertices and a set of finite non-empty subsets of called simplices such that
- Any set consisting of exactly one vertex is a simplex.
- Any nonempty subset of a simplex is a simplex.
Simplices is plural; the singular is simplex.
is called a simplex of , and its dimension is 1 less than its cardinality. The vertices of have dimension 0. The dimension of is the dimension of the largest simplex in .
A geometric realization of is an embedding such that the image of the vertices of are linearly independent. A geometric realization of is an embedding of each simplex that preserves the adjacency relationships of : That is, if are simplices and , then . Hence, an embedding is an isomorphism onto its image.
Next we define the orientation of a simplex:
Definition 50.3 Let be a -simplex. Define two orderings of its vertices of be equivalent if they differ by an even permutation. This defines two equivalence classes of vertex orderings for . (Vertices have only one class, hence one orientation.) Each of these classes is called an orientation of . An oriented simplex is a simplex together with an orientation of .
1 See [32] for a nice review of this history.
Let be linearly (affinely) independent points. We denote by the oriented simplex consisting of the simplex with vertices and the equivalence class of the particular ordering .
Homology Type Is Effectively Computable
One topological invariant is the homology type, by which we mean all the homology groups of a triangulation. Henceforth, all homology and chain groups will be taken to have integer coefficients. In this chapter, let denote the ring of integers. A finite triangulation’s homology groups are all finitely generated Abelian groups. These groups have a structure theorem, which tells us that each can be expressed in normal form as the direct sum of a free Abelian group, and zero or more torsion groups (quotients of ),
where the each divides the next, that is, . Furthermore, classical algebraic topology tells us that these homology groups are effectively computable.2 Homology computation has been considered in a complexity-theoretic setting (for regular CW-complexes and for semi-algebraic sets) by Schwartz and Sharir [37], among others.
The homology computation for a simplicial complex is effected as follows:
First, we construct the “chain groups” , which are free Abelian groups generated by the (oriented) simplices of each dimension. A boundary homomorphism maps from each to . The homology group is defined by
The kernel of a map is the set of chains it sends to zero. The image of a map is the set of chains . See definition 50.6 and equation (50.7) below.
We calculate the matrix of the boundary homomorphism in “simplex basis coordinates.” This matrix is then “diagonalized” over the ring of integers; the diagonal matrix is its “(Smith) normal form.” The diagonal entries are
From this matrix, we may immediately calculate the Betti number and torsion coefficients that give the canonical form of the group (50.1).
2 For a finite triangulation or regular cell complex. See textbooks such as [33, 35] for a good modern treatment.
Complexity
Suppose the input triangulation has simplices in dimension , and for some dimension bound . Let . The matrix of each boundary homomorphism has size . The computational bottleneck in determining simplicial homology is the conversion of these matrices to (Smith) normal form.
We describe the classical algorithm for computing all the homology groups of a triangulation.
The rank of is the number of -simplices in . Hence, may be represented by an matrix . Now, each -simplex has a boundary which is a chain. For example, consider a triangular patch as an oriented 2-simplex . Now, in general, for a -simplex we have
where the “hat” means that the vertex is to be deleted to obtain a -simplex. So, for our triangular patch we have
Hence, “encoding” equation (50.4) into the matrix requires entries (which are ’s) into one column of (here, ). These are the only nonzero entries in that column.
Exercises
- Compute the boundary of a line segment .
- Compute the boundary of a tetrahedron .
- Compute of a line segment .
- Compute of a tetrahedron .
Applications
Mathematicians are interested in the efficient computation of the higher homotopy groups of simply-connected spaces (such as -spheres). That computation uses the homology group computation as a subroutine.
However, there are many other applications as well. In structural biology and macromolecular design, we could take as input two triangulations representing macromolecules and compute whether they have the same homology groups. While isomorphism of all the homology groups does not imply homeomorphism, it does mean that their “topologies” are “similar.” For example, the triangulations could represent solid finite-element meshes in macromolecular structural biology, or curved surfaces (e.g., Bézier systems). We know that surfaces with torsion homology are generally not embeddable in . For example, for the Klein bottle and the projective plane
, we have and , respectively. Hence the presence of torsion implies the physical unrealizability of a design. Thus, for example, we could compute whether a series of modifications to a design preserves its embeddability, connectivity, number of holes, and so on. There is a wealth of information in the homology groups of a topological space . In geometric design, the Euler number has been suggested as a topological invariant. The Euler number of is computable from the Betti numbers in equation (50.1). Let be the Betti number in dimension . Then . Hence, it is clear how the homology type provides strictly more information than the Euler characteristic. Because the homology groups carry so much information about the space, we could indeed imagine a protein design system where the homology type of the design was part of the design specification, or where designs were classified by homology type.
Foundations
The computability of the homology groups of a simplicial complex is well known basic mathematics; see textbooks on elementary algebraic topology (e.g., [33, 35]). Worst-case deterministic bounds have been given in several studies [34, 23, 8, 20, 21]; see section 50.5.3. For work on computing cohomology groups, see references [17, 19, 25]. For other work on computational algebraic topology, see references [5, 1, 37, 31, 14, 9, 2, 24, 6, 7], and also [42]. Other studies [40, 39] discuss related problems of interest.
Computing Homology Groups
Simplicial Homology
See section 50.3 for a review of simplicial complexes. We first define the chain groups for a simplicial complex .
Definition 50.4 A -chain on a simplicial complex is a function from the oriented -simplices of to the integers that vanishes on all but finitely many -simplices, such that
if and are opposite orientations of the same simplex.
Definition 50.5 We add -chains by adding their values. This yields a group , called the chain group of dimension . For or , is the trivial group.
For every oriented simplex , we define the elementary chain as follows: , (if is the opposite orientation of ), and vanishes on all other oriented simplices. Now, it is convenient to write to denote not only an oriented simplex , but also to denote the elementary -chain . Hence, we write .
We note the following fact: is the direct sum of subgroups isomorphic to , one for each -simplex of . Hence, is a free Abelian group generated by the oriented -simplices of
. To “compute” , we simply count the number of -simplices, and “construct” as . This means we view the oriented -simplices as a basis for , and we can write any chain in the group as a finite linear combination . One example of such a chain is the RHS of equation (50.4).
Next, we define the boundary homomorphism using equation (50.3). An example of computing is shown in equation (50.4). This constructs a free chain complex (a differential graded group of degree , in which each is free Abelian):
It is straightforward to show that for all
Finally, we can define the homology groups, formalizing (50.2):
Definition 50.6 The kernel of is called the group of -cycles and is denoted . The image of is called the group of -boundaries, and is denoted . By equation (50.6), each boundary of a -chain is a -cycle, so . We define
to be the -th homology group of .
Computing the Homology Groups
Now, let and be free Abelian groups with bases and , respectively. For a homomorphism , then
for unique integers . The matrix is called the matrix of relative to the chosen bases for and .
We recall the following basic theorem from algebra:
Theorem 50.7 Let be an matrix over a principal ideal domain . Then can be “diagonalized” in the sense that we can obtain a diagonal matrix
where and . If the diagonal elements of (50.9) are , then . Furthermore, if is a Euclidean domain, then (50.9) may be obtained by elementary row and column operations on .
This “diagonal” form is called the “normal form” of the matrix; the algorithm to compute it is called the “reduction algorithm.” , of course, is a Euclidean domain. We further recall that the elementary row operations are as follows:
- Add an integer multiple of row to row ().
- Interchange rows and .
- Multiply row by a unit (in our case, ).
Each of these corresponds to a change of basis in . There are three similar “column” operations that correspond to a change of basis in . Theorem 50.7 therefore states that we can always apply a sequence of these six operations on to reduce it to the desired “normal form.” By viewing the presentation matrices for Abelian groups as -modules, we obtain the structure theorem for finitely generated Abelian groups (equation 50.1). The reduction algorithm is central to computing the normal form of the boundary homomorphism, and hence, to computing the homology groups. We review the reduction algorithm in section 50.5.3. We proceed now to describe the following classical construction from algebraic topology (see, e.g., [33]).
- Let , and .
- Let be all elements of such that some nonzero multiple of belongs to . is a subgroup of , called the group of weak -boundaries. We have
- Using the reduction algorithm, we diagonalize the matrix for , that is, we choose bases for and for , relative to which the matrix of has the normal form
where all the are positive, and . It is not hard to show that
- is a basis for .
- is a basis for .
- is a basis for .
A straightforward computation shows that
Now, the group is free, and is a torsion group. Hence, we can calculate by computing these two groups.
The Algorithm for Homology Group Computation
We proceed as follows. First, we choose bases for the chain groups by arbitrarily orienting the simplices of . These orientations remain fixed for the computation. Then we construct the matrix of the boundary homomorphism relative to these bases. Its entries will all be 0, 1, or . We next reduce this matrix to normal form using the reduction algorithm, obtaining a matrix like (50.10). Now,
- The rank of is the number of zero columns in matrix (50.10).
- The rank of is the number of nonzero rows in (50.10).
- There is an isomorphism
Hence, from the normal form of the boundary homomorphism (50.10) we can “read off” the torsion coefficients of in dimension ; they are simply the entries of the matrix that are greater than 1. We can also “read off” the rank of and (see above). Finally, the normal form for gives us the rank of . The Betti number of in dimension is simply .
The Reduction Algorithm We now prove theorem 50.7 by giving the classical reduction algorithm. In the process, we keep track of the complexity. We observe first that all elementary row (resp. column) operations take time (resp. ). The proof uses the division algorithm (i.e., the fact that is a Euclidean domain).
Proof of Theorem (50.7) Let be an matrix over .
Step 1 (preprocessing) We find the smallest nonzero element, of . (Here smallest means smallest “size” in the ring—i.e., smallest absolute value). Permute the rows and columns to move the smallest element to the upper lefthand corner, . Multiply the first row by to make positive.
Step 2 Suppose doesn’t divide some entry in the first column, say, :
Use the division algorithm to obtain
where and . Now we add times the first row to the row. This replaces by , while increasing the “size” of the numbers in row by a factor of . Since , is no longer the minimal element of . The new minimal element is somewhere in row (it may not be ). Repermute the matrix so that the new minimal element is in the upper left corner.
Step 3 Repeat step 2 until divides every in the first column.
Step 4 Similarly, we may use column operations to reduce to the case where divides every in the first row.
We observe that step 1 takes time , step 2 takes time . We observe that steps 3 and 4 terminate because at each step, is decremented by at least 1. Hence, we reach step 5 after time.
Step 5 Subtract off multiples of the first row and column to make all the elements in the first column and in the first row zero, for . Now the matrix looks like this:
Now, we wish to ensure that divides every element of the submatrix . We number ’s rows and columns starting at 2.
Step 6 Suppose some entry of is not divisible by . We add row to row 1 to obtain:
Next, we apply the division algorithm to obtain
with , . We subtract times column 1 from column to obtain:
Step 7 Now, at this point, is no longer the minimal element of , since . We go back to step 1, moving to . Since the corner element is decreased by at least 1 each time, the (entire) process terminates after at most iterations. Finally, will divide every entry in , and the first row and column will be zero, except for . Hence, the matrix has the form (50.14), and divides each element of .
Step 8 (Recursive Step) We note that if is an integer that divides each entry of , and that if is obtained from by any row or column operation, then still divides each entry of . Hence, we can recursively invoke the algorithm on submatrix .
All of the steps in the algorithm given in section 50.5.3 are essentially linear-time or quadratic-time operations except the reduction algorithm. The time required by the reduction algorithm (section 50.5.3), in fact, dominates the computation of homology type, which can clearly be done in time . The worst-case analysis of the algorithm indicates that it could run in doubly exponential time, due to the potential growth of the integer coefficients. While worst-case bounds for the reduction algorithm are poor, the algorithm is straightforward to implement and in practice it often runs very efficiently for a geometric object (such as a protein) that is embedded in three-dimensional Euclidean space.
In 1861, Smith [34] gave what is now considered the classical “reduction” algorithm showing that an integer matrix can be diagonalized using elementary row and column operations (section 50.5.3). It was noted in the 1970s that neither the classical algorithm nor several well-known subsequent algorithms for reduction were known to be polynomial (see [23] for a review of these observations). Kannan and Bachem then gave a polynomial-time algorithm for reduction to Smith normal form. This bound was subsequently improved: Chou and Collins [8] provided an algorithm, where for an matrix with maximum coefficient , we define . Two papers [20, 21] give fast worst-case bounds for computing Smith normal form, and hence the canonical structure of Abelian groups. The worst-case bounds given by Iliopoulos are roughly . The algorithms of Chou and Collins and Iliopoulos [20, 21, 8] are different from the classical algorithm. Either of these results could be used to compute the homology type in (deterministic) times or .
Exercise Compare and contrast the concepts of mathematical versus biological homology. How well does mathematical homology (e.g., integral homology groups) capture the notion of protein structural homology? Explain your answer, and give concrete examples from the PDB.
Alpha Shapes ( -Shapes) and Applications to Protein Structure
Herbert Edelsbrunner and colleagues [12] developed an efficient and useful version of homology group computation and applied it to structural biology. In this section, we will use the term face to describe both 2-simplices and 1-simplices. First, they restricted their attention to three-dimensional simplicial complexes, and to the part of the homology groups that do not have torsion (the so-called Betti numbers, discussed in section 50.4). They developed an efficient algorithm to compute Betti numbers for a triangulation. Then they imagined using an eraser to eliminate faces in the triangulation. The eraser would have a particular width, and so there would be some vertices that would be too close together for the eraser to fit between them, or to erase the face between them. Given an eraser with a particular width, they would thus remove some faces and then recompute the Betti numbers. Using a sophisticated computational geometry algorithm, they could then amortize the computation and sweep the eraser widths to vary from large to small (0), thereby calculating a measure of the topology as parameterized by eraser size () and face removal. Hence, the Betti numbers are parameterized by a continuous scalar value , and where the faces of the triangulation generating the homology groups are removed according to this width (size) parameter. The topology of the triangulation, and the Betti numbers, only change at a finite set of -values, which are called the critical values. The essence of the algorithm is to compute these critical values, and the topological changes (in Betti numbers) that passing through them triggers. This provides a nuanced representation of the topological structure of the triangulation. The approach, called -shapes, has been a useful tool in analyzing protein structure.
The size and shape of macromolecules such as proteins and nucleic acids play an important role in their functions. In molecular modeling, these properties are usually quantified based on various discretization or tessellation procedures involving analytical or numerical computations. Liang et al. [26] presents an analytically exact method for computing the metric properties of macromolecules based on the alpha () shape theory. This method uses the duality between the alpha complex and the weighted Voronoi decomposition of a molecule. The authors applied the method to compute areas and volumes of a number of protein systems.
Although the structures of most proteins are well-packed, they contain numerous cavities that play key roles in accommodating small molecules, or enabling conformational changes. From high-resolution structures, it is possible to identify these cavities. Liang et al. [27] developed a precise algorithm based on alpha shapes for measuring space-filling-based molecular models (such as van der Waals, solvent accessible, and molecular surface descriptions). They applied this method to compute the surface area and volume of cavities in several proteins. In addition, all of the atoms/residues lining the cavities were identified. They used this method to study the structure and the stability of several proteins, as well as to locate cavities that could contain structural water molecules in the proton transport pathway in the membrane protein bacteriorhodopsin.
Identification and size characterization of surface pockets and occluded cavities are often initial steps in protein structure-based ligand design. An algorithm called CAST, for automatically locating and measuring protein pockets and cavities, was developed based on alpha shapes and discrete flow theory [28]. CAST identifies and measures the atoms lining pockets, pocket openings, and buried cavities; the volume and area of pockets and cavities; and the area and circumference of mouth openings. CAST analysis of over 100 proteins was carried out; these proteins included a set of 51 monomeric enzyme-ligand structures, several elastase-inhibitor complexes, the FK506 binding protein, 30 HIV-1 protease-inhibitor complexes, and a number of small and large protein inhibitors.
Medium-sized globular proteins typically were found to have 10–20 pockets/cavities. Most often, binding sites were pockets with 1–2 mouth openings; much less frequently, they were cavities. Ligand-binding pockets varied widely in size, most within the range – . Statistical analysis revealed that the number of pockets and cavities was correlated with protein size, but there was no correlation between the size of the protein and the size of binding sites. Most frequently, the largest pocket/cavity was the active site (but there are a number of interesting exceptions [28]).
Ligand volume and binding site volume were somewhat correlated when binding site volume is , but the ligand seldom occupies the entire site [28]. Auxiliary pockets near the active site have been suggested as additional (“allosteric”) binding surfaces for designed ligands.3 Analysis of elastase-inhibitor complexes suggests that CAST can identify ancillary pockets suitable for recruitment in ligand design strategies. Analysis of the FK506 binding protein, and of compounds developed in SAR by NMR,4 indicated that CAST pocket computation may provide a priori identification of target proteins for linked-fragment design. CAST analysis of 30 HIV-1 protease-inhibitor complexes showed that the flexible active site pocket can vary over a range of roughly 850 to 1,500 , and that there are two pockets near or adjoining the active site that may be recruited for ligand design.
Conclusions and Future Work
We have described an algorithm for computing all the homology groups of a triangulation. The algorithm can be generalized to compute cohomology groups. Cohomology group computation is one of the essential steps in computing the higher homotopy groups of a simply connected triangulation. A great deal of work remains to be done. As is well known, the cohomology groups of a space are completely determined by its homology. However, they come equipped with a natural “cohomology operation” that gives these groups a ring structure. Spaces with
3 For example, see [30] and [18].
4 See chapter 15 and [38].
identical homology and cohomology groups can have different ring structure, hence, the ring structure distinguishes “more finely” between spaces. Deciding ring isomorphism is a central question here. Fast algorithmic solutions to these problems will prove a challenge to researchers in computational algebraic topology.
This chapter provided an introduction to some aspects of computational topology and protein structure. Other work abounds. For example, by using topological techniques from knot theory and line weavings, Michael Erdmann has analyzed protein shape similarity in terms of structure-preserving transformations [13]. His paper defines similarity based on atomic motions that preserve local backbone topology without incurring significant distance errors. Such geometric algorithms for computational topology represent a parallel branch of development to those exploiting integral homology groups. Moreover, Erdmann’s approach anticipates, as it were, protein design algorithms that consider bounded backbone flexibility (either continuous voxels [15] or discrete “backrubs” [16]) while still maintaining guarantees to compute the GMEC and enumerate a gap-free list of conformations in order of energy (see chapter 12 and [15, 16]). Such algorithms can be viewed as searching a conformation/mutation space subject to a topological constraint.
References
- [1] D. Anick. Computing rational homotopy groups is # -hard, in Computers in Geometry and Topology, Lecture Notes in Pure and Applied Mathematics. M. Tangora (ed.). New York: Marcel Dekker, 1989.
- [2] D. Arnon, G. Collins, and S. McCallum. Cylindrical Algebraic Decomposition I: The Basic Algorithm, CDS TR-427, Department Computer Science Purdue University, 1982.
- [3] M. Ben-Or, D. Kozen, and J. Reif. The complexity of elementary algebra and geometry, Journal of Computer and System Sciences 32 (1986): 251–264.
- [4] W. Boone, W. Haken, and V. Poenaru. On recursively unsolvable problems in topology and their classification, in Contributions to Mathematical Logic, H. Schmidt et al. (eds.). North Holland, 1968, pp. 37–74.
- [5] E. H. Brown. Finite computability of Postnikov complexes., Annals of Mathematics, 65 (1957): 1–20.
- [6] J. F. Canny. A New algebraic method for robot motion planning and real geometry, FOCS (1987). Foundations of Computer Science (FOCS) 1987
- [7] J. F. Canny, and B. R. Donald. Simplified Voronoi diagrams Discrete and Computational Geometry 3;3 (1990): 219–236.
- [8] T. J. Chou, and G. E. Collins. Algorithms for the solution of linear Diophantine equations, SIAM Journal on Computing 11 (1982): 687–708.
- [9] G. E. Collins. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Lecture Notes in Computer Science, No. 33. New York: Springer-Verlag, 1975, pp. 135–183.
- [10] H. Crapo. Applications of geometric homology in Geometry and Robotics. Lecture Notes in Computer Science 391, I.D. Boissonnat and I.P. Laumond (eds.). New York: Springer-Verlag 1989.
- [11] P. D. Domich. Residual Methods for Computing Hermite and Smith Normal Forms PhD thesis, Cornell University, 1985.
- [12] H. Edelsbrunner and E. P. Mucke. Three-dimensional alpha shapes., ACM Transactions on Graphics 13 (1994): 43–72.
- [13] M. A. Erdmann. Protein similarity from knot theory: Geometric convolution and line weavings. Journal of Computational Biology 12; 6 (2005): 609–637.
[14] H. Hironaka. Triangulations of algebraic sets. Proceedings of the Symposia in Pure Mathematics American Mathematical Society 29 (1975): 165–185.
[15] I. Georgiev and B. R. Donald. Dead-end elimination with backbone flexibility. Bioinformatics 23; 13 (2007). Special issue on papers from the International Conference on Intelligent Systems for Molecular Biology (ISMB 2007), Vienna, Austria: July 21–25, 2007.
[16] I. Georgiev, D. Keedy, J. Richardson, D. Richardson, and B. R. Donald. Algorithm for backrub motions in protein design. Bioinformatics 4;13 (2008):i196–i204. Special issue on papers from International Conference on Intelligent Systems for Molecular Biology (ISMB 2008) Toronto, July 2008.
[17] N. M. Glazunov. Algorithms for calculations of cohomology groups of finite groups, in Computations in Algebra and Combinatorial Analysis, Kiev: Akadem. Nauka Ukrainsk. SSR Instituta Kibernetika, (Math. Reviews 82f 20080), 1978.
[18] M. J. Gorczynski, J. Grembecka, Y. Zhou, Y. Kong, L. Roudaia, M.G. Douvas, M. Newman, et al. Allosteric inhibition of the protein-protein interaction between the leukemia-associated proteins Runx1 and CBFb. Chemistry & Biology 14; 10 (2007):1186–1197.
[19] D. F. Holt. The mechanical computation of first and second cohomology groups, Journal of Symbolic Computation 1, (1985):351–361.
[20] C. S. Iliopoulos. Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and Hermite and Smith normal form of an integer matrix, SIAM Journal on Computing, 18;4, (1989):658–669.
[21] C. S. Iliopoulos. Worst-case complexity bounds on algorithms for computing the canonical structure of infinite Abelian groups and solving systems of linear diophantine equations, SIAM Journal on Computing 18;4, (1989):670–678.
[22] N. Jacobson. Basic Algebra, I. New York Freeman, 1985.
[23] R. Kannan and A. Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, 8 (1979): 499–507.
[24] D. Kozen and C. K. Yap. Algebraic cell decomposition in NC. Proceedings of the 26th Annual Symposium on Foundations of Computer Science 515–521. (1985 Oct.).
[25] L. Lambe. Algorithms for Computing the Cohomology of Nilpotetnt Groups, in Computers in Geometry and Topology. Lecture Notes in Pure and Applied Mathematics. M. Tangora (ed.). New York: Marcel Dekker, 1989.
[26] J. Liang, H. Edelsbrunner, P. Fu, P. V. Sudhakar, and S. Subramaniam. Analytical shape computation of macromolecules: I. Molecular area and volume through alpha shape, Proteins 33;1: (1998 oct. 1) 1–17.
[27] J. Liang, H. Edelsbrunner, P. Fu, P. V. Sudhakar, and S. Subramaniam. Analytical shape computation of macromolecules: II. Inaccessible cavities in proteins, Proteins 33;1:18–29. (1998 Oct 1).
[28] J. Liang, H. Edelsbrunner, and C. Woodward. Anatomy of protein pockets and cavities: Measurement of binding site geometry and implications for ligand design. Protein Science 7;9: (1998 sep.) 1884–1897.
[29] A. A. Markov. Nerazreshimost’ Problemy Gomeomorfiy, Proceedings of the International Congress of Mathematicians. J.A. Todd (ed.). Cambridge University Press, 1958, pp. 300–306.
[30] C. Mattos, B. Rasmussen, X. Ding, G.A. Petsko, and D. Ringe. Analogous inhibitors of elastase do not always bind analogously. Nature Structural Biology 1 (1994):55–58.
[31] S. McCallum. Constructive Triangulation of Real Curves and Surfaces. Sidney: University of Sidney, 1979.
[32] W. S. Massey. Algebraic Topology: An Introduction, New York: Springer-Verlag, 1967.
[33] Munkres. Elements of Algebraic Topology, Menlo-Park, CA: Addison-Wesley; 1984.
[34] H.J.S. Smith. On systems of indeterminate equations and congruences. Philosophical Transactions 151 (1861): 293–326.
[35] E. H. Spanier. Algebraic Topology. New York: Springer-Verlag, 1966.
[36] H. Seifert, and W. Threlfall. Lehrbuch der Topologie. New York: Chelsea, 1947, chap. 7.
[37] J. Schwartz, and M. Sharir. On the ‘piano movers’ problem, II. General techniques for computing topological properties of real algebraic manifolds, in Planning, Geometry and Complexity of Robot Motion. J. Schwartz, J. Hopcroft, and M. Sharir, (eds.). Norwood, NJ: Ablex. 1987, chap. 5, pp. 154–186.
[38] S. B. Shuker, P. J. Hajduk, R. P. Meadows, and S. W. Fesik. Discovering high-affinity ligands for proteins: SAR by NMR. Science 274;5292(1996 Nov 29):1531–1534.
[39] J. Snoeyink. A trivial knot whose spanning disks have exponential size, Proceedings of ACM Symposium on Computational Geometry, Berkeley, CA (1990).
[40] G. Vegter and C. K. Yap. Computational complexity of combinatorial surfaces, Proceedings of ACM Symposium on Computational Geometry, Berkeley, CA (1990).
[41] J. Warren. The Effect of Base Points on Rational Bezier Surfaces, Department of Computer Science, Rice University (1990).
[42] H. Whitney. Elementary structure of real algebraic varieties, Annals of Mathematics. 66;3 (1957): 545–556.
[43] C. Yap. Algorithmic Motion Planning Advances in Robotics: Vol. 1 J. Schwartz and C. Yap (eds.) Lawrence Erlbaum Associates, 1986.