title: Fast and accurate non-sequential protein structure alignment using a new asymmetric linear sum assignment heuristic.
abstract: BACKGROUND
  The three dimensional tertiary structure of a protein at near atomic level resolution provides insight alluding to its function and evolution. As protein structure decides its functionality, similarity in structure usually implies similarity in function. As such, structure alignment techniques are often useful in the classifications of protein function. Given the rapidly growing rate of new, experimentally determined structures being made available from repositories such as the Protein Data Bank, fast and accurate computational structure comparison tools are required. This paper presents SPalignNS, a non-sequential protein structure alignment tool using a novel asymmetrical greedy search technique.
  
  
  RESULTS
  The performance of SPalignNS was evaluated against existing sequential and non-sequential structure alignment methods by performing trials with commonly used datasets. These benchmark datasets used to gauge alignment accuracy include (i) 9538 pairwise alignments implied by the HOMSTRAD database of homologous proteins; (ii) a subset of 64 difficult alignments from set (i) that have low structure similarity; (iii) 199 pairwise alignments of proteins with similar structure but different topology; and (iv) a subset of 20 pairwise alignments from the RIPC set. SPalignNS is shown to achieve greater alignment accuracy (lower or comparable root-mean squared distance with increased structure overlap coverage) for all datasets, and the highest agreement with reference alignments from the challenging dataset (iv) above, when compared with both sequentially constrained alignments and other non-sequential alignments.
  
  
  METHODS
  SPalignNS was implemented in C++. The source code, binary executable, and a web server version is freely available at: http://sparks-lab.org
  
  
  BACKGROUND
  yaoqi.zhou@griffith.edu.au.
authors.affiliation: School of ICT, Griffith University, Gold Coast, QLD 4222, Australia.
authors.forename: Peter
authors.initials: P
authors.lastname: Brown
authors.affiliation: School of ICT, Griffith University, Gold Coast, QLD 4222, Australia.
authors.forename: Wayne
authors.initials: W
authors.lastname: Pullan
authors.affiliation: Institute for Glycomics, Griffith University, Gold Coast, QLD 4222, Australia.
authors.forename: Yuedong
authors.initials: Y
authors.lastname: Yang
authors.affiliation: School of ICT, Griffith University, Gold Coast, QLD 4222, Australia Institute for Glycomics, Griffith University, Gold Coast, QLD 4222, Australia.
authors.forename: Yaoqi
authors.initials: Y
authors.lastname: Zhou
mesh_terms: D030562:Databases, Protein; D000066506:Heuristics; D008958:Models, Molecular; D011506:Proteins / Q000737:chemistry; D016415:Sequence Alignment; D012984:Software; D040681:Structural Homology, Protein
chemical_list: D011506:Proteins