An Efficient Approach in Comparing Protein Structures using Matrix Alignment Techniques

摘要

In this paper we present a fast and efficient approach for comparing protein structures represented by their contact matrices, generated from the distances between their atoms. The first step is the preprocessing step, when we compute the distance matrix for each protein in the database. These matrices are normalized in the interval [0... 255] and stored as gray images, on different scales. Next, for each two protein structures we compare their respective scaled matrices, for each scale factor, separately. Thus, we avoid the problem of comparing two relatively different sized matrices, which can lead to many ambiguous cases. For the actual comparing of the matrices, a new method is introduced, which combines techniques both of partial dynamic programming - for comparing the rows on the matrices, and a greedy approach - for consolidating the row-row matching results. This method has shown to be fairly more efficient in terms of time and memory complexity and accuracy as well, in comparison with the MatAlign[l] and DALI[2] algorithms, which are guided from the same idea for matrix alignment.