83 0

Quasi-triangulation의 심플렉스 Query 최적화와 이를 이용한 단백질 분자구조 분석

Title
Quasi-triangulation의 심플렉스 Query 최적화와 이를 이용한 단백질 분자구조 분석
Other Titles
Query Optimization of Simplexes in Quasi-triangulation and Its Application to the Analysis of Molecular Structure
Author
김재관
Alternative Author(s)
Kim, Jae-Kwan
Advisor(s)
김덕수
Issue Date
2012-02
Publisher
한양대학교
Degree
Doctor
Abstract
Molecular shape is fundamental in determining molecular function. Therefore, the analysis of three-dimensional protein structure plays an important role in structural bioinformatics. To efficiently analyze three-dimensional protein structure, it is necessary to have the representation of the proximity among atoms. In recent years, it has been reported that the beta-complex (whose boundary is the beta-shape) is a powerful computational construct for many structure- or shape-related problems of molecules. Given a quasi-triangulation, the dual structure of the Voronoi diagram of a molecule, querying its simplexes of a particular bounding state corresponding to the spherical probe of a given radius occurs frequently. The computation of the beta-complex is such an example which has various useful applications for reasoning the spatial properties of molecules. While such simplexes can be found by linearly scanning all simplexes in the quasi-triangulation, it is desirable to do the query faster. In this dissertation, we present a query optimization for the simplexes in the quasi-triangulation. Based on this query optimization, we show an efficient query algorithm for the quasi-triangulation using the set of sixteen primitives and the set of ten high-level query operators. In particular, the proposed method shows an extremely efficient performance for incremental queries. Then, we apply this optimized queries to the analysis of molecular structure. First, the concept of protein sphericity is introduced based on the beta-complex and beta-shape of a protein. Given the volume of a beta-shape, the ratio between the surface area of a sphere with this volume and the surface area of the beta-shape itself is a good measure to classify the sphericity of a protein, especially when the radius of a probe is 3.0 Å. The presented measure is invariant to translation and rotation. Second, the algorithm which evaluates the similarity between the boundaries of two proteins using the beta-shape is introduced. The algorithm iterates the mix-and-match procedure between the two beta-shapes. A heuristic algorithm is introduced to compute a good assessment of similarity quickly because the mix-and-match step is NP-hard.
URI
https://repository.hanyang.ac.kr/handle/20.500.11754/137382http://hanyang.dcollection.net/common/orgView/200000418439
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > INDUSTRIAL ENGINEERING(산업공학과) > Theses (Ph.D.)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE