Limits...
Fast structure similarity searches among protein models: efficient clustering of protein fragments.

Fogolari F, Corazza A, Viglino P, Esposito G - Algorithms Mol Biol (2012)

Bottom Line: The lower bound on RMSD may be used, when restricting the search of similarity to a reasonably low RMSD threshold value, to speed up similarity searches significantly.A linux executable and a Perl script with examples are given in the supplementary material (Additional file 1).The source code is available upon request from the authors.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Biomedical Sciences and Technologies, University of Udine Piazzale Kolbe 4, 33100 Udine - Italy and Istituto Nazionale Biostrutture e Biosistemi Viale Medaglie d'Oro 305, 00136 Roma, Italy. federico.fogolari@uniud.it.

ABSTRACT

Background: For many predictive applications a large number of models is generated and later clustered in subsets based on structure similarity. In most clustering algorithms an all-vs-all root mean square deviation (RMSD) comparison is performed. Most of the time is typically spent on comparison of non-similar structures. For sets with more than, say, 10,000 models this procedure is very time-consuming and alternative faster algorithms, restricting comparisons only to most similar structures would be useful.

Results: We exploit the inverse triangle inequality on the RMSD between two structures given the RMSDs with a third structure. The lower bound on RMSD may be used, when restricting the search of similarity to a reasonably low RMSD threshold value, to speed up similarity searches significantly. Tests are performed on large sets of decoys which are widely used as test cases for predictive methods, with a speed-up of up to 100 times with respect to all-vs-all comparison depending on the set and parameters used. Sample applications are shown.

Conclusions: The algorithm presented here allows fast comparison of large data sets of structures with limited memory requirements. As an example of application we present clustering of more than 100000 fragments of length 5 from the top500H dataset into few hundred representative fragments. A more realistic scenario is provided by the search of similarity within the very large decoy sets used for the tests. Other applications regard filtering nearly-indentical conformation in selected CASP9 datasets and clustering molecular dynamics snapshots.

Availability: A linux executable and a Perl script with examples are given in the supplementary material (Additional file 1). The source code is available upon request from the authors.

No MeSH data available.


Ratio of the number of RMSD computations performed over N(N - 1)/2 versus the logarithm of the number of structures in subsets from the semfold 1khm decoy set.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3403935&req=5

Figure 1: Ratio of the number of RMSD computations performed over N(N - 1)/2 versus the logarithm of the number of structures in subsets from the semfold 1khm decoy set.

Mentions: Comparing the results reported in Tables 1 and 2 there appears to be an effect of the ensemble size N on the ratio of the actual computations over N(N - 1)/2. This effect is not apparent from equations 2 and 3 because the integration upper limit s depends implicitly on N. Assuming heuristically that the RMSDs are distributed according to a simple sine law, equations 2 and 3 can be integrated and the ratio is found to decrease with the size of the ensemble. In order to test this suggestion, for the largest set (semfold 1khm set, 22000 structures) we considered sets with 1/2, 1/4, 1/8, 1/16, 1/32, 1/64 of the structures and plotted the ratio of computations over N(N - 1)/2 against log(N). The dependence is almost linear in the range considered (Figure 1).


Fast structure similarity searches among protein models: efficient clustering of protein fragments.

Fogolari F, Corazza A, Viglino P, Esposito G - Algorithms Mol Biol (2012)

Ratio of the number of RMSD computations performed over N(N - 1)/2 versus the logarithm of the number of structures in subsets from the semfold 1khm decoy set.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3403935&req=5

Figure 1: Ratio of the number of RMSD computations performed over N(N - 1)/2 versus the logarithm of the number of structures in subsets from the semfold 1khm decoy set.
Mentions: Comparing the results reported in Tables 1 and 2 there appears to be an effect of the ensemble size N on the ratio of the actual computations over N(N - 1)/2. This effect is not apparent from equations 2 and 3 because the integration upper limit s depends implicitly on N. Assuming heuristically that the RMSDs are distributed according to a simple sine law, equations 2 and 3 can be integrated and the ratio is found to decrease with the size of the ensemble. In order to test this suggestion, for the largest set (semfold 1khm set, 22000 structures) we considered sets with 1/2, 1/4, 1/8, 1/16, 1/32, 1/64 of the structures and plotted the ratio of computations over N(N - 1)/2 against log(N). The dependence is almost linear in the range considered (Figure 1).

Bottom Line: The lower bound on RMSD may be used, when restricting the search of similarity to a reasonably low RMSD threshold value, to speed up similarity searches significantly.A linux executable and a Perl script with examples are given in the supplementary material (Additional file 1).The source code is available upon request from the authors.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Biomedical Sciences and Technologies, University of Udine Piazzale Kolbe 4, 33100 Udine - Italy and Istituto Nazionale Biostrutture e Biosistemi Viale Medaglie d'Oro 305, 00136 Roma, Italy. federico.fogolari@uniud.it.

ABSTRACT

Background: For many predictive applications a large number of models is generated and later clustered in subsets based on structure similarity. In most clustering algorithms an all-vs-all root mean square deviation (RMSD) comparison is performed. Most of the time is typically spent on comparison of non-similar structures. For sets with more than, say, 10,000 models this procedure is very time-consuming and alternative faster algorithms, restricting comparisons only to most similar structures would be useful.

Results: We exploit the inverse triangle inequality on the RMSD between two structures given the RMSDs with a third structure. The lower bound on RMSD may be used, when restricting the search of similarity to a reasonably low RMSD threshold value, to speed up similarity searches significantly. Tests are performed on large sets of decoys which are widely used as test cases for predictive methods, with a speed-up of up to 100 times with respect to all-vs-all comparison depending on the set and parameters used. Sample applications are shown.

Conclusions: The algorithm presented here allows fast comparison of large data sets of structures with limited memory requirements. As an example of application we present clustering of more than 100000 fragments of length 5 from the top500H dataset into few hundred representative fragments. A more realistic scenario is provided by the search of similarity within the very large decoy sets used for the tests. Other applications regard filtering nearly-indentical conformation in selected CASP9 datasets and clustering molecular dynamics snapshots.

Availability: A linux executable and a Perl script with examples are given in the supplementary material (Additional file 1). The source code is available upon request from the authors.

No MeSH data available.