title: Fast overlapping of protein contact maps by alignment of eigenvectors.
abstract: 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.
authors.affiliation: Department of Computer Science, University of Bologna, Bologna, Italy. dilena@cs.unibo.it
authors.forename: Pietro
authors.initials: P
authors.lastname: Di Lena
authors.forename: Piero
authors.initials: P
authors.lastname: Fariselli
authors.forename: Luciano
authors.initials: L
authors.lastname: Margara
authors.forename: Marco
authors.initials: M
authors.lastname: Vassura
authors.forename: Rita
authors.initials: R
authors.lastname: Casadio
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry* / Q000502:physiology
chemical_list: D011506:Proteins