In this project we study algorithms for polygonal representations of protein structures. We developed algorithms for the writhing numbers, the Wiener index, the detour, and for simplifying polygons.

The writhing number of a polygonal knot is an attempt to capture the physical phenomenon that a cord tends to form loops and coils when it is twisted. Other than its mathematical interest, it has received attention both in physics and in biochemistry. For example, it is critical in understanding various geometric conformations we find for circular DNA in solutions. We show that the writhing number of a knot is related to the average winding number of its Gauss map. Using this relationship, we gave a subquadratic algorithm for computing the writhing number for a polygonal knot. We implemented a different, simple algorithm which significantly outperform current algorithms in practice, and applied it to protein backbones and DNA chains.

Drugs and other chemical compounds are often modeled as polygonal shapes, called their molecular graphs, which can be paths, trees, or general graphs. An indicator defined over such a molecular graph, the Wiener index, has been shown to be correlated to various chemical properties of the compound. The Wiener index conjecture for trees states that for any integer n, one can find a tree with Wiener index n. We make a significant step forward toward proving this conjecture by showing that it suffices to consider a succinct family of trees. We prove several properties of this family and describe polynomial-time algorithms to compute trees in this family and their Wiener index. We also show that at least 10 to the 8 integers are Wiener indices of trees in this family, compared to the previous record of 10 to the 4.

The detour of a polygonal curve, defined as the maximum ratio of the arc length over the Euclidian distance between any two points on the curve, measures how much the curve bends. It relates the Frechet to the Hausdorff distance in the sense that if the detour of each of two curves is at most k then the Frechet distance between the two curves is at most k times their Hausdorff distance. We present an nlogn expected-time algorithm for computing the detour of a polygonal chain under L2-metric in the plane and a subquadratic algorithm for a polygonal chain in 3-space.

Simplification of geometric substructures is often required to eliminate noise from experimentally obtained models. For example, the protein backbones obtained through experimental models often have noise-induced errors. A convenient way of removing such errors is to simplify the protein backbone, thus removing small noise. However, nearly all simplification algorithms have at least quadratic running time, thus making them less useful in practice. In particular, the algorithms for curves in 3-space all have at least quadratic running time, and hardly any efficient algorithms (and their implementations) exist. We propose an efficient near-linear time approximation algorithm for curve simplification under two error measures – the Frechet and Hausdorff error measures. We have implemented our algorithms, and experiments validate that our algorithms are efficient, and always produce good simplifications, very close to the optimal simplification