Recent developments in computer science enable algorithms previously perceived as too time-consuming to now be efficiently used for applications in bioinformatics and life sciences. This work focuses on proteins and their structures, protein structure similarity searching at main representation levels and various techniques that can be used to accelerate similarity searches. Divided into four parts, the first part provides a formal model of 3D protein structures for functional genomics, comparative bioinformatics and molecular modeling. The second part focuses on the use of multithreading for efficient approximate searching on protein secondary structures. The third and fourth parts concentrate on finding 3D protein structure similarities with the support of GPUs and cloud computing. Parts three and four both describe the acceleration of different methods. The text will be of interest to researchers and software developers working in the field of structural bioinformatics and biomedical databases.