Fast and accurate protein substructure searching with simulated annealing and GPUs.
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.
Stivala
Alex D
AD
Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia. a.stivala@pgrad.unimelb.edu.au
Stuckey
Peter J
PJ
Wirth
Anthony I
AI
D003196:Computer Graphics; D003198:Computer Simulation; D030562:Databases, Protein; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry*
D011506:Proteins
J Comput Biol. 2004;11(1):27-52
15072687
BMC Bioinformatics. 2007 Dec 10;8:474
18070356
Protein Sci. 2000 Jul;9(7):1274-81
10933492
BMC Bioinformatics. 2010 Jan 18;11 Suppl 1:S46
20122220
Bioinformatics. 2007 Jun 1;23(11):1331-8
17384423
Bioinformatics. 2010 Jan 1;26(1):134-5
19850754
Radiology. 1982 Apr;143(1):29-36
7063747
Biopolymers. 1983 Dec;22(12):2577-637
6667333
Protein Eng. 2000 Aug;13(8):535-43
10964982
Bioinformatics. 2005 Aug 1;21(15):3322-3
15914542
Proteins. 1995 Dec;23(4):566-79
8749853
Biometrics. 1988 Sep;44(3):837-45
3203132
Parallel Comput. 2009 Aug 1;35(8):429-440
20161021
Acta Crystallogr D Biol Crystallogr. 2004 Dec;60(Pt 12 Pt 1):2256-68
15572779
Bioinformatics. 2007 Jul 1;23(13):1631-9
17468121
BMC Res Notes. 2009 May 06;2:73
19416548
BMC Bioinformatics. 2008 Jun 05;9:265
18534022
Bioinformatics. 2000 Jun;16(6):566-7
10980157
Bioinformatics. 2009 Jun 1;25(11):1422-3
19304878
BMC Bioinformatics. 2009 May 19;10:153
19450287
BMC Res Notes. 2008 Jul 11;1:44
18710497
BMC Bioinformatics. 2006 Jan 10;7:10
16403221
Proteins. 1995 Nov;23(3):356-69
8710828
Biochim Biophys Acta. 2004 Nov 29;1695(1-3):73-87
15571810
Bioinformatics. 2005 Apr 15;21(8):1308-10
15604105
Science. 1983 May 13;220(4598):671-80
17813860
BMC Bioinformatics. 2008 Mar 25;9:161
18366735
BMC Bioinformatics. 2008 Mar 26;9 Suppl 2:S10
18387198
BMC Struct Biol. 2005 Sep 15;5:17
16164759
Nucleic Acids Res. 2000 Jan 1;28(1):235-42
10592235
BMC Bioinformatics. 2005 Aug 11;6:202
16095538
Bioinformatics. 2008 Feb 1;24(3):426-7
18174182
Bioinformatics. 2008 Mar 15;24(6):872-3
18227113
Nucleic Acids Res. 2004 Jan 1;32(Database issue):D189-92
14681391
J Comput Chem. 2009 Apr 30;30(6):864-72
19191337
Nucleic Acids Res. 2009 Jul;37(Web Server issue):W539-44
19465386
Bioinformatics. 2009 Jun 1;25(11):1370-6
19369496
Proteins. 2007 Mar 1;66(4):869-76
17206659
Bioinformatics. 2005 Oct 15;21(20):3940-1
16096348
Pac Symp Biocomput. 1996;:300-18
9390240
Proc Natl Acad Sci U S A. 1951 Nov;37(11):729-40
16578412
J Mol Biol. 2002 Jan 25;315(4):887-98
11812155
Bioinformatics. 2003 Nov 22;19(17):2308-10
14630660
Proteins. 2005 Oct 1;61(1):137-51
16049912
Proc Natl Acad Sci U S A. 1951 Apr;37(4):205-11
14816373
J Mol Graph. 1995 Jun;13(3):159-64
7577843
Science. 1996 Aug 2;273(5275):595-603
8662544
Bioinformatics. 1999 Apr;15(4):317-26
10320400
Nucleic Acids Res. 2008 Jan;36(Database issue):D419-25
18000004
J Mol Biol. 1981 Mar 25;147(1):195-7
7265238
Bioinformatics. 2005 May 15;21(10):2537-8
15741246
Protein Sci. 2004 Jan;13(1):278-94
14691242
Genome Biol. 2006;7(5):216
16737556
Protein Eng. 1996 Sep;9(9):727-32
8888137
Bioinformatics. 2010 Feb 15;26(4):574-5
20080504
Bioinformatics. 2008 Mar 1;24(5):645-51
18175768
Curr Opin Struct Biol. 1996 Jun;6(3):377-85
8804824
Pac Symp Biocomput. 2010;:123-32
19908365
Nucleic Acids Res. 2009 Jul;37(Web Server issue):W526-31
19420061
J Mol Biol. 2002 Nov 8;323(5):909-26
12417203
Bioinformatics. 2009 Aug 1;25(15):1937-43
19447788