LISA: A fast filtering algorithm for structural alignment

Protein - Protein Interactions (PPI) cause vital processes such as growing, division or maintenance of a cell. It is an important topic in order to understand the functioning of any cell with itself and others. Even though the most reliable techniques are experimental for investigating the properties of different structures, numerical methods are much faster with negligible error. Nevertheless, predictions of PPI needs improvements in order to derive more accurate results faster. In this thesis, we are implementing a two-step hashing algorithm in order to increase the speed of prediction of PPI structures. In the first part, a large number of interfaces are classified by their different properties such as bond angles, dihedral angles and distances between Carbon Alpha (CA) atoms. For each non-consecutive residue that has the distance of 4 $\AA$ to 13 $\AA$, between CA atoms,we are calculating necessary angles and distances with selected CA atoms and their consecutive neighbors. Then, we are classifying fragments of interfaces with similar properties in the first phase of the algorithm by using a hash table. In the second phase, we are comparing a given protein using the same properties that calculated for templates, and score them by their similarity. Proposed algorithm is developed for filtering the dissimilar interfaces and limiting the possible number of interfaces that can be used in Template-Based PPI prediction protocols. In addition, it is useful for reducing the computation time of any structural alignment algorithm to find input templates for a docking algorithm by returning a filtered subset from a given template dataset.