| With the recent success of the Human Genome Project, one of the main challenges in molecular biology in this post-genomic era is the determination and exploitation of the three-dimensional structure of proteins and their function. The ability for proteins to perform their numerous functions is made possible by the diversity of their three-dimensional structures. Hence, to attack the key problems involved, such as protein folding and docking, geometry and topology become important tools. Despite their essential roles, geometric and topological methods are relatively uncommon in computational biology, partly due to a number of modeling and algorithmic challenges. This thesis describes efficient computational methods for describing and comparing molecular structures by combining both geometric and topological approaches.; In particular, in the first part of the thesis, we study three geometric descriptions: (i) the writhing number of protein backbones, which measures how many times a backbone coils around itself; (ii) the level-of-details representation of protein backbones via simplification, which helps to extract main features of backbones; and (iii) the elevation of molecular surfaces, which we propose to identify geometric features such as protrusions and cavities from protein surfaces. We develop efficient algorithms for computing these descriptions.; The second part of the thesis focuses on molecular shape matching algorithms. By modeling a molecule as the union of balls, we propose algorithms to compute the similarity between two such unions by (variants of) the widely used Hausdorff distance. We also study the protein docking problem, which, from a geometric perspective, can be considered as the problem of searching for configurations with maximum complementarity between two molecular surfaces. Using the feature information computed from the elevation function, we describe an efficient algorithm to find promising initial relative placements of the proteins. |
