Knottedness of Compact Lattice Chains

Knottedness of Compact Lattice Chains
(PDF version)
by Rhonald Lua
rlua@physics.umn.edu
adviser: Professor Alexander Yu. Grosberg

Abstract:
A method to determine the type of knot formed by a compact lattice chain is described. The compact lattice chain refers to a lattice self-avoiding walk that visits ever lattice site within a cubic region. The method is implemented in computer code as C++ and Java programs. As a first measure of knot complexity, the average number of crossings in the knot projection for a range of chain sizes is determined. Next, the frequency of occurrence of the first few types of knots in the compact lattice chains is measured. There is also particular interest in isolating those chains that are trivial or unknotted. These chains may be analyzed further to yield information such as the statistics of the sub-chains.

Contents
I. Introduction
II. Method
    A. Generating Compact Lattice Chains
    B. Generating Plane Projection
    C. Preprocessing
    D. Computing the Alexander Polynomial
    E. Computing the Vassiliev Invariants
III. Results
    A. Average Crossing Number
    B. Knot/Unknot Probabilities
    C. Sub-chain Statistics
IV. Conclusions
Acknowledgments
Appendix
    A. Programs and Source Code
References

I. Introduction

    Self-avoiding random walks, both on and off lattice, are frequently used to model the spatial configuration of a polymer chain. In a lattice random walk, the monomer units comprising the polymer are represented by the lattice sites visited by the walk, while the bonds are represented by the links between adjacent lattice sites.
    A compact lattice chain is a self-avoiding walk that visits every lattice site within a cubic region and forms a closed loop in space (Figure 1a). This chain could serve as a model of a compact loop of a single polymer (e.g. a globular protein), or a 'sea' of polymer strands (e.g. a polymer melt).
    Compact lattice chains are very amenable to computer analysis. As such, it may be used effectively to explore interesting properties of polymers, foremost being their knottedness or topology. For example, it is found that DNA loops in gel-electrophoresis experiments move faster the more complicated the knot type [1]. The knottedness of compact lattice chains may also manifest itself on the statistics of its sub-chains or segments. (These sub-chains could possibly model polymers in a 'melt'.) For instance, the relationship between mean square end-to-end distance (or some measure of size, such as gyration radius) of a sub-chain and the number of steps comprising this sub-chain could be studied to yield 'scaling relations' and 'critical exponents'.
    A knot is a closed curve in space which does not intersect itself. An intuitive grasp of what a knot is should suffice to enable one to understand, and hopefully appreciate, the ideas described in this paper. Ironically, it is this intuitive appeal of knots that makes its study and associated computations not-so-trivial. The necessary concepts will be introduced as we go along.
    The primary mathematical tools employed from knot theory to determine the knot type are the Alexander polynomial invariant, a.k.a. D(t) [2], and the Vassiliev invariant of degrees two (v2) and three (v3) [3]. The knot invariants serve as a signature of the knot type. These invariants are computed from a plane projection of the knot. Each invariant is guaranteed not to change value or form as the knot is deformed without cutting or letting the strands pass through each other (these 'destructive' operations may change the knot type). A single knot invariant may correspond to more than one knot type though (more about this later).
    The compact lattice chains studied in this project are generated with code developed by Alexander Borovinskiy based on (and improving upon) reference [4]. The chains are specified on a regular lattice as a sequence of non-negative integers (x y z). As a rough measure of the complexity of the knots formed for each chain size, the average number of crossings in the projection is determined. The knot invariants for each chain are also determined. These lead to each chain being associated with a particular knot type. The spatial coordinates of chains with knot invariants corresponding to a trivial knot are collected and analyzed further.

II. Method

Starting from a compact lattice chain (Figure 1a), which we henceforth just call a chain, it is desired to obtain a set of numbers corresponding to the Alexander and Vassiliev invariants. I shall illustrate the process visually, but keep in mind that much of the steps are implemented on abstract program data structures. The following are the major steps (See also figure 1 a-d):

Generate LxLxL compact lattice chain.
Convert three-dimensional conformation of chain into a two-dimensional plane projection.
Preprocess plane projection to reduce the number of crossings (or intersections) in the knot projection via so-called Reidemeister moves.
Construct an Alexander matrix and obtain value of Alexander polynomial, D(-1), by evaluating a determinant.
Construct a Gauss code for the knot and evaluate the Vassiliev invariants, v2 and v3.

Figure 1a. Compact lattice chain (4x4x4).
Green circles indicate lattice sites (nodes). Red lines represent links (bonds).

Figure 1b. Knot projection.
Black (blue) circle indicates vertical segment is an underpass (overpass) in the intersection.

Figure 1c. Preprocessing.
Knot projection after symbolic removal of trivial crossings.

Figure 1d. Computing knot invariants.
The values shown correspond to either a right-handed (shown) or left-handed trefoil.

Figure 1 a-d. How the procedure works on a 4x4x4 compact lattice chain knotted in a trefoil.

Each step is discussed in more detail below.

A. Generating Compact Lattice Chains
A chain is generated using a method called Hamiltonian path generation [4]. A chain is specified by giving the non-negative integer coordinates of its nodes. The dimension (LxLxL) of a closed chain may only be even. Thus, the chain lengths explored in this study belong to the sequence N=L³=4³=64, 216, 512, 1000, ... (no knots are formed for L=2). The generated chains are assumed to be 'fairly' sampled (ergodic).

B. Generating Plane Projection
The knot invariants are usually evaluated given a planar representation of the knot. This is obtained by projecting the nodes (sites) and links of a chain onto a plane. The criteria for a good projection are (1) the overpassing and underpassing strands of the knot are clearly specified, and (2) only two strands may intersect at a point on the projection. This may be achieved simply by looking at figure 2a. The nodes are projected onto the diagonal of a horizontal square. We may consider the x,y coordinates on the plane projection of a node to be related to its x,y,z coordinates in space in the following manner: (x,y,z) --> (x+z/L, y+z/L). Here L is the maximum coordinate + 1, or one more than the dimension of the bounding cubic region. Note that this method is better than using rotation matrices which would require explicit computation of sines and cosines.

Figure 2a. Projecting the nodes (circles) onto the horizontal plane. Idea suggested by Alexander Borovinskiy.

Figure 2b. Projected nodes and links of figure 1a by the method of figure 2a.

By referring to figure 2b, it is clear that crossings (intersections) only occur between links that appear as horizontal and vertical segments in the projection. As to which segment in a crossing is an overpass, one need only check which segment corresponds to nodes that have a larger z-coordinate.
Another important piece of information associated with a crossing is its 'sign'. The sign represents the relative orientation of the crossing segments. It is required in specifying a knot and calculating the invariants. The sign is defined by imagining taking a trip along the path defined by the knot, in the process associating a direction or arrow to the knot. A +1 (-1) is then assigned to the crossing in which the overpassing segment points to the right (left) of the underpassing segment (Figure 3).

Figure 3. Sign of an intersection.

These three pieces of information - sequence of crossings, overpass/underpass, sign - suffice to specify a knot.

C.Preprocessing
Once a plane projection faithfully representing the knottedness of a chain is obtained, one more practical step is needed before the knot invariants are calculated. It is apparent that there occur many crossings that are not essential in classifying a knot. These crossings may be removed by intuitive operations on the knot projection called Reidemeister moves (Figure 4a). Reidemeister has shown that two knots are equivalent (the knot theory term is 'ambient isotopic') if and only if one may be transformed into the other via a sequence of Reidemeister moves. Unfortunately, there is no recipe for producing such a sequence of moves in a quick and deterministic fashion.
In the absence of an algorithm to minimize the number of crossings, the simplest thing to do is to scan the knot for certain patterns and implement moves on these patterns that would reduce (but not necessarily minimize) the number of crossings. These moves are the first two Reidemeister moves plus that shown in Figure 4b.

Figure 4a. The three Reidemeister moves.
Move I is simple uncurling. Move II is removal of overlap. Move III slides the vertical segment passed a crossing.
It is to be understood that one is working with only portions of a knot

Figure 4b. Top drawing shows a combination of the third and first Reidemeister moves.
The bottom drawing shows a loop underpassing an unspecified section of the knot.

The reduction is necessary from a code performance standpoint as the computation time of the knot invariants rises quickly as the number of crossings in the knot projection increases (see D and E). In the range of chain sizes explored, the moves reduce the number of crossings to less than half (see figure 6). It is found that the most effective in removing crossings is move II while the least effective is move I+III (Figure 4b).
An upper bound for the number of crossings for a given L may be calculated by referring to a diagram like figure 2b. Letting each node be connected to its nearest neighbors, the exact number of crossings comes out as L(L-1)³. In fact one may go further and predict the average number of crossings. Assuming the orientations of the links (of the 3-D chain) are equally distributed among the three orthogonal directions, one may derive the following expression

(Expression 1) for the average crossing number.

D. Computing the Alexander Polynomial
    What follows is a short discussion of the general features of the knot invariants used in this study. The detailed recipes for computing them are described very well in the references.
    The Alexander polynomial is a one-variable polynomial (D(t)) with integer coefficients. The polynomial corresponding to a knot does not change (within powers of t) as the knot is deformed non-destructively in space, which is equivalent to performing Reidemeister moves on the projection. Calculation of the Alexander polynomial entails constructing a matrix, called the Alexander matrix, and taking its determinant (although this is not the only way) [2]. This matrix is very sparse. The only possible non-zero entries are 1,-1,-t and t-1. The dimension of this matrix is identical to the number of crossings (actually C-1) in the knot projection.
    The Alexander polynomial is not a 'perfect' invariant in the sense that it fails to distinguish between certain knots. Also the Alexander polynomial does not distinguish a knot from its mirror image (A knot that is distinct from its mirror image is called 'chiral', otherwise it is 'achiral'.).
    For simplicity, the Alexander polynomial is evaluated at a special value of the variable (D(t=-1)). This restricts the elements of the Alexander matrix to a small set of integer values. The correct way to evaluate the Alexander polynomial is then to evaluate a determinant using only integer operations. For an algorithm such as Gaussian elimination, the computation time (really the number of multiplications) should scale as the third power of the matrix dimension (C-1).

E. Computing the Vassiliev Invariants
The Vassiliev invariants are calculated in a combinatorial fashion starting from a Gauss code representing the knot [3]. For example, a Gauss code for a left-handed trefoil is b-1,a-2,b-3,a-1,b-2,a-3. The group of three symbols separated by commas represents a crossing. The letter 'b' (for 'below', and 'a' for 'above') indicates the segment is an underpass (overpass). The second symbol is the sign mentioned earlier. The third symbol is a label for the crossing. The label is required in order to know when the same crossing is going to be traversed a second time (note that a crossing is encountered twice when making a round trip along the knot - once as an underpass and once as an overpass). The Gauss code may be represented pictorially by a chord diagram (Figure 5).

Figure 5. Chord diagram for a knot (trefoil) with Gauss code b-1,a-2,b-3,a-1,b-2,a-3.
The chords represent the crossings. The arrow head (tail) indicates an underpass (overpass).
The circle (knot) is traversed along the direction indicated by the arrow.

    The computation of the Vassiliev invariants is essentially a simple pattern recognition task on the symbols of the Gauss code. Certain patterns of overpasses and underpasses (which may be depicted in a diagram like figure 5) are assigned weights and the contributions of all matching patterns in the knot are added together to yield a number corresponding to each Vassiliev invariant. The Vassiliev invariant of degree two (v2) requires a simpler pattern to search for than that for the Vassiliev invariant of degree three (v3). This implies that v2 takes much shorter time to evaluate than v3.
    The Vassiliev invariants are coefficients of a certain expansion of a polynomial similar to the Alexander polynomial, called the Jones polynomial. This polynomial is still not 'perfect', but in contrast to the Alexander polynomial, the more powerful Jones polynomial does distinguish between mirror images. Of the two Vassiliev invariants used, the degree three invariant gives opposite signs for mirror images. One may deduce from this property that an achiral knot has v3 equal to zero (See table 1 below).
    The Arf invariant, which takes only values 0 or 1, is obtained somewhat as a byproduct of the calculation of the Vassiliev invariant of degree two.

Once the knot invariants for a compact lattice chain are determined, that chain may be assigned a knot type. For example, the knot invariants for the 4x4x4 chain in figure 1a have invariants |D(-1)|=3,v2=1,|v3|=1. These values are identical to the (pre)computed values for a trefoil. So the chain in figure 1a is classified as a trefoil.
In general, there is as yet no complete set of knot invariants that could unambiguously identify a knot. However, by taking the invariants D(-1), v2, v3 together, the probability of incorrectly classifying a knot is much reduced. For instance, the set of numbers corresponding to a trivial knot (D(-1)=1,v2=0,v3=0) are unique among 'prime' knots with ten or fewer crossings in their projection (249 in number). Also, no knot has yet been found that has the same Jones polynomial as the trivial knot.

III. Results

A. Average Crossing Number
The data for average crossing number versus chain length are shown in figure 6 together with the prediction (Expression 1). For each chain, the knot projections onto each of the orthogonal planes (xy,zx,yz) were obtained and the number of crossings determined for each projection. Each chain therefore contributed three projections towards computing the average crossing number. As an aside, the projection (xy,zx or yz) that gives the least number of crossings (after reduction) is chosen when the time comes to compute the knot invariants.

Figure 6. Average crossing number versus compact lattice chain length (N=L³),
plotted in a log-log scale. Prediction and linear fit also shown.

The results for average crossing number is significant in two ways. First, the average crossing number may provide a rough measure of knot complexity for a given chain size. Second, for large L, the expression for the average crossing number (as well as for the upper bound) becomes L⁴=N^(4/3) to within a constant factor. This expression is reminiscent of the 'four-thirds power' law relating average crossing number to 'rope length' for tight knots [5,6].

B. Knot/Unknot Probabilities
The probabilities of occurrence of the trivial knot (unknot), 3-1 (trefoil), 4-1 (figure-eight), 5-1 (star) and 5-2 versus the chain length (N=L³ and L=4,6,8,10,12) are shown together with their knot diagrams (Figures 7,8,9 below). This list is ordered according to increasing velocity in gel-electrophoresis experiments (A rationale for this ordering could be that more complicated knots tend to be more compact and therefore move faster in solution). These graphs are similar to those of studies made with other chain models [7]. Notice (Figure 9) that between knots with five crossings in the projection, 5-2 occurs more often than 5-1 (perhaps because 5-2 looks more asymmetric?). This particular result also agrees with studies done with other chain models, such as that of [2]. The barely visible error bars are the computed standard deviations assuming the occurrence of a particular knot is binomially distributed.

Figure 7. Log-linear plot for probability of occurrence of trivial knots in compact lattice chains,
together with linear fit (actually exponential but appears as a line in the plot).
This behaviour is expected as knot complexity increases (trivial knots become more rare) with chain size.

Left-handed trefoil (3-1). Distinct from the right-handed trefoil (its mirror image).

Figure eight. Identical to its mirror image (i.e. it is 'achiral').

Star (5-1).

5-2. This knot travels faster than 5-1 in gel-electrophoresis experiments.

Figure 8. Diagrams for the first four knots. The trivial knot (unknot) is equivalent to a circle.

Figure 9. Probability of occurrence of the first four 'prime' knots.

KNOT	Alexander, \|D(-1)\|	Vassiliev, v2	\|v3\|	CHIRAL?
Trivial	1	0	0	NO
Trefoil, 3-1	3	1	1	YES
Figure eight, 4-1	5	-1	0	NO
Star, 5-1	5	3	5	YES
5-2	7	2	3	YES

Table 1. Knot invariants for the trivial knot and the first four knots.

The present study does not distinguish between a knot and its mirror image. This means the Vassiliev invariant of degree three (which flips sign when a mirror image is taken) is determined and compared only in magnitude.
For the purpose of efficiently counting how many times the five simple knots occur, the program computed the invariants in increasing order of computation time. So the invariant that takes the least amount of time, v2, is computed first. If the resulting number corresponds to one of the five knots, the next invariant is computed, D(-1). If this again corresponds to one of the five knots under study, the slowest- to-compute invariant, v3, is evaluated last.

C. Sub-chain Statistics
The measurements for the mean-square end-to-end distance and gyration radius for a range of sub-chain lengths are shown in figures 10a,b for compact lattice chains of size 12x12x12. Both indicators of size give a smaller radius for the sub-chains of trivial knots. We may interpret the results by saying that trivial knots are less entangled and therefore portions of it tend to form smaller clumps. These results are encouraging as it reinforces our belief that the method of knot invariants do indeed give us the correct knot type.

Figure 10a. Measurements of mean square end-to-end distance versus sub-chain length
made from 109 trivial knots and 187 non-trivial knots, plotted in a log-log scale.

Figure 10b. Log-log plot of mean square gyration radius versus sub-chain length.
A formula for the square of gyration radius is

where the r's are radius vectors of the nodes and M is the number of nodes in the sub-chain.

Figure 10c. Log-log plot of mean square end-to-end versus sub-chain length (from 10 to 100) with linear fit.

The choice of compact lattice chain size (12x12x12) was guided by the desire to have the largest possible chain and not-too-slow program execution time. It took about one day for a single program to generate and analyze 2500 chains on a supercomputer (e.g. IBM-SP at the Minnesota Supercomputing Institute) to yield on average 5 trivial knots. The program may still be optimized, in particular if native math software libraries on the supercomputer are utilized (e.g. IBM's ESSL).
The range of sub-chain lengths explored was motivated by the desire to model a linear polymer immersed in a large sea of other polymers (e.g. a polymer melt). The number of steps in the sub-chain beyond which the effects of the cube boundaries are 'felt' is estimated to be about 12²=144, as in a random walk. Indeed, figure 10a shows that the curves begin to flatten at around M=150, indicating that the boundaries have been encountered by the sub-chains.

IV. Conclusions
A method to analyze the knottedness of compact lattice chains was described and implemented. The results for average crossing number and knotting/unknotting probabilities are reminiscent of those of other authors. In particular, the average crossing number is related to the chain length via a four-thirds power for large chain sizes. Also, the unknotting probability drops roughly exponentially versus chain length. Analysis of sub-chain sizes indicate a difference between trivial knots and non-trivial knots. There is a range of sub-chain lengths where sub-chains of trivial knots are smaller on average than sub-chains of non-trivial knots.

Acknowledgments
Thanks to Professor Alexander Grosberg for his guidance in this project. Thanks also to Alexander Borovinskiy for useful discussions.
Some of the images (DNA photo, the knot diagrams in figure 8) were culled from the web.

Appendix
A. Programs and Source Code
The methods described in this paper and in the references were implemented in several computer languages and platforms, most notably in C++ and Java. The C++ implementation of the knot analysis code does the real work; it is more comprehensive and couples easily with the loop/chain generation routines of my colleagues (Alexander Borovinskiy and Nathan Moore). The Java program is primarily for prototyping and visualization purposes.
The link to programs and source code is http://www.physics.umn.edu/~rlua/knots.

References
[1] G. Buck and J. Simon, "Energy and length of knots", Lectures at Knots96 (Ed. S. Suzuki), World Scientific Publ., 1997, 219-234.
[2] A.V. Vologodskii, A.V. Lukashin, M.D. Frank-Kamenetskii, and V.V. Anshelevich, Zh. Eksp. Fiz. 66, 2153 (1974) [Sov. Phys. JETP 39, 1059 (1974)]
[3] M. Polyak and O. Viro, Gauss Diagram Formulas for Vassiliev Invariants, preprint.
[4] R. Ramakrishnan, J.F. Pekny, and J.M. Caruthers, J. Chem. Phys. 103, 7592 (1995).
[5] J. Cantarella, R.B. Kusner and J.M. Sullivan, Tight Knot Values Deviate from Linear Relations, Nature, 392 (1998) pp. 237-238.
[6] G. Buck, Four-thirds Power Law for Knots and Links, Nature, 392 (1998), pp. 238-239.
[7] T. Deguchi and K. Tsurusaki, "Random Knots and Links and Applications to Polymer Physics", Lectures at Knots96 (Ed. S. Suzuki), World Scientific Publ., 1997, 95-122.

Back to Knots