Software

Persistent homology (or simply persistence) is an algebraic-topological invariant of a filtered cell complex. Perseus computes this invariant for a wide class of filtrations built around datasets arising from point samples, images, distance matrices and so forth.

The standard algorithm for computing persistence intervals relies on Smith normal form and is therefore of super-cubical complexity in the total number of cells. Perseus reduces the original filtration drastically in linear time via discrete Morse theory without altering its persistent homology. The reduced complex is then passed on to the standard algorithm. This Morse-theoretic pre-processing results in incredible savings of both time and memory when compared to the standard approach. More details are in the associated paper.

For a quick introduction to persistent homology, see the surveys by Carlsson and Ghrist. An elementary account of simplicial complexes, what homology actually measures, and some biological applications can be found in my introductory paper written with Sazdanovic. For a much more comprehensive (but elementary!) overview of applied topology, consult Rob Ghrist’s book.

Go to the Perseus manual →

The diamond cubic is a highly symmetric three-dimensional graph structure in which all angles in sight are tetrahedral. Statistics of self-avoiding random walks on diamond cubics might provide convenient null hypotheses when analysing corresponding structures of protein molecules, since protein molecules are also built on a backbone of tetrahedrally arranged atoms. Norris generates self-avoiding random walks on diamond cubics. The C++ source is a single file.

Usage

Open rwalk.cpp in any text editor and change the following #define globals at the top of the file to suit your requirements:

WALKSIZE

the number of steps in the walk

NUMPIVOTTRYS

the number of pivot attempts

NUMWALKS

the number of random walks to generate (default 1)

FILESTR

how the output files are named; the default is rw_(walk number).txt

Now compile the file with any standard C++ compiler and run the executable. For instance, on a Unix-type terminal with gcc installed:

g++ rwalk.cpp -O3 -o norris
./norris

That’s it! The output is a collection of NUMWALKS files (named according to FILESTR) in the working directory. Each file contains an ordered list of 3D points, one per line, representing the vertices of the diamond cubic traversed during a self-avoiding walk.

How it works

Norris uses the famous pivot algorithm to create self-avoiding walks. First, we generate a self-avoiding walk of the desired length by doing something obvious. On the integer lattice, an obvious initial walk of length n would start at the origin and go in the +X direction n times. The starting walk for a diamond cubic requires a subtler approach since it lacks translation-invariance, but the principle is the same.

Next, we pick a random point P, called the pivot, on this walk and apply a random symmetry of the diamond cubic (which fixes P) to all the points after P. If the new walk is self-avoiding, we keep it and apply another symmetry at another point; if not, we discard the symmetry and try again. Repeating this for a large enough number of pivot attempts generates a truly random self-avoiding walk.