title: Towards optimal alignment of protein structure distance matrices.
abstract: BACKGROUND
  Structural alignments of proteins are important for identification of structural similarities, homology detection and functional annotation. The structural alignment problem is well studied and computationally difficult. Many different scoring schemes for structural similarity as well as many algorithms for finding high-scoring alignments have been proposed. Algorithms using contact map overlap (CMO) as scoring function are currently the only practical algorithms able to compute provably optimal alignments.
  
  
  RESULTS
  We propose a new mathematical model for the alignment of inter-residue distance matrices, building upon previous work on maximum CMO. Our model includes all elements needed to emulate various scoring schemes for the alignment of protein distance matrices. The algorithm that we use to compute alignments is practical only for sparse distance matrices. Therefore, we propose a more effective scoring function, which uses a distance threshold and only positive structural scores. We show that even under these restrictions our approach is in terms of alignment accuracy competitive with state-of-the-art structural alignment algorithms, whereas it additionally either proves the optimality of an alignment or returns bounds on the optimal score. Our novel method is freely available and constitutes an important promising step towards truly provably optimal structural alignments of proteins.
  
  
  BACKGROUND
  An executable of our program PAUL is available at http://planet-lisa.net/.
authors.affiliation: CWI, Life Sciences Group, Amsterdam, The Netherlands. Inken.Wohlers@cwi.nl
authors.forename: Inken
authors.initials: I
authors.lastname: Wohlers
authors.forename: Francisco S
authors.initials: FS
authors.lastname: Domingues
authors.forename: Gunnar W
authors.initials: GW
authors.lastname: Klau
mesh_terms: D000465:Algorithms; D006801:Humans; D008956:Models, Chemical; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins