Tableau-based protein substructure search using quadratic programming
Related Experiment Video
Updated: Jun 23, 2026

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
Published on: July 25, 2013
Alex Stivala1, Anthony Wirth, Peter J Stuckey
1Department of Computer Science and Software Engineering, The University of Melbourne, Victoria, Australia. a.stivala@pgrad.unimelb.edu.au
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.
Related Concept Videos
Quadratic Models
Protein Organization
The primary structure of a protein is its amino acid sequence.
Quadratic Equations
Protein and Protein Structures
A protein's shape is critical to its function. For example, an enzyme can...
Protein and Protein Structure
A protein's shape is critical to its function. For example, an enzyme can...
Protein Complexes with Interchangeable Parts
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...

