title: Fast and accurate protein substructure searching with simulated annealing and GPUs.
abstract: BACKGROUND
  Searching a database of protein structures for matches to a query structure, or occurrences of a structural motif, is an important task in structural biology and bioinformatics. While there are many existing methods for structural similarity searching, faster and more accurate approaches are still required, and few current methods are capable of substructure (motif) searching.
  
  
  RESULTS
  We developed an improved heuristic for tableau-based protein structure and substructure searching using simulated annealing, that is as fast or faster and comparable in accuracy, with some widely used existing methods. Furthermore, we created a parallel implementation on a modern graphics processing unit (GPU).
  
  
  CONCLUSIONS
  The GPU implementation achieves up to 34 times speedup over the CPU implementation of tableau-based structure search with simulated annealing, making it one of the fastest available methods. To the best of our knowledge, this is the first application of a GPU to the protein structural search problem.
authors.affiliation: Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia. a.stivala@pgrad.unimelb.edu.au
authors.forename: Alex D
authors.initials: AD
authors.lastname: Stivala
authors.forename: Peter J
authors.initials: PJ
authors.lastname: Stuckey
authors.forename: Anthony I
authors.initials: AI
authors.lastname: Wirth
mesh_terms: D003196:Computer Graphics; D003198:Computer Simulation; D030562:Databases, Protein; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins
references.citation: J Comput Biol. 2004;11(1):27-52
references.pmid: 15072687
references.citation: BMC Bioinformatics. 2007 Dec 10;8:474
references.pmid: 18070356
references.citation: Protein Sci. 2000 Jul;9(7):1274-81
references.pmid: 10933492
references.citation: BMC Bioinformatics. 2010 Jan 18;11 Suppl 1:S46
references.pmid: 20122220
references.citation: Bioinformatics. 2007 Jun 1;23(11):1331-8
references.pmid: 17384423
references.citation: Bioinformatics. 2010 Jan 1;26(1):134-5
references.pmid: 19850754
references.citation: Radiology. 1982 Apr;143(1):29-36
references.pmid: 7063747
references.citation: Biopolymers. 1983 Dec;22(12):2577-637
references.pmid: 6667333
references.citation: Protein Eng. 2000 Aug;13(8):535-43
references.pmid: 10964982
references.citation: Bioinformatics. 2005 Aug 1;21(15):3322-3
references.pmid: 15914542
references.citation: Proteins. 1995 Dec;23(4):566-79
references.pmid: 8749853
references.citation: Biometrics. 1988 Sep;44(3):837-45
references.pmid: 3203132
references.citation: Parallel Comput. 2009 Aug 1;35(8):429-440
references.pmid: 20161021
references.citation: Acta Crystallogr D Biol Crystallogr. 2004 Dec;60(Pt 12 Pt 1):2256-68
references.pmid: 15572779
references.citation: Bioinformatics. 2007 Jul 1;23(13):1631-9
references.pmid: 17468121
references.citation: BMC Res Notes. 2009 May 06;2:73
references.pmid: 19416548
references.citation: BMC Bioinformatics. 2008 Jun 05;9:265
references.pmid: 18534022
references.citation: Bioinformatics. 2000 Jun;16(6):566-7
references.pmid: 10980157
references.citation: Bioinformatics. 2009 Jun 1;25(11):1422-3
references.pmid: 19304878
references.citation: BMC Bioinformatics. 2009 May 19;10:153
references.pmid: 19450287
references.citation: BMC Res Notes. 2008 Jul 11;1:44
references.pmid: 18710497
references.citation: BMC Bioinformatics. 2006 Jan 10;7:10
references.pmid: 16403221
references.citation: Proteins. 1995 Nov;23(3):356-69
references.pmid: 8710828
references.citation: Biochim Biophys Acta. 2004 Nov 29;1695(1-3):73-87
references.pmid: 15571810
references.citation: Bioinformatics. 2005 Apr 15;21(8):1308-10
references.pmid: 15604105
references.citation: Science. 1983 May 13;220(4598):671-80
references.pmid: 17813860
references.citation: BMC Bioinformatics. 2008 Mar 25;9:161
references.pmid: 18366735
references.citation: BMC Bioinformatics. 2008 Mar 26;9 Suppl 2:S10
references.pmid: 18387198
references.citation: BMC Struct Biol. 2005 Sep 15;5:17
references.pmid: 16164759
references.citation: Nucleic Acids Res. 2000 Jan 1;28(1):235-42
references.pmid: 10592235
references.citation: BMC Bioinformatics. 2005 Aug 11;6:202
references.pmid: 16095538
references.citation: Bioinformatics. 2008 Feb 1;24(3):426-7
references.pmid: 18174182
references.citation: Bioinformatics. 2008 Mar 15;24(6):872-3
references.pmid: 18227113
references.citation: Nucleic Acids Res. 2004 Jan 1;32(Database issue):D189-92
references.pmid: 14681391
references.citation: J Comput Chem. 2009 Apr 30;30(6):864-72
references.pmid: 19191337
references.citation: Nucleic Acids Res. 2009 Jul;37(Web Server issue):W539-44
references.pmid: 19465386
references.citation: Bioinformatics. 2009 Jun 1;25(11):1370-6
references.pmid: 19369496
references.citation: Proteins. 2007 Mar 1;66(4):869-76
references.pmid: 17206659
references.citation: Bioinformatics. 2005 Oct 15;21(20):3940-1
references.pmid: 16096348
references.citation: Pac Symp Biocomput. 1996;:300-18
references.pmid: 9390240
references.citation: Proc Natl Acad Sci U S A. 1951 Nov;37(11):729-40
references.pmid: 16578412
references.citation: J Mol Biol. 2002 Jan 25;315(4):887-98
references.pmid: 11812155
references.citation: Bioinformatics. 2003 Nov 22;19(17):2308-10
references.pmid: 14630660
references.citation: Proteins. 2005 Oct 1;61(1):137-51
references.pmid: 16049912
references.citation: Proc Natl Acad Sci U S A. 1951 Apr;37(4):205-11
references.pmid: 14816373
references.citation: J Mol Graph. 1995 Jun;13(3):159-64
references.pmid: 7577843
references.citation: Science. 1996 Aug 2;273(5275):595-603
references.pmid: 8662544
references.citation: Bioinformatics. 1999 Apr;15(4):317-26
references.pmid: 10320400
references.citation: Nucleic Acids Res. 2008 Jan;36(Database issue):D419-25
references.pmid: 18000004
references.citation: J Mol Biol. 1981 Mar 25;147(1):195-7
references.pmid: 7265238
references.citation: Bioinformatics. 2005 May 15;21(10):2537-8
references.pmid: 15741246
references.citation: Protein Sci. 2004 Jan;13(1):278-94
references.pmid: 14691242
references.citation: Genome Biol. 2006;7(5):216
references.pmid: 16737556
references.citation: Protein Eng. 1996 Sep;9(9):727-32
references.pmid: 8888137
references.citation: Bioinformatics. 2010 Feb 15;26(4):574-5
references.pmid: 20080504
references.citation: Bioinformatics. 2008 Mar 1;24(5):645-51
references.pmid: 18175768
references.citation: Curr Opin Struct Biol. 1996 Jun;6(3):377-85
references.pmid: 8804824
references.citation: Pac Symp Biocomput. 2010;:123-32
references.pmid: 19908365
references.citation: Nucleic Acids Res. 2009 Jul;37(Web Server issue):W526-31
references.pmid: 19420061
references.citation: J Mol Biol. 2002 Nov 8;323(5):909-26
references.pmid: 12417203
references.citation: Bioinformatics. 2009 Aug 1;25(15):1937-43
references.pmid: 19447788