Fast overlapping of protein contact maps by alignment of eigenvectors.
BACKGROUND
Searching for structural similarity is a key issue of protein functional annotation. The maximum contact map overlap (CMO) is one of the possible measures of protein structure similarity. Exact and approximate methods known to optimize the CMO are computationally expensive and this hampers their applicability to large-scale comparison of protein structures.


RESULTS
In this article, we describe a heuristic algorithm (Al-Eigen) for finding a solution to the CMO problem. Our approach relies on the approximation of contact maps by eigendecomposition. We obtain good overlaps of two contact maps by computing the optimal global alignment of few principal eigenvectors. Our algorithm is simple, fast and its running time is independent of the amount of contacts in the map. Experimental testing indicates that the algorithm is comparable to exact CMO methods in terms of the overlap quality, to structural alignment methods in terms of structure similarity detection and it is fast enough to be suited for large-scale comparison of protein structures. Furthermore, our preliminary tests indicates that it is quite robust to noise, which makes it suitable for structural similarity detection also for noisy and incomplete contact maps.


BACKGROUND
Available at http://bioinformatics.cs.unibo.it/Al-Eigen.
Di Lena
Pietro
P
Department of Computer Science, University of Bologna, Bologna, Italy. dilena@cs.unibo.it
Fariselli
Piero
P
Margara
Luciano
L
Vassura
Marco
M
Casadio
Rita
R
D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry* / Q000502:physiology
D011506:Proteins