Paper by Erik D. Demaine

Erik D. Demaine, Stefan Langerman, and Joseph O'Rourke, “Geometric Restrictions on Producible Polygonal Protein Chains”, Algorithmica, volume 44, number 2, February 2006, pages 167–181. Special issue of selected papers from the 14th Annual International Symposium on Algorithms and Computation, 2003.

Fixed-angle polygonal chains in 3D serve as an interesting model of protein backbones. Here we consider such chains produced inside a “machine” modeled crudely as a cone, and examine the constraints this model places on the producible chains. We call this notion producible, and prove as our main result that a chain whose maximum turn angle is α is producible in a cone of half-angle ≥ α if and only if the chain is flattenable, that is, the chain can be reconfigured without self-intersection to lie flat in a plane. This result establishes that two seemingly disparate classes of chains are in fact identical. Along the way, we discover that all producible configurations of a chain can be moved to a canonical configuration resembling a helix. One consequence is an algorithm that reconfigures between any two flat states of a “nonacute chain” in O(n) “moves,” improving the O(n2)-move algorithm in [ADD+02].

Finally, we prove that the producible chains are rare in the following technical sense. A random chain of n links is defined by drawing the lengths and angles from any “regular” (e.g., uniform) distribution on any subset of the possible values. A random configuration of a chain embeds into R3 by in addition drawing the dihedral angles from any regular distribution. If a class of chains has a locked configuration (and no nontrivial class is known to avoid locked configurations), then the probability that a random configuration of a random chain is producible approaches zero geometrically as n → ∞.

This paper is also available from SpringerLink.

Copyright held by the authors.

The paper is 17 pages.

The paper is available in PostScript (5391k), gzipped PostScript (3069k), and PDF (464k).
See information on file formats.
[Google Scholar search]

Related papers:
ProteinMachine_ISAAC2003 (Geometric Restrictions on Producible Polygonal Protein Chains)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 16, 2024 by Erik Demaine.