BACKGROUND
finding structures in a database which contain a substructure that is similar to a query structure or structural motif is an important technique in analyzing protein structure, function, and evolution.
there are many existing methods for finding structurally similar proteins which take diverse approaches, such as: structural alignment at the level of residues or backbone atoms  <cit>  or  secondary structure elements  <cit> , purely topological matching  <cit> , and probabilistic approaches  <cit> .
detailed structural alignment, however, although capable of great accuracy, is often slow  <cit> , and therefore impractical for searching entire databases of the size of scop  <cit>  or the pdb  <cit> .
the tops-based method  <cit>  provides structural motif searches, but by operating purely on topology it "ignores other important spatial properties" .
non-alignment approaches, such as pride  <cit> , can be extremely fast, but not as accurate as alignment-based approaches  <cit> , and provide only a matching score, not an alignment or a coarse-grained or seed alignment for further refinement.
two recent approaches, prosmos  <cit>  and tableausearch  <cit> , use spatial interactions between secondary structure elements  to find common structures.
prosmos constructs a "meta-matrix" of sses and the interactions between them, and finds all possible submatrices in a database meta-matrix that match the query meta-matrix.
tableausearch constructs tableaux  <cit> , which represent relative orientations of sses, and finds substructural matches by extracting maximally-similar subtableaux between the query tableau and a database tableau.
in the exact  technique, this problem is expressed as a quadratic integer program  or integer linear program   <cit>  and solved exactly using ilog cplex  <cit> .
both prosmos and the exact tableau search formulation allow substructures to be found within structures.
they also allow non-linear matchings, that is, sets of correspondences between sses in which the sequential order of corresponding sses is not preserved.
such non-linear matchings have recently been shown to be significantly more widespread than had previously been thought  <cit> , and are therefore of considerable interest.
the two most similar methods to tableau matching are perhaps lock  <cit> , and its newer version lock  <dig>  <cit> , and prosmos.
lock and lock  <dig> also match sse vectors between structures, but use a more complex set of seven scoring functions, both orientation dependent and orientation independent, and use iterative dynamic programming requiring parameters for each of the scoring functions  <cit> .
in contrast, the tableau matching formulation is simpler and more elegant, although to obtain higher accuracy we extend it with a distance difference constraint that requires a parameter.
prosmos, although it is similar to tableau matching in its use of sse orientations, takes quite a different approach from most existing structural search methods in that, rather than taking a structure  definition as a query, the query meta-matrix is constructed manually  by the user.
this is clearly useful for finding user-specified motifs in a database of structures, but creates challenges in assessing the performance of the method since the results are so dependent on the user-specified query.
prosmos, in contrast to our method, returns a list of hits to the query structure, rather than a matching score for each structure in the database.
this is often simpler for the user, but it does have the disadvantage that finding more  hits requires editing the query meta-matrix, which can be quite difficult to calibrate.
returning a score for each database structure means that adjusting the sensitivity or specificity required is simply a matter of varying the cutoff score for a match to be considered significant.
an advantage of the maximally-similar subtableaux formulation is that it allows the discovery of similar substructures within two structures, without requiring that the two structures are themselves similar as a whole, or that one of the structures must match as a whole some substructure within the other structure.
we may choose to use one structure as a "query" motif, usually a small well-defined structural folding pattern, and find structures that contain this entire motif as a substructure, but it is also possible to find common substructures in two unrelated folds.
however, the rigorous tableau searching method is too slow for a full database search, and so konagurthu et al.
<cit>  introduce tableausearch.
this method approximates the exact solution using an alignment-like approach  <cit> , with two phases of dynamic programming.
tableausearch is extremely fast, but loses the rigorous theoretical justification and is not as accurate as the exact method.
it is also inherently sequential, thereby losing the ability to find non-linear structural matchings, and, at least partly, loses the ability to find substructural  rather than full structure  matches.
this may be possible, however, by removing end gap penalties  <cit> .
here we present a method, based on the exact tableaux matching formulation  <cit>  and recent work in alignment of molecular networks  <cit> , that allows searches for occurrences of a query structure as substructures of structures in a database such as scop in practical time, allows non-linear matchings, and is able to provide a set of correspondences between sses.
RESULTS
we evaluate the accuracy of our qp tableau matching algorithm as a method for determining the fold of a structure, using scop as the truth.
the tradeoff between sensitivity and specificity for such a classification task can be shown as a receiver operating characteristic  curve  <cit> .
roc curves for several different structural queries are shown in figures  <dig> and  <dig>  figure  <dig> shows results obtained using only tableau information, while figure  <dig> shows results obtained using tableau and distance information .
the area under the roc curve  for each of these curves is shown in table  <dig>  incorporating distance information results in consistently higher auc values without significantly affecting the elapsed time.
area under roc curve  and time taken for searches for several structural folding patterns against the astral scop 95% sequence identity non-redundant database consisting of  <dig> domains using discrete tableaux, both with and without incorporating sse distance information.
times  reported are elapsed times using the sparse matrix  implementation on an intel xeon  <dig>  ghz machine with  <dig> gb memory running linux.
the table is sorted by query size .
we find that the best-performing variation of our method, using the discrete tableau encoding rather than numeric Ω matrices, and incorporating distance information, has an auc of  <dig>  averaged over the eight queries in table  <dig>
we can see in table  <dig> that the ferredoxin fold query  performs significantly worse than the others.
we examined the results from this query and found that a large number of false negatives occur .
examining some of these false negatives in detail, we find that it is often due to dssp  <cit> , which we use to define sses, not defining some of the sses required to match the query structure .
although we have the capability of using stride  <cit>  rather than dssp, the results are often similar .
this is a shortcoming of any method that depends on sse definitions, although prosmos solves it to some degree by using palsse  <cit> , a secondary structure assignment method that assigns many more residues to sses precisely in order to avoid this problem  <cit> .
false negatives can also occur independently of the sse definition algorithm, if a structure does not have some sses not considered essential to the fold according to scop  and/or sufficiently different in their orientation that tableau matching does not assign them a high score.
an example of this is d1q8ba_, which does not have all the helices in the query structure, and some which it does include have rather different orientations from those in the query, but it is nevertheless classified as a member of the ferredoxin-like fold.
for a larger-scale test, we used a set of  <dig> queries chosen from the astral scop  <dig>  95% sequence identity non-redundant data set  <cit> .
the queries were chosen so that each class  is represented in the query set in the same ratio as it is in the database.
the overall auc for different normalizations  and different methods are shown in table  <dig>  it can be seen that normalization norm <dig> is the best normalization function for the tableau search methods, and that sheba  <cit>  is the best performing method, followed by our method, then vast  <cit> , and lastly tableausearch  <cit>  and tops.
figure  <dig> shows the roc curves for the different methods .
it can be seen that the curve for sheba lies above that for vast at every point, consistent with the results for all-against-all comparisons in the astral scop  <dig>  40% sequence identity non-redundant data set reported in  <cit> .
the curve for our method lies between the two at low false positive rates, but crosses over the sheba curve at a false positive rate of approximately  <dig> , indicating it has a slightly higher sensitivity at high false positive rates than sheba.
sheba, however, is more sensitive at low false positive rates, a generally more useful attribute.
area under roc curve  for the  <dig> query set against the astral scop 95% sequence identity non-redundant database consisting of  <dig> domains, for different methods and normalizations.
note that only the tableau search methods  and tableausearch) require normalization, as vast, sheba and tops report normalized scores themselves and so do not require an external normalization step to combine results for different queries.
the table is ordered by decreasing auc.
in terms of elapsed time , tableausearch is by far the fastest method.
on our system, it has a total elapsed time for the  <dig> query set of only  <dig> hour  <dig> minutes, compared to  <dig> hours for vast,  <dig> hours for sheba, and  <dig> hours for our method.
large scale comparisons with the exact solution of the qip or ilp with cplex are not practical, as a single comparison takes at least several seconds and can take up to several days, and in some cases exhausts the virtual memory of our machine.
comparison with max-cmo heuristic
maximum contact map overlap  is a formulation of the problem of finding the similarity of two protein structures.
max-cmo uses the contact map representation of proteins, in which a protein with n residues is represented as a square symmetric matrix cn × n where cij =  <dig> when the distance between residues i and j is less than some threshold, and cij =  <dig> otherwise.
typically this distance is defined as the cα distance, and the threshold is for example  <dig> Å. the max-cmo problem is then to find a  alignment of residues that maximizes the overlap between two contact maps.
the value  of the alignment is the number of contacts in one protein whose residues are aligned with residues that are also in contact in the other protein  <cit> .
max-cmo is an np-hard problem, and methods for solving it exactly, by such techniques as integer programming with lagrangian relaxation  <cit>  or branch-and-bound  <cit>  can be impractically slow.
therefore, heuristic approaches are useful, and recently a variable neighborhood search  algorithm for approximating max-cmo has been published, with an analysis of its effectiveness in ranking protein similarity  <cit> .
here we compare the performance of the qp formulation of maximally-similar subtableaux extraction with the vns heuristic for max-cmo of  <cit> .
we should perhaps discount any superiority in the performance of the tableau search method at the class level, as this level of classification in the cath hierarchy indicates only the percentage of α-helices and β-strands in the domain  <cit> .
since tableaux are based on sses  we could trivially obtain good classification performance at this level just from the dssp classification, while max-cmo uses only residue contact information, and so must score protein similarity at this high level without having sses defined by an existing method.
ignoring the class level comparisons therefore, we find that qp tableau search has significantly superior accuracy compared to msvns <dig> on the fischer data set, and similar accuracy to msvns <dig> on the nh3d data set.
for the fischer data set, msvns <dig> took  <dig> hours while the sparse matrix  implementation of qp tableau search took  <dig> hours on a pc with an intel core  <dig> duo processor and  <dig> gb of memory running 32-bit linux.
for the nh3d data set, msvns <dig> took  <dig> hours while qp tableau search took  <dig> hours.
examples
substructure queries need not be entire structures themselves.
in order to illustrate the ability of our method to find substructural matches, we chose the b/c sheet of the the canonical active serpin, α1-antitrypsin, pdb id 1qlp <cit>  as a query tableau.
figure  <dig> shows the substructure represented by this query.
of the total  <dig> structures in our database classified by scop as belonging to the serpin fold,  <dig> are matched as the top  <dig> hits .
one, however, d1m <dig> , is only at rank  <dig> in the sorted hit list.
this is the cleaved form of the serpin, but this does not account for the failure to detect its similarity, as, for example, d1jjo.
<dig> is also the cleaved form and it is at rank  <dig> in the sorted hit list.
inspection of the tableaux for the b/c sheets of these two serpins shows that while that for d1jjo.
<dig> is visibly similar to the query tableau, the relative angles of the strands in the b/c sheet of d1m <dig>  are different enough from the query that the tableau is no longer sufficiently similar to find the correct matching of the two sheets.
using the entire serpin structure d1qlpa_ as the query, however, results in all  <dig> serpins as the top  <dig> hits.
substructure search
evaluated as a substructure  query, the β-grasp query  using the discrete tableau encoding has an auc of  <dig> .
since the data set used as the gold standard in this case is that defined by prosmos  <cit> , that method by definition has an auc of  <dig>  on this query.
the number of superfamilies in the astral scop 95% sequence identity nonredundant database found for the eight query structures by prosmos , ssm , tops  and our method, qp tableau search .
prosmos and ssm return a list of significant hits, so the number of superfamilies found by these hits is shown.
other methods return scores for all database structures, and the number of superfamilies in the hits with a z-score ≥  <dig>  are shown.
the r column is the number of superfamilies, from the combined list of those found by all methods, in which the relevant query pattern or fold description is explicitly mentioned in the scop structure description.
the ratio columns show the number of superfamilies in the r column found by the specified method.
therefore the prosmos results reflect not only the performance of prosmos, but also our construction of the relevant query matrices.
we note that our results here differ significantly from those in table  <dig> of  <cit> : our method of constructing this table is similar, but not identical, to that of  <cit> , we have used slightly different queries  and different versions of the software and a different database have been used.
consistently with  <cit> , ssm finds the least number of matches.
in our results, however, prosmos does not always return the greatest number of matches: sometimes tops does, since we are using a version of tops that computes scores for all matches, rather than the precomputed "classic" structure patterns.
tops also tends to have more false positives than prosmos or our method, that is, superfamilies found by tops that are not considered by the scop descriptions to contain the fold in question.
this is consistent with tops being a purely topological method, which does not take account of other structural properties.
sometimes this also results in tops finding true positives which the other methods do not, for example when using the ferredoxin query, only tops finds the monooxygenase  regulatory protein superfamily, d. <dig> , which scop describes as having "some topological similarity to the ferredoxin-like fold".
scop also notes in the family description for d. <dig> .
<dig> that "the solution structure determinations disagree in the relative orientations of two motifs", so topological similarity without taking into account more detailed structural similarity  is a more appropriate method to find matches to this structure, reflected in the relatively better performance of tops, and the previously discussed poor performance of our method on this query.
in order to better examine the unique properties of each method, table  <dig> shows, for each method, the number of superfamilies found only by that method, and the number of these for which scop explicitly mentions the relevant query pattern.
ssm finds no hits that the other methods do not, and tops usually finds the most.
for the ferredoxin query, we can see that tops finds a large number of true positives  that the other methods do not; our method finds  <dig> and prosmos  <dig>  however, on the tim-barrel query, tops finds  <dig> unique hits, none of which are considered to contain the tim-barrel motif according to scop, while our method finds  <dig> unique hits that all contain the tim-barrel motif according to scop.
with the exception of ssm, we can see that each method finds some unique true matches that the others do not.
as an example of true positive hits that only our method finds, consider the jelly-roll query.
only qp tableau search finds the viral protein domain superfamily b.
<dig> , and the membrane penetration protein μ <dig> superfamily e. <dig> , both of which are described by scop as containing a jelly-roll motif.
the number of superfamilies in the astral scop 95% sequence identity nonredundant database found by only that method for the eight query structures by prosmos , ssm , tops  and our method, qp tableau search .
the r column is the number of superfamilies, from the combined list of those found uniquely by each method, in which the relevant query pattern or fold description is explicitly mentioned in the scop structure description.
the ratio columns show the number of superfamilies in the r column represented by the superfamilies found only by the specified method.
an interesting example is the ferredoxin fold, where the performance of our method as a structural search method is relatively poor.
however, as a substructure search technique, some true positives are found only by our method.
only qp tableau search finds the peptide methionine sulfoxide reductase superfamily d. <dig> , the ccmk-like superfamily d. <dig> , and the release factor superfamily e. <dig> .
the first two are members of the ferredoxin-like fold but d. <dig>  is described by scop as having the common fold "elaborated with additional secondary structures".
the release factor superfamily  is described by scop as having  <dig> domains, one of which is a ferredoxin-like fold.
it is important to note several caveats in interpreting table  <dig> and table  <dig>  first, as already discussed, prosmos queries were manually constructed, which is not the case for the other methods.
second, prosmos and ssm return a set of hits for a query, whereas the other methods return a matching score between the query and every database structure.
hence, in order to construct the tables, a cutoff score needs to be chosen .
the values in the tables are therefore very sensitive to the method used to choose the cutoff score: we could find arbitrarily many superfamilies simply by decreasing the value at which a score is considered a hit.
third, as discussed in  <cit> , the lack of explicit mention of a structure in the scop description does not necessarily mean the structural motif is absent.
non-linear matchings
in order to verify the capability of our method to find non-linear matchings when the sse ordering constraint is disabled, we first use an artificial test.
five different random permutations of the eight tableaux  previously discussed and shown in table  <dig> were generated.
these were then used as queries, and the auc for each calculated in the same way as for table  <dig>  the average auc for each fold over its five permutations is shown in table  <dig>  from this table we can see that, despite the tableaux being permuted so that the sses in the query are no longer in the same sequence as in the database structures, the structures are still matched, albeit sometimes with a lower auc than for the correctly ordered sses with the ordering constraint enabled.
as a demonstration of a real case of a non-linear matching, we use as the query the hypothetical novel-fold protein ta <dig>   <cit>  which was recently found to have several non-linear alignments  <cit> .
when ordering constraints are enabled, our method finds no significant matches in the astral scop  <dig>  95% sequence identity non-redundant database.
however, when ordering constraints are disabled, some high-scoring hits are found, in particular the top-scoring hit is to d1kb9b <dig>  cytochrome bc <dig> core subunit  <dig>  the superposition of these two structures is shown in figure  <dig>  this is different from the result reported by guerler and knapp  <cit>  using gangsta+  <cit> , who find that pdb identifier 1go <dig> is the most similar structure .
therefore, we used the gangsta+ webserver  <cit>  with 2jmk as the query, and found that after setting the selection criteria to require at least  <dig> matching sses, d1kb9b <dig> is the fourth most significant hit, demonstrating that gangsta+ is in agreement with our method that this non-linear matching is significant.
CONCLUSIONS
we have introduced an improved method of searching for protein structures with similar folds using tableaux, incorporating constraints on the distances between sses to improve accuracy.
this method is capable of finding either matches of an entire structure to the query, or matches where the query is a substructure of a larger structure.
it is capable of finding non-linear matchings, where structurally equivalent parts do not have the same relative positions in the sequences of the two proteins.
it also provides a set of corresponding sses, useful for manual validation of the result or as a seed for a more detailed structural alignment.
in assessing their vns heuristic for max-cmo, pelta et al.
<cit>  ask whether it is necessary to solve max-cmo exactly in order to perform structure classification, and conclude that it is not: the heuristic solution is sufficient.
we have shown that, consistent with previous work using the tableau representation of protein folds  <cit> , the much more coarse-grained  tableau representation is sufficient to accurately represent protein folds and perform structure classification.
specifically, we have shown that the efficient approximation of maximally-similar subtableaux extraction by relaxed quadratic programming is able to consistently classify folds at least as accurately as the vns heuristic for max-cmo.
in addition, our implementation is able to do so in less time than the msvns <dig> implementation described by  <cit> .
we have demonstrated that the accuracy of our technique assessed as a protein fold recognition method compares favorably with some existing methods, and that it is fast enough to scan protein structure databases in a practical time, unlike the exact solution using cplex.
it is, however, not as fast as some existing methods such as sheba and vast, and the tableausearch dynamic programming approximation introduced by  <cit>  is faster still.
these methods, however, cannot be used to find substructures or non-linear matchings.
we have also demonstrated the use of our technique as a method for searching for substructures in protein structures, and compared it with some existing techniques, including prosmos.
complications in objectively assessing the performance of these methods make definite conclusions in this area difficult: we can perhaps say at most that each method has different enough properties that they are all capable of finding unique hits that others miss.
a structural biologist searching for matches to a motif or substructure, then, would do well to employ several of these methods rather than relying on just one.
as noted by li et al.
<cit> , further theoretical work to find tight sufficient conditions for the qp to have an integer solution is required, although empirically an integer solution is almost always found.

 finding structures in a database which contain a substructure that is similar to a query structure or structural motif is an important technique in analyzing protein structure, function, and evolution. there are many existing methods for finding structurally similar proteins which take diverse approaches, such as: structural alignment at the level of residues or backbone atoms or secondary structure elements, purely topological matching, and probabilistic approaches. detailed structural alignment, however, although capable of great accuracy, is often slow, and therefore impractical for searching entire databases of the size of scop or the pdb. the tops-based method provides structural motif searches, but by operating purely on topology it "ignores other important spatial properties". non-alignment approaches, such as pride, can be extremely fast, but not as accurate as alignment-based approaches, and provide only a matching score, not an alignment or a coarse-grained or seed alignment for further refinement. two recent approaches, prosmos and tableausearch, use spatial interactions between secondary structure elements to find common structures. prosmos constructs a "meta-matrix" of sses and the interactions between them, and finds all possible submatrices in a database meta-matrix that match the query meta-matrix. tableausearch constructs tableaux, which represent relative orientations of sses, and finds substructural matches by extracting maximally-similar subtableaux between the query tableau and a database tableau. in the exact technique, this problem is expressed as a quadratic integer program or integer linear program and solved exactly using ilog cplex. both prosmos and the exact tableau search formulation allow substructures to be found within structures. they also allow non-linear matchings, that is, sets of correspondences between sses in which the sequential order of corresponding sses is not preserved. such non-linear matchings have recently been shown to be significantly more widespread than had previously been thought, and are therefore of considerable interest. the two most similar methods to tableau matching are perhaps lock, and its newer version lock, and prosmos. lock and lock also match sse vectors between structures, but use a more complex set of seven scoring functions, both orientation dependent and orientation independent, and use iterative dynamic programming requiring parameters for each of the scoring functions. in contrast, the tableau matching formulation is simpler and more elegant, although to obtain higher accuracy we extend it with a distance difference constraint that requires a parameter. prosmos, although it is similar to tableau matching in its use of sse orientations, takes quite a different approach from most existing structural search methods in that, rather than taking a structure definition as a query, the query meta-matrix is constructed manually by the user. this is clearly useful for finding user-specified motifs in a database of structures, but creates challenges in assessing the performance of the method since the results are so dependent on the user-specified query. prosmos, in contrast to our method, returns a list of hits to the query structure, rather than a matching score for each structure in the database. this is often simpler for the user, but it does have the disadvantage that finding more hits requires editing the query meta-matrix, which can be quite difficult to calibrate. returning a score for each database structure means that adjusting the sensitivity or specificity required is simply a matter of varying the cutoff score for a match to be considered significant. an advantage of the maximally-similar subtableaux formulation is that it allows the discovery of similar substructures within two structures, without requiring that the two structures are themselves similar as a whole, or that one of the structures must match as a whole some substructure within the other structure. we may choose to use one structure as a "query" motif, usually a small well-defined structural folding pattern, and find structures that contain this entire motif as a substructure, but it is also possible to find common substructures in two unrelated folds. however, the rigorous tableau searching method is too slow for a full database search, and so konagurthu et al. introduce tableausearch. this method approximates the exact solution using an alignment-like approach, with two phases of dynamic programming. tableausearch is extremely fast, but loses the rigorous theoretical justification and is not as accurate as the exact method. it is also inherently sequential, thereby losing the ability to find non-linear structural matchings, and, at least partly, loses the ability to find substructural rather than full structure matches. this may be possible, however, by removing end gap penalties. here we present a method, based on the exact tableaux matching formulation and recent work in alignment of molecular networks, that allows searches for occurrences of a query structure as substructures of structures in a database such as scop in practical time, allows non-linear matchings, and is able to provide a set of correspondences between sses.  we evaluate the accuracy of our qp tableau matching algorithm as a method for determining the fold of a structure, using scop as the truth. the tradeoff between sensitivity and specificity for such a classification task can be shown as a receiver operating characteristic curve. roc curves for several different structural queries are shown in figures and figure shows results obtained using only tableau information, while figure shows results obtained using tableau and distance information. the area under the roc curve for each of these curves is shown in table incorporating distance information results in consistently higher auc values without significantly affecting the elapsed time. area under roc curve and time taken for searches for several structural folding patterns against the astral scop 95% sequence identity non-redundant database consisting of domains using discrete tableaux, both with and without incorporating sse distance information. times reported are elapsed times using the sparse matrix implementation on an intel xeon ghz machine with gb memory running linux. the table is sorted by query size. we find that the best-performing variation of our method, using the discrete tableau encoding rather than numeric Ω matrices, and incorporating distance information, has an auc of averaged over the eight queries in table we can see in table that the ferredoxin fold query performs significantly worse than the others. we examined the results from this query and found that a large number of false negatives occur. examining some of these false negatives in detail, we find that it is often due to dssp, which we use to define sses, not defining some of the sses required to match the query structure. although we have the capability of using stride rather than dssp, the results are often similar. this is a shortcoming of any method that depends on sse definitions, although prosmos solves it to some degree by using palsse, a secondary structure assignment method that assigns many more residues to sses precisely in order to avoid this problem. false negatives can also occur independently of the sse definition algorithm, if a structure does not have some sses not considered essential to the fold according to scop and/or sufficiently different in their orientation that tableau matching does not assign them a high score. an example of this is d1q8ba_, which does not have all the helices in the query structure, and some which it does include have rather different orientations from those in the query, but it is nevertheless classified as a member of the ferredoxin-like fold. for a larger-scale test, we used a set of queries chosen from the astral scop 95% sequence identity non-redundant data set. the queries were chosen so that each class is represented in the query set in the same ratio as it is in the database. the overall auc for different normalizations and different methods are shown in table it can be seen that normalization norm is the best normalization function for the tableau search methods, and that sheba is the best performing method, followed by our method, then vast, and lastly tableausearch and tops. figure shows the roc curves for the different methods. it can be seen that the curve for sheba lies above that for vast at every point, consistent with the results for all-against-all comparisons in the astral scop 40% sequence identity non-redundant data set reported in. the curve for our method lies between the two at low false positive rates, but crosses over the sheba curve at a false positive rate of approximately, indicating it has a slightly higher sensitivity at high false positive rates than sheba. sheba, however, is more sensitive at low false positive rates, a generally more useful attribute. area under roc curve for the query set against the astral scop 95% sequence identity non-redundant database consisting of domains, for different methods and normalizations. note that only the tableau search methods and tableausearch) require normalization, as vast, sheba and tops report normalized scores themselves and so do not require an external normalization step to combine results for different queries. the table is ordered by decreasing auc. in terms of elapsed time, tableausearch is by far the fastest method. on our system, it has a total elapsed time for the query set of only hour minutes, compared to hours for vast, hours for sheba, and hours for our method. large scale comparisons with the exact solution of the qip or ilp with cplex are not practical, as a single comparison takes at least several seconds and can take up to several days, and in some cases exhausts the virtual memory of our machine. comparison with max-cmo heuristic maximum contact map overlap is a formulation of the problem of finding the similarity of two protein structures. max-cmo uses the contact map representation of proteins, in which a protein with n residues is represented as a square symmetric matrix cn × n where cij = when the distance between residues i and j is less than some threshold, and cij = otherwise. typically this distance is defined as the cα distance, and the threshold is for example Å. the max-cmo problem is then to find a alignment of residues that maximizes the overlap between two contact maps. the value of the alignment is the number of contacts in one protein whose residues are aligned with residues that are also in contact in the other protein. max-cmo is an np-hard problem, and methods for solving it exactly, by such techniques as integer programming with lagrangian relaxation or branch-and-bound can be impractically slow. therefore, heuristic approaches are useful, and recently a variable neighborhood search algorithm for approximating max-cmo has been published, with an analysis of its effectiveness in ranking protein similarity. here we compare the performance of the qp formulation of maximally-similar subtableaux extraction with the vns heuristic for max-cmo of. we should perhaps discount any superiority in the performance of the tableau search method at the class level, as this level of classification in the cath hierarchy indicates only the percentage of α-helices and β-strands in the domain. since tableaux are based on sses we could trivially obtain good classification performance at this level just from the dssp classification, while max-cmo uses only residue contact information, and so must score protein similarity at this high level without having sses defined by an existing method. ignoring the class level comparisons therefore, we find that qp tableau search has significantly superior accuracy compared to msvns on the fischer data set, and similar accuracy to msvns on the nh3d data set. for the fischer data set, msvns took hours while the sparse matrix implementation of qp tableau search took hours on a pc with an intel core duo processor and gb of memory running 32-bit linux. for the nh3d data set, msvns took hours while qp tableau search took hours. examples substructure queries need not be entire structures themselves. in order to illustrate the ability of our method to find substructural matches, we chose the b/c sheet of the the canonical active serpin, α1-antitrypsin, pdb id 1qlp as a query tableau. figure shows the substructure represented by this query. of the total structures in our database classified by scop as belonging to the serpin fold, are matched as the top hits. one, however, d1m, is only at rank in the sorted hit list. this is the cleaved form of the serpin, but this does not account for the failure to detect its similarity, as, for example, d1jjo. is also the cleaved form and it is at rank in the sorted hit list. inspection of the tableaux for the b/c sheets of these two serpins shows that while that for d1jjo. is visibly similar to the query tableau, the relative angles of the strands in the b/c sheet of d1m are different enough from the query that the tableau is no longer sufficiently similar to find the correct matching of the two sheets. using the entire serpin structure d1qlpa_ as the query, however, results in all serpins as the top hits. substructure search evaluated as a substructure query, the β-grasp query using the discrete tableau encoding has an auc of. since the data set used as the gold standard in this case is that defined by prosmos, that method by definition has an auc of on this query. the number of superfamilies in the astral scop 95% sequence identity nonredundant database found for the eight query structures by prosmos, ssm, tops and our method, qp tableau search. prosmos and ssm return a list of significant hits, so the number of superfamilies found by these hits is shown. other methods return scores for all database structures, and the number of superfamilies in the hits with a z-score ≥ are shown. the r column is the number of superfamilies, from the combined list of those found by all methods, in which the relevant query pattern or fold description is explicitly mentioned in the scop structure description. the ratio columns show the number of superfamilies in the r column found by the specified method. therefore the prosmos results reflect not only the performance of prosmos, but also our construction of the relevant query matrices. we note that our results here differ significantly from those in table of: our method of constructing this table is similar, but not identical, to that of, we have used slightly different queries and different versions of the software and a different database have been used. consistently with, ssm finds the least number of matches. in our results, however, prosmos does not always return the greatest number of matches: sometimes tops does, since we are using a version of tops that computes scores for all matches, rather than the precomputed "classic" structure patterns. tops also tends to have more false positives than prosmos or our method, that is, superfamilies found by tops that are not considered by the scop descriptions to contain the fold in question. this is consistent with tops being a purely topological method, which does not take account of other structural properties. sometimes this also results in tops finding true positives which the other methods do not, for example when using the ferredoxin query, only tops finds the monooxygenase regulatory protein superfamily, d., which scop describes as having "some topological similarity to the ferredoxin-like fold". scop also notes in the family description for d.. that "the solution structure determinations disagree in the relative orientations of two motifs", so topological similarity without taking into account more detailed structural similarity is a more appropriate method to find matches to this structure, reflected in the relatively better performance of tops, and the previously discussed poor performance of our method on this query. in order to better examine the unique properties of each method, table shows, for each method, the number of superfamilies found only by that method, and the number of these for which scop explicitly mentions the relevant query pattern. ssm finds no hits that the other methods do not, and tops usually finds the most. for the ferredoxin query, we can see that tops finds a large number of true positives that the other methods do not; our method finds and prosmos however, on the tim-barrel query, tops finds unique hits, none of which are considered to contain the tim-barrel motif according to scop, while our method finds unique hits that all contain the tim-barrel motif according to scop. with the exception of ssm, we can see that each method finds some unique true matches that the others do not. as an example of true positive hits that only our method finds, consider the jelly-roll query. only qp tableau search finds the viral protein domain superfamily b., and the membrane penetration protein μ superfamily e., both of which are described by scop as containing a jelly-roll motif. the number of superfamilies in the astral scop 95% sequence identity nonredundant database found by only that method for the eight query structures by prosmos, ssm, tops and our method, qp tableau search. the r column is the number of superfamilies, from the combined list of those found uniquely by each method, in which the relevant query pattern or fold description is explicitly mentioned in the scop structure description. the ratio columns show the number of superfamilies in the r column represented by the superfamilies found only by the specified method. an interesting example is the ferredoxin fold, where the performance of our method as a structural search method is relatively poor. however, as a substructure search technique, some true positives are found only by our method. only qp tableau search finds the peptide methionine sulfoxide reductase superfamily d., the ccmk-like superfamily d., and the release factor superfamily e.. the first two are members of the ferredoxin-like fold but d. is described by scop as having the common fold "elaborated with additional secondary structures". the release factor superfamily is described by scop as having domains, one of which is a ferredoxin-like fold. it is important to note several caveats in interpreting table and table first, as already discussed, prosmos queries were manually constructed, which is not the case for the other methods. second, prosmos and ssm return a set of hits for a query, whereas the other methods return a matching score between the query and every database structure. hence, in order to construct the tables, a cutoff score needs to be chosen. the values in the tables are therefore very sensitive to the method used to choose the cutoff score: we could find arbitrarily many superfamilies simply by decreasing the value at which a score is considered a hit. third, as discussed in, the lack of explicit mention of a structure in the scop description does not necessarily mean the structural motif is absent. non-linear matchings in order to verify the capability of our method to find non-linear matchings when the sse ordering constraint is disabled, we first use an artificial test. five different random permutations of the eight tableaux previously discussed and shown in table were generated. these were then used as queries, and the auc for each calculated in the same way as for table the average auc for each fold over its five permutations is shown in table from this table we can see that, despite the tableaux being permuted so that the sses in the query are no longer in the same sequence as in the database structures, the structures are still matched, albeit sometimes with a lower auc than for the correctly ordered sses with the ordering constraint enabled. as a demonstration of a real case of a non-linear matching, we use as the query the hypothetical novel-fold protein ta which was recently found to have several non-linear alignments. when ordering constraints are enabled, our method finds no significant matches in the astral scop 95% sequence identity non-redundant database. however, when ordering constraints are disabled, some high-scoring hits are found, in particular the top-scoring hit is to d1kb9b cytochrome bc core subunit the superposition of these two structures is shown in figure this is different from the result reported by guerler and knapp using gangsta+, who find that pdb identifier 1go is the most similar structure. therefore, we used the gangsta+ webserver with 2jmk as the query, and found that after setting the selection criteria to require at least matching sses, d1kb9b is the fourth most significant hit, demonstrating that gangsta+ is in agreement with our method that this non-linear matching is significant.  we have introduced an improved method of searching for protein structures with similar folds using tableaux, incorporating constraints on the distances between sses to improve accuracy. this method is capable of finding either matches of an entire structure to the query, or matches where the query is a substructure of a larger structure. it is capable of finding non-linear matchings, where structurally equivalent parts do not have the same relative positions in the sequences of the two proteins. it also provides a set of corresponding sses, useful for manual validation of the result or as a seed for a more detailed structural alignment. in assessing their vns heuristic for max-cmo, pelta et al. ask whether it is necessary to solve max-cmo exactly in order to perform structure classification, and conclude that it is not: the heuristic solution is sufficient. we have shown that, consistent with previous work using the tableau representation of protein folds, the much more coarse-grained tableau representation is sufficient to accurately represent protein folds and perform structure classification. specifically, we have shown that the efficient approximation of maximally-similar subtableaux extraction by relaxed quadratic programming is able to consistently classify folds at least as accurately as the vns heuristic for max-cmo. in addition, our implementation is able to do so in less time than the msvns implementation described by. we have demonstrated that the accuracy of our technique assessed as a protein fold recognition method compares favorably with some existing methods, and that it is fast enough to scan protein structure databases in a practical time, unlike the exact solution using cplex. it is, however, not as fast as some existing methods such as sheba and vast, and the tableausearch dynamic programming approximation introduced by is faster still. these methods, however, cannot be used to find substructures or non-linear matchings. we have also demonstrated the use of our technique as a method for searching for substructures in protein structures, and compared it with some existing techniques, including prosmos. complications in objectively assessing the performance of these methods make definite conclusions in this area difficult: we can perhaps say at most that each method has different enough properties that they are all capable of finding unique hits that others miss. a structural biologist searching for matches to a motif or substructure, then, would do well to employ several of these methods rather than relying on just one. as noted by li et al., further theoretical work to find tight sufficient conditions for the qp to have an integer solution is required, although empirically an integer solution is almost always found. 
we compare the accuracy of the method in classifying protein folds with some existing techniques. 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. 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.
 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.  we developed an improved method for detecting substructural similarities in proteins using tableaux. tableaux are compared efficiently by solving the quadratic program corresponding to the quadratic integer program formulation of the extraction of maximally-similar tableaux. we compare the accuracy of the method in classifying protein folds with some existing techniques.  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. 