| Geometric Hashing is a powerful method for finding common substructures in models. In this thesis, Geometric Hashing is applied to proteins and some algorithm improvements are explored. A review of the Geometric Hashing literature is included, including a detailed description and analysis of the algorithm. The improvements that were made to the algorithm are described in detail. The original algorithm is O(n 4) [21] but by making use of distance constraints, the complexity of the Geometric Hashing algorithm that is presented in this thesis is reduced to O(n2). This does change the applicability of the method slightly, and can affect the accuracy of the method. |
