The Frechet distance is used to measure the similarity between two (oriented) curves. A unique property of this notion of distance is its sensitivity to the order along the two curves. We are investigating robust variants of Frechet distance suitable for partial matching. We also develop efficient algorithms for computing these measures based on the techniques developed for computing shortest paths on polyhedral surfaces. A challenging problem in this context is the extension of Frechet distance from curves to surfaces.

If a protein backbone is represented as a self-avoiding walk on a lattice in 3-space, its contact map is defined as the graph whose nodes are the vertices of the chain and in which two nodes are connected by an arc if they are adjacent in the lattice but not in the chain. The similarity between two self-avoiding walks can be measured by computing an order-preserving mapping of vertices of one contact map to the other that preserves a maximum number of such arcs. This so-called contact-map-overlay measure has been used to measure similarity between two protein backbones. We improve the running time of the previously fastest algorithm and prove bounds on the quality of guaranteed approximations.