We present an efficient algorithm for maintaining the boundary and surface area
of protein molecules as they undergo conformational changes.
We also describe a robust
implementation of the algorithm and report on experimental results with our
implementation on proteins with hundreds of residues. Our work extends and
combines two previous results: (i) controlled perturbation for static molecular
surfaces, and (ii) data structures for self-collision testingand energy maintenance of proteins that change
conformation. As our method keeps a highly accurate
representation of the boundary surface and of the voids in the molecule, it can
be useful in various applications, in particular in Monte Carlo Simulation.
In addition we propose, analyze and implement an alternative method for
efficiently recalculating the surface area under conformational (and hence
topological) changes based on techniques for efficient dynamic maintenance of
graph connectivity. This method greatly improves the running time of our
algorithm on most inputs, as we demonstrate in the experiments reported here.
Links
Eran Eyal and
Dan Halperin Dynamic Maintenance of Molecular Surfaces under Conformational Changes
Proc. 21st ACM Symposium on Computational Geometry, Pisa, June 2005, pp 45--54.
[BibTex,pdf]
Eran Eyal and
Dan Halperin Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity
To appear in Proc. 5th Workshop on Algorithms in Bioinformatics, Mallorca, October 2005.
[BibTex]
![[Molecule]](../images/dynsur.gif)
![[Projects Page]](../images/icons/projects.gif){kind=icon}
![[Top]](../images/icons/top.gif){kind=icon}
