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 PP , 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 PP 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 ℝ3\mathbb{R}^3 . 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 pp -simplex is a convex hull of p+1p + 1 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 (ℝ3\mathbb{R}^3)?” 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 pp -simplex by its vertices [v0,…,vp][v_0, \dots, v_p] . 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 KK consists of a set {v}\{v\} of vertices and a set {s}\{s\} of finite non-empty subsets of {v}\{v\} called simplices such that

  1. Any set consisting of exactly one vertex is a simplex.
  2. Any nonempty subset of a simplex is a simplex.

Simplices is plural; the singular is simplex.

σ∈K\sigma \in K is called a simplex of KK , and its dimension is 1 less than its cardinality. The vertices of KK have dimension 0. The dimension of KK is the dimension of the largest simplex in KK .

A geometric realization of σ\sigma is an embedding ϕ:σ→ℝn\phi : \sigma \rightarrow \mathbb{R}^n such that the image of the vertices of σ\sigma are linearly independent. A geometric realization of KK is an embedding of each simplex that preserves the adjacency relationships of KK : That is, if σ,τ,ρ\sigma, \tau, \rho are simplices and σ∩τ=ρ\sigma \cap \tau = \rho , then ϕ(σ)∩ϕ(τ)=ϕ(ρ)\phi(\sigma) \cap \phi(\tau) = \phi(\rho) . Hence, an embedding is an isomorphism onto its image.

Next we define the orientation of a simplex:

Definition 50.3 Let σ\sigma be a pp -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 p>0p > 0 . (Vertices have only one class, hence one orientation.) Each of these classes is called an orientation of σ\sigma . An oriented simplex is a simplex σ\sigma together with an orientation ±1\pm 1 of σ\sigma .

1 See [32] for a nice review of this history.

Let v0,…,vpv_0, \dots, v_p be linearly (affinely) independent points. We denote by [v0,…,vp][v_0, \dots, v_p] the oriented simplex consisting of the simplex with vertices v0,…,vpv_0, \dots, v_p and the equivalence class of the particular ordering v0,…,vpv_0, \dots, v_p .

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 ZZ 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 ZZ),

Zb⊕Z/d1⊕…⊕Z/dl,(50.1)Z^b \oplus Z/d_1 \oplus \dots \oplus Z/d_l, \quad (50.1) where the each did_i divides the next, that is, d1|d2|…|dld_1|d_2| \dots |d_l . 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 KK is effected as follows:

First, we construct the “chain groups” {Cp}\{C_p\} , which are free Abelian groups generated by the (oriented) simplices of each dimension. A boundary homomorphism ∂p\partial_p maps from each CpC_p to Cp−1C_{p-1} . The pthp^{th} homology group is defined by

Hp(K)=(ker⁡∂p)/(im ∂p+1).(50.2)H_p(K) = (\ker \partial_p)/(\text{im } \partial_{p+1}). \quad (50.2)

The kernel ker⁡∂p\ker \partial_p of a map ∂p\partial_p is the set of chains it sends to zero. The image im ∂p+1\text{im } \partial_{p+1} of a map ∂p+1:Cp+1→Cp\partial_{p+1} : C_{p+1} \rightarrow C_p is the set of chains {∂p+1(x)∣x∈Cp+1}\{\partial_{p+1}(x) \mid x \in C_{p+1}\} . 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

1,…,1,d1,d2,…,dl⏞r 1’s(r≥0).\overbrace{1, \dots, 1, d_1, d_2, \dots, d_l}^{r \text{ 1's}} \quad (r \geq 0).

From this matrix, we may immediately calculate the Betti number bb and torsion coefficients d1,…,dld_1, \dots, d_l 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 KK has npn_p simplices in dimension pp , and dim⁡K=D\dim K = D for some dimension bound DD . Let n=max⁡pnpn = \max_p n_p . The matrix of each boundary homomorphism has size O(n2)O(n^2) . 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 npn_p of CpC_p is the number of pp -simplices in KK . Hence, ∂p\partial_p may be represented by an np−1×npn_{p-1} \times n_p matrix ApA_p . Now, each pp -simplex has a boundary which is a (p−1)(p-1) chain. For example, consider a triangular patch as an oriented 2-simplex [v0,v1,v2][v_0, v_1, v_2] . Now, in general, for a pp -simplex σ\sigma we have

∂pσ=∂p[v0,…,vp]=∑i=0p(−1)i[v0,…,v̂i,…,vp],(50.3)\partial_p \sigma = \partial_p [v_0, \dots, v_p] = \sum_{i=0}^p (-1)^i [v_0, \dots, \hat{v}_i, \dots, v_p], \quad (50.3) where the “hat” v̂i\hat{v}_i means that the vertex viv_i is to be deleted to obtain a (p−1)(p-1) -simplex. So, for our triangular patch we have

∂2[v0,v1,v2]=[v1,v2]−[v0,v2]+[v0,v1].(50.4)\partial_2 [v_0, v_1, v_2] = [v_1, v_2] - [v_0, v_2] + [v_0, v_1]. \quad (50.4)

Hence, “encoding” equation (50.4) into the matrix ApA_p requires p+1p+1 entries (which are ±1\pm 1 ’s) into one column of ApA_p (here, p=2p = 2). These are the only nonzero entries in that column.

Exercises

  1. Compute the boundary ∂1([v0,v1])\partial_1([v_0, v_1]) of a line segment [v0,v1][v_0, v_1] .
  2. Compute the boundary ∂3([v0,v1,v2,v3])\partial_3([v_0, v_1, v_2, v_3]) of a tetrahedron [v0,v1,v2,v3][v_0, v_1, v_2, v_3] .
  3. Compute ∂0(∂1([v0,v1]))\partial_0(\partial_1([v_0, v_1])) of a line segment [v0,v1][v_0, v_1] .
  4. Compute ∂2(∂3([v0,v1,v2,v3]))\partial_2(\partial_3([v_0, v_1, v_2, v_3])) of a tetrahedron [v0,v1,v2,v3][v_0, v_1, v_2, v_3] .

Applications

Mathematicians are interested in the efficient computation of the higher homotopy groups of simply-connected spaces (such as nn -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 ℝ3\mathbb{R}^3 . For example, for the Klein bottle 𝒦\mathcal{K} and the projective plane

P2P^2 , we have H1(K)=Z⊕Z/2H_1(K) = Z \oplus Z/2 and H1(P2)=Z/2H_1(P^2) = Z/2 , 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 KK . In geometric design, the Euler number χ(K)\chi(K) has been suggested as a topological invariant. The Euler number of KK is computable from the Betti numbers in equation (50.1). Let βp\beta_p be the Betti number in dimension pp . Then χ(K)=∑p(−1)pβp\chi(K) = \sum_p (-1)^p \beta_p . 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 KK .

Definition 50.4 A pp -chain on a simplicial complex KK is a function cc from the oriented pp -simplices of KK to the integers that vanishes on all but finitely many pp -simplices, such that

c(σ)=−c(σ′)c(\sigma) = -c(\sigma')

if σ\sigma and σ′\sigma' are opposite orientations of the same simplex.

Definition 50.5 We add pp -chains by adding their values. This yields a group Cp(K)C_p(K) , called the chain group of dimension pp . For p<0p < 0 or p>dim⁡Kp > \dim K , Cp(K)C_p(K) is the trivial group.

For every oriented simplex σ\sigma , we define the elementary chain cσc_\sigma as follows: cσ(σ)=1c_\sigma(\sigma) = 1 , cσ(σ′)=−1c_\sigma(\sigma') = -1 (if σ′\sigma' is the opposite orientation of σ\sigma), and cσc_\sigma vanishes on all other oriented simplices. Now, it is convenient to write σ\sigma to denote not only an oriented simplex σ\sigma , but also to denote the elementary pp -chain cσc_\sigma . Hence, we write σ′=−σ\sigma' = -\sigma .

We note the following fact: Cp(K)C_p(K) is the direct sum of subgroups isomorphic to ZZ , one for each pp -simplex of KK . Hence, Cp(K)C_p(K) is a free Abelian group generated by the oriented pp -simplices of

KK . To “compute” Cp(K)C_p(K) , we simply count the number npn_p of pp -simplices, and “construct” Cp(K)C_p(K) as ZnpZ^{n_p} . This means we view the oriented pp -simplices as a basis for Cp(K)C_p(K) , and we can write any chain in the group as a finite linear combination ∑kiσi\sum k_i \sigma_i . One example of such a chain is the RHS of equation (50.4).

Next, we define the boundary homomorphism ∂p:Cp(K)→Cp−1(K)\partial_p : C_p(K) \rightarrow C_{p-1}(K) using equation (50.3). An example of computing ∂2\partial_2 is shown in equation (50.4). This constructs a free chain complex (a differential graded group of degree −1-1 , in which each CpC_p is free Abelian):

Cp(K)→∂pCp−1(K)→∂p−1⋯→∂2C1(K)→∂1C0(K).(50.5)C_p(K) \xrightarrow{\partial_p} C_{p-1}(K) \xrightarrow{\partial_{p-1}} \cdots \xrightarrow{\partial_2} C_1(K) \xrightarrow{\partial_1} C_0(K). \quad (50.5)

It is straightforward to show that for all pp

∂p−1∘∂p=0.(50.6)\partial_{p-1} \circ \partial_p = 0. \quad (50.6)

Finally, we can define the homology groups, formalizing (50.2):

Definition 50.6 The kernel of ∂p:Cp(K)→Cp−1(K)\partial_p : C_p(K) \rightarrow C_{p-1}(K) is called the group of pp -cycles and is denoted Zp(K)Z_p(K) . The image of ∂p+1:Cp+1(K)→Cp(K)\partial_{p+1} : C_{p+1}(K) \rightarrow C_p(K) is called the group of pp -boundaries, and is denoted Bp(K)B_p(K) . By equation (50.6), each boundary of a (p+1)(p+1) -chain is a pp -cycle, so Bp(K)⊂Zp(K)B_p(K) \subset Z_p(K) . We define

Hp(K)=Zp(K)/Bp(K)(50.7)H_p(K) = Z_p(K)/B_p(K) \quad (50.7) to be the pp -th homology group of KK .

Computing the Homology Groups

Now, let GG and HH be free Abelian groups with bases σ1,…,σn\sigma_1, \dots, \sigma_n and ρ1,…,ρm\rho_1, \dots, \rho_m , respectively. For a homomorphism f:G→Hf : G \rightarrow H , then

f(σj)=∑i=1jaijρi,(50.8)f(\sigma_j) = \sum_{i=1}^j a_{ij} \rho_i, \quad (50.8) for unique integers aija_{ij} . The matrix A=(aij)A = (a_{ij}) is called the matrix of ff relative to the chosen bases for GG and HH .

We recall the following basic theorem from algebra:

Theorem 50.7 Let A=(aij)A = (a_{ij}) be an n×mn \times m matrix over a principal ideal domain RR . Then AA can be “diagonalized” in the sense that we can obtain a diagonal matrix

PAQ,(50.9)PAQ, \quad (50.9) where P∈GLm(R)P \in GL_m(R) and Q∈GLn(R)Q \in GL_n(R) . If the diagonal elements of (50.9) are d1,d2,…,dld_1, d_2, \dots, d_l , then d1|d2|⋯|dld_1|d_2|\cdots|d_l . Furthermore, if RR is a Euclidean domain, then (50.9) may be obtained by elementary row and column operations on AA .

This “diagonal” form is called the “normal form” of the matrix; the algorithm to compute it is called the “reduction algorithm.” ZZ , of course, is a Euclidean domain. We further recall that the elementary row operations are as follows:

  1. Add an integer multiple of row ii to row jj (i≠ji \neq j).
  2. Interchange rows ii and jj .
  3. Multiply row ii by a unit (in our case, ±1\pm 1).

Each of these corresponds to a change of basis in HH . There are three similar “column” operations that correspond to a change of basis in GG . Theorem 50.7 therefore states that we can always apply a sequence of these six operations on AA to reduce it to the desired “normal form.” By viewing the presentation matrices for Abelian groups as ZZ -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]).

  1. Let Zp=ker⁡∂pZ_p = \ker \partial_p , and Bp=im ∂p+1B_p = \text{im } \partial_{p+1} .
  2. Let WpW_p be all elements σp\sigma_p of CpC_p such that some nonzero multiple of σp\sigma_p belongs to BpB_p . WpW_p is a subgroup of CpC_p , called the group of weak pp -boundaries. We have

Bp⊂Wp⊂Zp⊂Cp.B_p \subset W_p \subset Z_p \subset C_p.

    1. Using the reduction algorithm, we diagonalize the matrix for ∂p\partial_p , that is, we choose bases σ1,…,σn\sigma_1, \dots, \sigma_n for CpC_p and ρ1,…,ρm\rho_1, \dots, \rho_m for Cp−1C_{p-1} , relative to which the matrix of ∂p\partial_p has the normal form

σ1…σlσl+1…σnρ1⋮d10⋮0ρl0dlρl+100⋮ρm(50.10)\begin{array}{ccccccc} & \sigma_1 & \dots & \sigma_l & \sigma_{l+1} & \dots & \sigma_n \\ \rho_1 & \vdots & & & & & \\ & & d_1 & & 0 & & \\ & & & \vdots & & & \\ & & & & & 0 & \\ \rho_l & & 0 & d_l & & & \\ \rho_{l+1} & & & & \hline & & & 0 & & 0 & \\ & & & & \vdots & & \\ & & & & & & \\ \rho_m & & & & & & \\ & & & & & & \end{array} \qquad(50.10) where all the did_i are positive, and d1|d2|…|dld_1 | d_2 | \dots | d_l . It is not hard to show that

    1. σl+1,…,σn\sigma_{l+1}, \dots, \sigma_n is a basis for ZpZ_p .
    1. ρ1,…,ρl\rho_1, \dots, \rho_l is a basis for Wp−1W_{p-1} .
    1. d1ρ1,…,dlρld_1 \rho_1, \dots, d_l \rho_l is a basis for Bp−1B_{p-1} .

A straightforward computation shows that

Hp(K)≅(Zp/Wp)⊕(Wp/Bp).(50.11)H_p(K) \cong (Z_p/W_p) \oplus (W_p/B_p). \quad (50.11)

Now, the group Zp/WpZ_p/W_p is free, and Wp/BpW_p/B_p is a torsion group. Hence, we can calculate Hp(K)H_p(K) 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 KK . 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 −1-1 . We next reduce this matrix to normal form using the reduction algorithm, obtaining a matrix like (50.10). Now,

  1. The rank of ZpZ_p is the number of zero columns in matrix (50.10).
  2. The rank of Wp−1W_{p-1} is the number of nonzero rows in (50.10).
  3. There is an isomorphism

Wp−1/Bp−1≅Z/d1⊕⋯⊕Z/dl.W_{p-1}/B_{p-1} \cong Z/d_1 \oplus \cdots \oplus Z/d_l.

Hence, from the normal form of the boundary homomorphism (50.10) we can “read off” the torsion coefficients of KK in dimension p−1p - 1 ; they are simply the entries of the matrix that are greater than 1. We can also “read off” the rank of ZpZ_p and Wp−1W_{p-1} (see above). Finally, the normal form for ∂p+1\partial_{p+1} gives us the rank of WpW_p . The Betti number of KK in dimension pp is simply b=rank(Zp/Wp)=rank(Zp)−rank(Wp)b = \text{rank}(Z_p/W_p) = \text{rank}(Z_p) - \text{rank}(W_p) .

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 O(m)O(m) (resp. O(n)O(n)). The proof uses the division algorithm (i.e., the fact that ZZ is a Euclidean domain).

Proof of Theorem (50.7) Let A=(aij)A = (a_{ij}) be an m×nm \times n matrix over ZZ .

Step 1 (preprocessing) We find the smallest nonzero element, ℓ1\ell_1 of AA . (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, a11a_{11} . Multiply the first row by ±1\pm 1 to make a11a_{11} positive.

Step 2 Suppose a11a_{11} doesn’t divide some entry in the first column, say, a11∤ai1a_{11} \nmid a_{i1} :

(a11⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅ai1⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅)(50.12)\begin{pmatrix} a_{11} & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ a_{i1} & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \end{pmatrix} \quad (50.12)

Use the division algorithm to obtain

ai1=qa11+r,(50.13)a_{i1} = qa_{11} + r, \qquad(50.13) where q,r∈ℤq, r \in \mathbb{Z} and 0<r<a110 < r < a_{11} . Now we add (−q)(-q) times the first row to the ithi^{th} row. This replaces ai1a_{i1} by rr , while increasing the “size” of the numbers in row ii by a factor of qq . Since r<a11r < a_{11} , a11a_{11} is no longer the minimal element of AA . The new minimal element is somewhere in row ii (it may not be rr). Repermute the matrix so that the new minimal element is in the upper left corner.

Step 3 Repeat step 2 until a11a_{11} divides every ai1a_{i1} in the first column.

Step 4 Similarly, we may use column operations to reduce to the case where a11a_{11} divides every a1ja_{1j} in the first row.

We observe that step 1 takes time O(mn)O(mn) , step 2 takes time O(m+n)O(m + n) . We observe that steps 3 and 4 terminate because at each step, a11a_{11} is decremented by at least 1. Hence, we reach step 5 after O(mn+ℓ1(n+m))O(mn + \ell_1(n + m)) time.

Step 5 Subtract off multiples of the first row and column to make all the elements ai1a_{i1} in the first column and a1ja_{1j} in the first row zero, for i,j≠1i, j \neq 1 . Now the matrix looks like this:

(a110⋯00B0)(50.14)\begin{pmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & & & \\ & & B & \\ & & & \\ 0 & & & \end{pmatrix} \qquad(50.14)

Now, we wish to ensure that a11a_{11} divides every element of the submatrix BB . We number BB ’s rows and columns starting at 2.

Step 6 Suppose some entry bijb_{ij} of BB is not divisible by a11a_{11} . We add row ii to row 1 to obtain:

(a11bi2⋯bij⋯bin0BB0).(50.15)\begin{pmatrix} a_{11} & b_{i2} & \cdots & b_{ij} & \cdots & b_{in} \\ 0 & & & & & \\ & & B & & & \\ & & & & B & \\ & & & & & \\ 0 & & & & & \end{pmatrix}. \qquad(50.15)

Next, we apply the division algorithm to obtain

bij=qa11+r(50.16)b_{ij} = qa_{11} + r \qquad(50.16) with q,r∈ℤq, r \in \mathbb{Z} , 0<r<a110 < r < a_{11} . We subtract qq times column 1 from column jj to obtain:

(a11bi2⋯r⋯bin00)(50.17)\begin{pmatrix} a_{11} & b_{i2} & \cdots & r & \cdots & b_{in} \\ 0 & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ 0 & & & & & \end{pmatrix} \quad (50.17)

Step 7 Now, at this point, a11a_{11} is no longer the minimal element of AA , since r<a11r < a_{11} . We go back to step 1, moving rr to a11a_{11} . Since the corner element is decreased by at least 1 each time, the (entire) process terminates after at most ℓ1\ell_1 iterations. Finally, a11a_{11} will divide every entry in BB , and the first row and column will be zero, except for a11a_{11} . Hence, the matrix has the form (50.14), and a11a_{11} divides each element of BB .

Step 8 (Recursive Step) We note that if aa is an integer that divides each entry of AA , and that if A′A' is obtained from AA by any row or column operation, then aa still divides each entry of A′A' . Hence, we can recursively invoke the algorithm on submatrix BB . ▫\square

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 R(n)R(n) required by the reduction algorithm (section 50.5.3), in fact, dominates the computation of homology type, which can clearly be done in time O(D(n2+R(n)))O(D(n^2 + R(n))) . 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 O(s11)O(s^{11}) algorithm, where for an n×mn \times m matrix with maximum coefficient ℘\wp , we define s=m+n+log⁡|℘|s = m + n + \log |\wp| . 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 O(s5)O(s^5) . 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 O(Dn11)O(Dn^{11}) or O(Dn5)O(Dn^5) .

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 (α\alpha -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 (α\alpha) and face removal. Hence, the Betti numbers are parameterized by a continuous scalar value α\alpha , 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 α\alpha -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 α\alpha -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 (α\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 10210^2 – 103 Å310^3 \text{ \AA}^3 . 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 ≤700 Å3\leq 700 \text{ \AA}^3 , 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 Å3\text{\AA}^3 , 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 # 𝒫\mathcal{P} -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.