Tableau-based Protein Substructure Search Using Quadratic Programming

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2009 May 20

PMID 19450287

Citations 7

Authors

Alex Stivala

Anthony Wirth

Peter J Stuckey

Affiliations

Soon will be listed here.

Abstract

Background: Searching for proteins that contain similar substructures is an important task in structural biology. The exact solution of most formulations of this problem, including a recently published method based on tableaux, is too slow for practical use in scanning a large database.

Results: We developed an improved method for detecting substructural similarities in proteins using tableaux. Tableaux are compared efficiently by solving the quadratic program (QP) corresponding to the quadratic integer program (QIP) formulation of the extraction of maximally-similar tableaux. We compare the accuracy of the method in classifying protein folds with some existing techniques.

Conclusion: We find that including constraints based on the separation of secondary structure elements increases the accuracy of protein structure search using maximally-similar subtableau extraction, to a level where it has comparable or superior accuracy to existing techniques. We demonstrate that our implementation is able to search a structural database in a matter of hours on a standard PC.

Citing Articles

Efficient and automated large-scale detection of structural relationships in proteins with a flexible aligner.

Gutierrez F, Rodriguez-Valenzuela F, Ibarra I, Devos D, Melo F BMC Bioinformatics. 2016; 17:20.

PMID: 26732380 PMC: 4702403. DOI: 10.1186/s12859-015-0866-8.

Multiple graph regularized protein domain ranking.

Jing-Yan Wang J, Bensmail H, Gao X BMC Bioinformatics. 2012; 13:307.

PMID: 23157331 PMC: 3583823. DOI: 10.1186/1471-2105-13-307.

BetaSearch: a new method for querying β-residue motifs.

Ho H, Gange G, Kuiper M, Ramamohanarao K BMC Res Notes. 2012; 5:391.

PMID: 22839199 PMC: 3532365. DOI: 10.1186/1756-0500-5-391.

ProDis-ContSHC: learning protein dissimilarity measures and hierarchical context coherently for protein-protein comparison in protein database retrieval.

Wang J, Gao X, Wang Q, Li Y BMC Bioinformatics. 2012; 13 Suppl 7:S2.

PMID: 22594999 PMC: 3348016. DOI: 10.1186/1471-2105-13-S7-S2.

Rigid substructure search.

Shirvanyants D, Alexandrova A, Dokholyan N Bioinformatics. 2011; 27(9):1327-9.

PMID: 21460026 PMC: 3138080. DOI: 10.1093/bioinformatics/btr129.

References

Zhenping L, Zhang S, Wang Y, Zhang X, Chen L . Alignment of molecular networks by integer quadratic programming. Bioinformatics. 2007; 23(13):1631-9. DOI: 10.1093/bioinformatics/btm156. View

Kirillova S, Carugo O . Progress in the PRIDE technique for rapidly comparing protein three-dimensional structures. BMC Res Notes. 2008; 1:44. PMC: 2535597. DOI: 10.1186/1756-0500-1-44. View

Caprara A, Carr R, Istrail S, Lancia G, Walenz B . 1001 optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap. J Comput Biol. 2004; 11(1):27-52. DOI: 10.1089/106652704773416876. View

Pelta D, Gonzalez J, Moreno Vega M . A simple and fast heuristic for protein structure comparison. BMC Bioinformatics. 2008; 9:161. PMC: 2335283. DOI: 10.1186/1471-2105-9-161. View

Elliott P, Pei X, Dafforn T, Lomas D . Topography of a 2.0 A structure of alpha1-antitrypsin reveals targets for rational drug design to prevent conformational disease. Protein Sci. 2000; 9(7):1274-81. PMC: 2144685. DOI: 10.1110/ps.9.7.1274. View

Koo B, Jung J, Jung H, Nam H, Kim Y, Yee A . Solution structure of the hypothetical novel-fold protein TA0956 from Thermoplasma acidophilum. Proteins. 2007; 69(2):444-7. DOI: 10.1002/prot.21490. View

Shi S, Zhong Y, Majumdar I, Sri Krishna S, Grishin N . Searching for three-dimensional secondary structural patterns in proteins with ProSMoS. Bioinformatics. 2007; 23(11):1331-8. DOI: 10.1093/bioinformatics/btm121. View

Abyzov A, Ilyin V . A comprehensive analysis of non-sequential alignments between all protein structures. BMC Struct Biol. 2007; 7:78. PMC: 2213659. DOI: 10.1186/1472-6807-7-78. View

Hanley J, McNeil B . The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology. 1982; 143(1):29-36. DOI: 10.1148/radiology.143.1.7063747. View

10.

Jung J, Lee B . Protein structure alignment using environmental profiles. Protein Eng. 2000; 13(8):535-43. DOI: 10.1093/protein/13.8.535. View

11.

Shapiro J, Brutlag D . FoldMiner: structural motif discovery using an improved superposition algorithm. Protein Sci. 2003; 13(1):278-94. PMC: 2286532. DOI: 10.1110/ps.03239404. View

12.

Frishman D, Argos P . Knowledge-based protein secondary structure assignment. Proteins. 1995; 23(4):566-79. DOI: 10.1002/prot.340230412. View

13.

Konagurthu A, Stuckey P, Lesk A . Structural search and retrieval using a tableau representation of protein folding patterns. Bioinformatics. 2008; 24(5):645-51. DOI: 10.1093/bioinformatics/btm641. View

14.

Murzin A, Brenner S, Hubbard T, Chothia C . SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol. 1995; 247(4):536-40. DOI: 10.1006/jmbi.1995.0159. View

15.

Krissinel E, Henrick K . Secondary-structure matching (SSM), a new tool for fast protein structure alignment in three dimensions. Acta Crystallogr D Biol Crystallogr. 2004; 60(Pt 12 Pt 1):2256-68. DOI: 10.1107/S0907444904026460. View

16.

Guerler A, Knapp E . Novel protein folds and their nonsequential structural analogs. Protein Sci. 2008; 17(8):1374-82. PMC: 2492825. DOI: 10.1110/ps.035469.108. View

17.

Casbon J, Crooks G, Saqi M . A high level interface to SCOP and ASTRAL implemented in python. BMC Bioinformatics. 2006; 7:10. PMC: 1373603. DOI: 10.1186/1471-2105-7-10. View

18.

Madej T, Gibrat J, BRYANT S . Threading a database of protein cores. Proteins. 1995; 23(3):356-69. DOI: 10.1002/prot.340230309. View

19.

Sri Krishna S, Grishin N . Structural drift: a possible path to protein fold change. Bioinformatics. 2004; 21(8):1308-10. DOI: 10.1093/bioinformatics/bti227. View

20.

Sam V, Tai C, Garnier J, Gibrat J, Lee B, Munson P . ROC and confusion analysis of structure comparison methods identify the main causes of divergence from manual protein classification. BMC Bioinformatics. 2006; 7:206. PMC: 1513609. DOI: 10.1186/1471-2105-7-206. View