Paper by Erik D. Demaine

Reference:

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.

BibTeX

@Article{ProteinMachine_Algorithmica,
  AUTHOR        = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke},
  TITLE         = {Geometric Restrictions on Producible Polygonal Protein
                   Chains},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 44,
  NUMBER        = 2,
  MONTH         = {February},
  YEAR          = 2006,
  PAGES         = {167--181},
  NOTE          = {Special issue of selected papers from the 14th Annual
                   International Symposium on Algorithms and Computation,
                   2003.},

  doi           = {https://dx.doi.org/10.1007/s00453-005-1205-7},
  dblp          = {https://dblp.org/rec/journals/algorithmica/DemaineLO06},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00453-005-1205-7">SpringerLink</A>.},
  copyright     = {Copyright held by the authors.},
  length        = {17 pages},
  papers        = {ProteinMachine_ISAAC2003},
  replaces      = {ProteinMachine_ISAAC2003},
}

Abstract:

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(n²)-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 R³ 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 → ∞.

Comments:

This paper is also available from SpringerLink.

Copyright:

Length:

The paper is 17 pages.

Availability:

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)