• Computer Graphics and CAD • Previous Articles     Next Articles

Higher-Order Level-Set Method and Its Application in Biomolecular Surfaces Construction

Chandrajit L. Bajaj1, Guo-Liang Xu2, and Qin Zhang2,3   

  1. 1CVC, Department of Computer Science, Institute for Computational Engineering and Sciences, University of Texas at Austin, TX 78712, U.S.A. 2LSEC, Institute of Computational Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100190, China 3School of Sciences, Beijing Information Science and Technology University, Beijing 100192, China
  • Received:2007-06-28 Revised:2008-08-28 Online:2008-11-10 Published:2008-11-10

We present a general framework for a higher-order spline level-set (HLS) method and apply this to biomolecule surfaces construction. Starting from a first order energy functional, we obtain a general level set formulation of geometric partial differential equation, and provide an efficient approach to solving this partial differential equation using a $C^2$ spline basis. We also present a fast cubic spline interpolation algorithm based on convolution and the Z-transform, which exploits the local relationship of interpolatory cubic spline coefficients with respect to given function data values. One example of our HLS method is demonstrated, which is the construction of biomolecule surfaces (an implicit solvation interface) with their individual atomic coordinates and solvated radii as prerequisites.

[1]Osher S, Fedkiw R. Level Set Method and Dynamic Implicit Surfaces. New York: Springer, 2003.
[2]} Sethian J A. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge Monographs on Applied and Computational Mathematical, Second edition, Cambridge University Press, 1999.
[3]} Osher S, Sethian J. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. {\it Journal of Computational Physics}, 1988, 79(1): 12--49.
[4]} Sanner M, Olson A, Spehner J. Reduced surface: An efficient way to compute molecular surfaces. {\it Biopolymers}, 1996, 38(3): 305--320.
[5]} Connolly M. Analytical molecular surface calculation. {\it J. Appl. Cryst.}, 1983, 16(5): 548--558.
[6]} Richards F M. Areas, volumes, packing, and protein structure. {\it Ann. Rev. Biophys. Bioeng.}, 1997, 6: 151--176.
[7]} Liang J, Edelsbrunner H, Fu P, Sudhakar P V, Subramaniam S. Analytical shape computation of macromolecules: I. molecular area and volume through Alpha shape. {\it Proteins: Structure, Function, and Genetics}, 1998, 33(1): 1--17.
[8]} Cazals F, Proust F. Revisiting the description of Protein-Protein interfaces, part I: Algorithms. Research Report 5346, INRIA, 2004.
[9]} Cazals F, Proust F. Revisting the description of Protein-Protein interface, part II: Experimental study. Research Report 5501, INRIA, 2005.
[10]} Cazals F, Proust F, Bahadur R P, Janin J. Revisiting the Voronoi description of Protein-Protein interfaces. {\it Protein Sci.}, 2006, 15(9): 2082--2092.
[11]} Akkiraju N, Edelsbrunner H. Triangulating the surface of a molecule. {\it Discr. Appl. Math.}, 1996, 71(1-3): 5--22.
[12]} Liang J, Edelsbrunner H, Fu P, Sudhakar P V, Subramaniam S. Analytical shape computation of macromolecules: II. inaccessible cavities in protein. {\it Proteins: Structure, Function, and Genetics}, 1998, 33(1): 18--29.
[13]} Edelsbrunner H. Deformable smooth surface design. {\it Discrete $\&$ Computational Geometry}, 1999, 21(1): 87--115.
[14]} Cheng H-L, Dey T K, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. {\it Discrete $\&$ Computational Geometry}, 2001, 25(4): 525--568.
[15]} Bajaj C, Lee H, Merkert R, Pascucci V. NURBS based B-rep Models from Macro-molecules and their properties. In {\it Proc. Fourth Symposium on Solid Modeling and Applications}, 1997, pp.217--228.
[16]} Bajaj C, Pascucci V, Shamir A, Holt R, Netravali A. Dynamic maintenance and visualization of molecular surfaces. {\it Discrete Applied Mathematics}, 2003, 127(1): 23--51.
[17]} Blinn J. A generalization of algebraic surface drawing. {\it ACM Transactions on Graphics}, 1982, 1(3): 235--256.
[18]} Duncan B S, Olson A J. Shape analysis of molecular surfaces. {\it Biopolymers}, 1993, 33(2): 231--238.
[19]} Grant J, Pickup B. A Gaussian description of molecular shape. {\it Journal of Phys. Chem.}, 1995, 99(11): 3503--3510.
[20]} Zhang Y, Xu G, Bajaj C. Quality meshing of implicit solvation models of biomolecular structures. {\it Computer Aided Geometric Design}, 2006, 23(6): 510--530.
[21]} Baker N, Sept D, Joseph S, Holst M, Mc-Cammon J. Electrostatics of nanosystems: Application to microtubules and the ribosome. In {\it Proc. Natl. Acad. Sci.}, USA, 2001, pp.10037--10041.
[22]} Holst M, Saied F. Multigrid solution of the Poisson-Boltzmann equation. {\it J. Comput. Chem}., 1993, 14(1): 105--113.
[23]} Bajaj C L, Xu G, Zhang Q. {Smooth surface constructions via a higher-order level-set method}. ICES Report 06-18, Institute for Computational and Engineering Sciences, The University of Texas at Austin, 2006.
[24]} Faugeras O D, Keriven R. Variational principles, surface evolution, PDE's, level-set methods, and the stereo problem. {\it IEEE Trans. Image Process.}, 1998, 7(3): 336--344.
[25]} Xu G, Zhang Q. Construction of geometric partial differential equations in computational geometry. {\it Mathematica Numerica Sinica}, 2006, 28(4): 337--356.
[26]} Osher S, Shu C W. High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. {\it SIAM Journal of Numerical Analysis}, 1991, 28(4): 907--922.
[27]} Peng D, Merriman B, Osher S, Zhao H, Kang M. A PDE-based fast local level set method. {\it Journal of Computational Physics}, 1999, 155(2): 410--438.
[28]} Bajaj C L, Djeu P, Siddavanahalli V, Thane A. Texmol: Interactive visual exploration of large flexible multi-component molecular complexes. In {\it Proc. the Annual IEEE Visualization Conference'04}, Austin, Texas, USA, 2004, pp.243--250.
No related articles found!
Full text



[1] Xu Meirui; Liu Xiaolin;. A VLSI Algorithm for Calculating the Tree to Tree Distance[J]. , 1993, 8(1): 68 -76 .
[2] Pan Zhigeng; Shi Jiaoying; Hu Bingfeng;. DGLa: A Distributed Graphics Language[J]. , 1994, 9(2): 97 -106 .
[3] LIN Hua; LU Mi; Jesse Z.FANG;. A Direct Approach for Finding Loop Transformation Matrices[J]. , 1996, 11(3): 237 -256 .
[4] SHEN Yidong;. A General Scheme for Formalizing Defaults Usingthe Predicate ab(I,S)[J]. , 1999, 14(2): 159 -164 .
[5] SONG Jianping; HOU Zifeng; SHI Yuntao;. An Optimal Multicast Algorithm for Cube-Connected Cycles[J]. , 2000, 15(6): 572 -583 .
[6] Zhi Jin. Revisiting the Meaning of Requirements[J]. , 2006, 21(1): 32 -40 .
[7] Tao Ju. Fixing Geometric Errors on Polygonal Models: A Survey[J]. , 2009, 24(1 ): 19 -29 .
[8] Osman Hasan and Sofiéne Tahar, Senior Member, IEEE, Member, ACM . Formally Analyzing Expected Time Complexity of Algorithms Using Theorem Proving[J]. , 2010, 25(6): 1305 -1320 .
[9] Xue-Jun Yang (杨学军), Senior Member, CCF, Member, ACM, IEEE, Xiang-Ke Liao (廖湘科), Senior Member CCF, Member, ACM, Kai Lu . The TianHe-1A Supercomputer: Its Hardware and Software[J]. , 2011, 26(3): 344 -351 .
[10] Fred S. Roberts. The Challenges of Multidisciplinary Education in Computer Science[J]. , 2011, 26(4): 636 -642 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved