Efficient Construction of Pathways in the Complement of the Union of Balls in R3

Abstract

Channels of the CYP3A4 Enzyme as detected by MolAxis.
The CYP3A4 is represented by cartoons and the heme prosthetic group is represented by its VDW surface and colored orange. Each channel surface is colored in a different color for the sake of clarity.

Given a molecule modeled by a collection of balls in three-dimensional space we wish to efficiently identify pathways in the complement of their union. The desired pathways should balance between length and clearance. Namely, we prefer short and wide pathways between a given start point and goal point positioned in the complement. MolAxis is a web server and stand-alone software package designed to assist the biologist/biochemist to automatically identify pathways in the complement of molecules. A major contribution of the work is the notion of the pathway graph which approximates an idealistic construct related to the medial axis, and which unlike the medial axis is easy to compute in the case of the complement of the union of balls. We provide theoretical analysis of the properties of the pathway graph.

Publications

• Eitan Yaffe and Dan Halperin
  Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space
  Discrete & Computational Geometry 44(3), pages  660-685, 2010 [link] [bibtex]
  Symposium on Computational Geometry (SoCG), pages 260-269, 2008 [link] [bibtex] [full-version]

• Eitan Yaffe, Dan Fishelovitch, Haim J. Wolfson, Dan Halperin, and Ruth Nussinov
  MolAxis: Efficient and Accurate Identification of Channels in Macromolecules
  Proteins: Structure, Function, and Bioinformatics, 73(1): 72-86, October 2008 [link] [bibtex]
• Eitan Yaffe, Dan Fishelovitch, Haim J. Wolfson, Dan Halperin, and Ruth Nussinov
  MolAxis: A server for Identification of Channels in Macromolecule
  Nucleic Acids Research, Volume 36 (Web Server issue), Pages: W210-W215, July 2008 [link] [bibtex]
  
• Eitan Yaffe
  Efficient Construction of Pathways in the Complement of the Union of Balls in R3
  M.Sc. Thesis, Tel-Aviv University, September 2007 [pdf] [bibtex]

Links

•  The MolAxis website.

• An example of using MolAxis for cavity and tunnel detection by the UCSF Computer Graphics Lab (Chimera team). 

Contact

Eitan Yaffe
Dan Halperin