A protein is a macromolecule consisting of the permutation of 20 different kinds of amino acids. Amino acids are linearly connected to one another via peptide bonds to form chains. When a protein consists of two chains, it is called a dimer as shown in Fig. 1(a). Shown in Fig. 1(b) and (c) are examples of a trimer (three chains) and a tetramer (four chains), respectively. Since interaction among chains is critical for protein functions, understanding the interaction is getting more important and the geometric properties of the interactions are getting more attention.

사용자 삽입 이미지

Fig. 1  Protein examples: (a) a dimer, (b) a trimer, and (c) a tetramer.


The interaction interface IIF is defined in this paper as follows. Let A = {a1, a2, ..., am}, B = {b1, b2,..., bn} be two chains in a protein, where ai and bj are atoms with appropriate centers and radii. The interaction interface between two chains A and B is defined as IF(A,B) = { p | dist(p,A) = dist(p,B) }, where dist(p,A) denotes the minimum Euclidean distance from p to the surfaces of all van der Waals atoms in the set A. Then, IF(A,B) is a subset of Voronoi faces in VD(A∪B). Hence, IF(A,B) can be easily located by simply checking each Voronoi face with its generating atom types. Note that IF(A,B) expands to infinity.


사용자 삽입 이미지

Fig. 2  A dimer (PDB ID: 1bh8): (a) van der Waals model, and (b) IIF(A,B),


  The infinite Voronoi faces in IF(A,B) are biologically less significant since proteins, as well as IF(A,B), are usually hydrated. Hence, we define a trimmed interaction interface IF(A,B) against a probe of a water molecule. Fig. 2(a) and (b) illstrate the van der Waals atoms of a dimer 1bh8 downloaded from PDB and the corresponding IIF(A,B), respectively. Once an interaction interface is computed, various analyses can be done on the interaction behavior between chains in the protein polymer.


       * 2003년부터 진행해온 연구이다. 석사학위 논문 주제였으나, 아직까지...

크리에이티브 커먼즈 라이선스
Creative Commons License

VDRC have developed and implemented an algorithm which constructs Euclidean Voronoi diagram for spheres in 3-dimensional space by tracing Voronoi edges. Once such a Voronoi diagram is constructed, various spatial queries can be answered most efficiently and exactly. Shown in the following figure is a snapshot of such Voronoi diagram in our software developed

사용자 삽입 이미지

Sphere set Voronoi Diagram



사용자 삽입 이미지

Voronoi faces for sphere set


This Voronoi diagram can be a useful tool to analyze the structural properties of proteins, and therefore we have developed and included various algorithms using the Voronoi diagram in our software for the purpose of analyzing protein structure such as defining protein-protein interface, finding largest empty space, constructing molecular surface, etc.


사용자 삽입 이미지

Seperating faces of atoms into two different groups



사용자 삽입 이미지

Internal voids



사용자 삽입 이미지

Blending surfaces

크리에이티브 커먼즈 라이선스
Creative Commons License

In 2001, VDRC have published a pair of papers in Computer Aided Geometric Design journal, discussing an algorithm to compute Euclidean Voronoi diagram for circles. Shown in the following figure are examples computed from our algorithm. The algorithm is based on an exact computation paradigm and takes advantage of edge-flipping based on the solution of Apollonius 10th problem. They have shown that the algorithm can compute the desired Voronoi diagram in O(N2) without failure. In the middle of the development, the famous Apollonius 10th Problem (a problem to compute circles tangent to three circles) was also solved via Möbius mapping between complex planes.

사용자 삽입 이미지

Circle set Voronoi diagram


The Voronoi diagram for circles can be applied to various geometric problems such as cable packing problem, shortest path problem, and widest channel problem.

사용자 삽입 이미지

Cable packing problem



사용자 삽입 이미지

Shortest path problem



사용자 삽입 이미지

Largest channel problem


크리에이티브 커먼즈 라이선스
Creative Commons License

Suppose that geometric objects are given in a space, a Voronoi diagram is defined by a set of Voronoi regions which are closer to the corresponding object than any other objects. Below figures show the Voronoi diagrams of point and circle sets in a plane. Once such a Voronoi diagram is represented in an efficient data structure, we can efficiently and exactly analyze various structural characteristics of particles in the space.
크리에이티브 커먼즈 라이선스
Creative Commons License