BACKGROUND
clustering techniques are widely used in the analysis and interpretation of molecular simulations for biological macromolecules, such as proteins and nucleic acids.
for example, markov state and related approaches for conformational space partitioning  <cit>  are being used to analyze trajectories generated by molecular dynamics, e.g., to identify important folding intermediates  <cit> .
clustering is also used, either explicitly or implicitly, in order to identify high quality models generated by protein or rna structure prediction methods  <cit> .
in particular, geometric consensus methods for model quality assessment  rank models by comparing their pairs, e.g., by 3d superposition, to find frequently sampled and hence likely well predicted substructures  <cit> .
a number of methods have been developed recently to enable fast ranking and clustering of very large sets of protein models that can be generated by using current hardware in conjunction with simulation and structure prediction methods.
assessing structural similarity for pairs of models constitutes the major computational bottleneck in clustering and consensus-based mqa methods.
consequently, many ranking and clustering methods attempt to simplify structure-to-structure comparison to avoid 3d superposition, e.g., by projecting the structure into a structural motif frequency profile using a fragment library  <cit> , by using parallelization to speed-up the loop over pairs of models  <cit> , or by relying on traditional k-means clustering to limit the computational complexity  <cit> , as only the distances to k centroids need to be computed.
for example, pleiades  <cit>  uses a projection of the backbone into 21-dimensional vectors using gauss integrals, resulting in a fast k-means-based algorithm that compares structures in terms of their 21-dimensional backbone profiles.
the fragbag approach  <cit> , on the other hand, projects 3d structures into a frequency profile to enable fast structure-to-structure comparison and similarity search with a representative library of structural fragments.
pconsd  <cit> , a successful mqa method, computes model ranking by assessing similarity between protein models in terms of their distance matrices while using gpus to speed-up comparison of all pairs of models.
parallelization is also used in clusco  <cit>  to enable large scale all-vs-all comparison and enhance both hierarchical and k-means clustering in conjunction with the traditional root mean square deviation  superposition.
importantly, since k-means approaches do not imply a loop over pairs of models, the overall computation can be broken into data ‘slices’ and therefore easily implemented on modern distributed computing platforms for ‘big data’, such as hadoop or spark implementations of the map/reduce framework.
in contrast, traditional hierarchical clustering techniques require that all pairs of structures are compared, making it incompatible with these distributed platforms.
in addition, the overall distance matrix needs to be stored in memory, greatly limiting the size of data that can be analyzed using traditional hierarchical clustering approaches.
here, we address both of these challenges by combining structural profiles with a linear time geometric consensus-based ranking algorithm and profile hashing.
as shown in  <cit> , by projecting 3d coordinates into a suitable 1d structural profile that assigns each residue to a distinct state, e.g.
exposed vs. buried, the 1d-jury method implicitly compares all pairs of models to identify those that share common substructures without the need to perform a loop over pairs of models .
thus, 1d-jury provides geometric consensus-based ranking of all models in a set with a linear time complexity algorithm.
in addition, 1d-jury provides natural centroids of clusters consisting of models sharing common substructures.
it should be also noted that the 1d-jury approach can be generalized to arbitrary structures  as long as they can be projected into fixed length structural profiles, such as frequency profiles used by fragbag or gauss integral projections used by pleiades.
structural profiles in conjunction with linear time consensus ranking can be further combined with profile hashing to enable efficient hierarchical clustering with a low memory footprint.
the main idea is to use structural profiles in order to define hashing keys that map similar structures into the same values of a hash function, and thus enable collating profiles/structures with the same keys into initial micro-clusters.
these micro-clusters are subsequently either tuned  to obtain a certain number  of clusters and data coverage , or aggregated hierarchically using the hamming, cosine or other applicable distance measure .
building on these algorithmic engines, we present the uqlust package which combines 1d structural profiles, hashing and linear time ranking to enable ultrafast clustering of very large sets of atomistic or coarse-grained protein or rna structures.fig.
<dig> schematic representation of approximate hierarchical clustering with profile hashing to generate ‘micro-clusters’  that are subsequently hierarchically clustered, starting from the representative structures  in each micro-cluster, using an applicable distance measure, such as hamming, cosine or rmsd
implementation
structural profiles
the following versatile residue-level projections of 3d structures  are implemented in uqlust:i) ss-sa or secondary structure  – solvent accessibility  profile, which assigns each amino acid residue to one of three secondary structures , and one of up to nsa =  <dig> solvent accessibility states; the dssp utility  <cit>  is integrated with uqlust to assign ss and rsa states;
ii) ca-nc or approximate distance dependent secondary structure  – solvent accessibility  profile, which can be used for cα only models, and assigns pseudo-secondary structure states based on distances between cα atoms  – for details see supplementary materials and uqlust manual;
iii) ca-cm , which is also applicable to both atomistic and reduced models, and consists of the top triangle of the binary contact map, where d <  <dig>  ang, |i-j| >  <dig>
analogously to protein profiles, 1d rna profiles for ranking and clustering  are built either using a backbone phosphorus atom contact map  where d <  <dig>  ang, |i-j| >  <dig>  or by considering a combination of secondary structure and base pairing states generated by using rnaview  <cit> .
namely, a simplified secondary structure assignment  is combined with a coarse-grained leontis and westhof  classification of base-pairs into one of  <dig> different types based on nucleotide pairs , glycosidic bond orientation , interacting edges , resulting in  <dig> distinct states .
another type of profile available in uqlust uses a structural motif/fragment frequency profile to represent arbitrary structures .
for proteins, uqlust uses the fragbag library  <cit>  of  <dig> backbone fragments of length  <dig> residues, while its custom developed rna-fragbag counterpart is used for rnas .
a user-defined, protein or rna, residue level or fragment-based profile can also be used in uqlust, in conjunction with an external application, such as dssr  <cit> .
a pre-defined workflow  combines simple secondary structure state assignment  with distinct torsional angle states , defined as combinations of dssr epsilon-zeta bi and bii backbone states with chi syn- and anti- states .
the resulting  <dig> distinct states can be further split based on base-pair type assignment, similar to that used for rna-ss-lw.
such defined profiles, as listed in additional file 1: table s <dig>  can be used for either model assessment using 1d-jury , or explicit clustering with profile hashing, using hash keys generated with a profile of choice to provide an initial ‘slicing’ of data.
profile hashing
profile hashing is used in conjunction with 1d-jury to achieve ultrafast clustering heuristics with a low memory footprint.
binary hash keys are generated with a 1d profile of choice by comparing each profile with a reference profile that obtains the maximum 1d-jury score .
the hash key for a profile is defined at each position as follows:  <dig> is added to the key if a given profile is in the same state as the reference profile at that position,  <dig> is added otherwise .
since the best 1d-jury score reference profile is expected to represent a natural geometric consensus for a substantial subset of models  <cit> , one can also expect that many of such largely consistent models will likely obtain the same hash key, resulting in less granular partitioning into micro-clusters  compared with a random reference structure, or a direct use of multi-state profile as opposed to binary ‘geometric consensus’ keys.
clustering heuristics for big macromolecular data
the first heuristic discussed here is a profile hashing-based clustering that directly draws from the above considerations.
it is referred to as uqlust:hash , where k defines the number of target clusters, and f denotes the fraction of data that should be contained within those k clusters.
hash  starts by slicing data into micro-clusters with the same hashing function value.
subsequent agglomeration into k clusters  is obtained by simply changing the granularity of hash keys, which is achieved by removing a sufficient number of the most variable profile hash key positions characterized by high entropy across all data vectors.
another heuristic in uqclust is a form of reference-based partitioning, which is referred to as uqlust:rpart .
as before, this new heuristic relies on the initial identification of 1d-jury ‘centroid’ for the entire data set, as a suitable reference conformation.
for efficiency and granularity, rpart also represents all profiles in terms of binary hash keys.
however, the subsequent partitioning of data proceeds very differently.
rather than aggregating hashing-based micro-clusters, rpart recursively identifies macro-clusters centered on a reference profile by adjusting the radius of clustering to achieve k clusters comprising f% of data.
specifically, hamming distances to the reference profile hash key are computed to identify a central inner sphere that contains data points closer than the radius of clustering  to the reference vector.
such defined sphere constitutes a candidate for a macro-cluster.
the profile  with the highest 1d-jury score in the outer layer is then selected as the next reference structure.
next, the radius of clustering is reset to its distance from the original 1d-jury reference, and the process is repeated on the remainder of the data, considering only points at distances less than twice the current radius of clustering from the original 1d-jury reference.
if after k iterations less than f% of data points are covered by such defined k candidate macro-clusters, then the size of the radius of clustering is increased , and the process is repeated.
the process stops when no further improvement towards the targeted f is observed.
finally, in the case of approximate hierarchical clustering, which is referred to as uqlust:tree, the first step is analogous to that used for rpart  or hash , except that a large k is used to induce a large number of small clusters  and f is set to 100% to include all data.
while k can be modified by the user to set the tradeoff between speed and accuracy, its default value is set to k =  <dig>  to provide sufficient granularity in both conformational space partitioning and model clustering for quality assessment .
in the next step, a 1d-jury centroid is computed for each micro-cluster, and from this level traditional average distance agglomerative  hierarchical clustering with either hamming or cosine distance , or rmsd  can be applied.
as a result, effectively linear complexity in the number of structures, nstruct, is achieved when nstruct > > k .
implementation details
uqlust is written in c# and should be easily portable between different operating systems .
multithreading is implemented to speed-up profile pre-processing, ranking and clustering.
fast methods for rmsd  <cit>  and maxsub  <cit>  structure similarity measures are implemented to speed-up structure to structure comparison when profiles are not used.
for vector hashing, c# dictionary type with a hash function default method gethashcode() is used.
work is in progress to enable the use of uqlust  in conjunction with hadoop map/reduce framework, using the microsoft azure plugin for c#.
RESULTS
linear time ranking of macromolecular models
as shown in  <cit> , by projecting macromolecular 3d coordinates into a suitable 1d profile and profile pre-processing to compute the state frequency vector at each profile position, one can implicitly compare all pairs of models to compute their overall geometric consensus ranking with a linear time complexity algorithm.
the resulting 1d-jury approach enables ultrafast ranking of large sets of models, while yielding results on par with quadratic complexity methods, such as 3d-jury  <cit>  or pconsd  <cit> .
this is illustrated in additional file 1: figure s <dig>
here, uqlust is evaluated in terms of ranking and model assessment using casp <dig>  <cit>  and tasser  <cit>  benchmarks for proteins.
only those targets/models that were successfully processed by all methods are used for comparison .
several well performing profiles, including a simple 1d-ss-sa and a contact map profile 1d-ca-cm, motivated by the success of pconsd , are assessed.
as can be seen from table  <dig>  the running times indeed scale linearly with the number of structures for uqlust-1d-ca-cm, as opposed to quadratic scaling for pconsd.
furthermore, as can be seen from table  <dig>  the results of uqlust-1d-ca-cm and more compact uqlust-1d-ss-sa profile based ranking are on par with pconsd in terms of selection of top models.
interestingly, using centroids of explicitly identified clusters as top models leads to further improvements, especially for hashing and reference-based uqlust heuristics that outperform k-means approaches on casp, while hierarchical uqlust:tree clustering works best on tasser.table  <dig> running times for model ranking on tasser target 256b_a
profile preprocessing
uqlust:1d-ca-cm
time in cpu sec on a server with  <dig> intel  core  <dig> q6600@ <dig> ghz cpus, 4 gb, and linux version ubuntu  <dig> .
pconsd was allowed to use all  <dig> cpus and the tesla c <dig> graphical card with  <dig> gpus, while times for uqlust are for  <dig> cpu only to demonstrate its linear scaling
uqlust:1d-ca-cm
<dig>  /  <dig>
<dig>  /  <dig>
uqlust:1d-ss-sa
<dig>  /  <dig>
<dig>  /  <dig>
uqlust: hash
<dig>  /  <dig>
<dig>  /  <dig>
uqlust: rpart
<dig>  /  <dig>
<dig>  /  <dig>
uqlust:tree
<dig>  /  <dig>
<dig>  /  <dig>
average maxsub similarity score between top ranking and best models , and fraction of good models  are reported for both casp and tasser targets.
the fraction of good models is defined as the fraction of targets with the top ranking model less than  <dig>  maxsub score from the best model for casp, and less than  <dig> ang rmsd for tasser.
centroids of the  <dig> largest  clusters are considered for clustering methods, and f = 60% of data is used for uqlust
ultrafast clustering with profile hashing
traditional and profile hashing-based hierarchical clustering techniques are compared in terms of time and memory usage in table  <dig>  we used coarse-grained models generated using the cabs-flex server  <cit>  for three distinct conformers of troponin c, increasing the number of models for each conformer to obtain a series of data sets of growing size, each consisting of  <dig> distinct clusters of equal number of structures.
note that, unlike for other hierarchical clustering methods tested, the running time and memory usage grow essentially linearly with the size of the problem for uqlust:tree  to define initial micro-clusters).
running times and memory allocation can be further reduced by replacing the ca-cm profile used here with a much more compact ss-sa profile.table  <dig> time and memory usage for hierarchical clustering methods
time
104
241
581
1604
3743
time
70
92
168
310
488
memory
<dig>
<dig>
<dig>
<dig>
<dig>
cpu times  and memory usage  for approximate uqlust:tree vs. full hierarchical clustering, obtained by using clusco  <cit>  or maxclust  <cit> .
all calculations were performed on a server with  <dig> intel  xeon  e5-2680-0@ <dig> ghz cpus, 132gb, and linux version  <dig> .32- <dig> .
<dig> el <dig> centos.plus.x86_64
it should be emphasized that there is a very high degree of concordance between full hierarchical and ca-cm  profile-based uqlust:tree, as indicated by the rand index of  <dig>   and illustrated in additional file 1: figure s <dig>  very similar results can also be obtained  using the compact pseudo-secondary structure/contact number profile, ca-nc, illustrating the versatility of uqlust.
it should be also noted that rmsd can also be used in uqust:tree to aggregate micro-clusters, providing in this case virtually identical results to those of full hierarchical clustering, without affecting significantly running times since only representative structures need to be superimposed.
in addition to applications to large scale structure prediction and molecular simulations of a target protein or rna , uqlust can also be used in conjunction with the fragbag structural motif frequency profile  <cit>  for analysis and clustering of arbitrary structures , including an interactive exploration of the entire pdb.
this is illustrated by performing hierarchical clustering of about  <dig>  protein chains from the pdb that were assigned no more than one cath fold level annotation to avoid ambiguous class assignment.
in order to perform the task on a linux intel i7-30610qm  <dig>  ghz  <dig> core laptop, uqlust:tree requires less than  <dig>  gb of ram and about  <dig>  and  <dig>  cpu hours for profile generation and hierarchical clustering, respectively, using the fragbag profile, rpart  micro-clusters and cosine similarity measure.
for comparison, a simple hashing-based clustering with uqlust: hash  takes only about  <dig> cpu seconds, resulting in small clusters largely consistent at the superfamily level .
it should be also noted that cosine similarity is more appropriate for frequency profiles that are characterized by large differences in counts and the overall profile vector norm, as opposed to hamming distance that works well for residue level or contact map profiles .
note that cath contains over thousand folds and about  <dig>  superfamilies, requiring a large number  of micro-clusters for these highly granular data  <cit> .
the results are illustrated in fig.
2: the three main classes of proteins  cluster largely together, while within the micro-clusters the majority voting results in over 91%, 88% and 87% classification accuracy  at the level of cath class, architecture, and fold assignment, respectively.fig.
<dig> hierarchical clustering of  <dig>  protein chains from the protein data bank, using the fragment-based fragbag profile and the uqlust:tree algorithm.
the initial micro-clusters of structures deemed as closely related  constitute the leaves in the tree.
cath assignment at the class level for majority alpha, alpha/beta  and beta clusters are shown as red, blue and yellow bars, respectively.
it should be noted that the uqlust graphical user interface enables interactive exploration of such generated dendograms and other representations of large data sets
thus, despite large differences in length and significant variation in the secondary structure content within cath fold or superfamily members, a simple fragbag profile can capture important global characteristics of the hierarchy of protein folds.
on the other hand, the fragbag library had been primarily designed to enable fast retrieval of similar structures from pdb, rather than the overall structural classification.
importantly, the resolution and accuracy achieved here can be further improved by combining fragbag with other types of profiles, such as the gauss integral representation of the backbone trace used by pleiades  <cit> .
such extensions can be implemented by using a user defined profile in uqlust, and will be a subject of a future investigation.
clustering and ranking of rna structures
we briefly illustrate the use of uqlust to cluster and rank rna structures, using the farna benchmark  <cit> , and a set of 23s, 16s and 5s ribosomal rnas, collected from the scor database  <cit>  and augmented by additional structures obtained from pdb.
the results for six farna targets, with a subset of  <dig> models each, obtained using clustering to identify centroids of  <dig> largest clusters as top scoring models, are summarized in table  <dig>  the performance of uqlust: rpart  with either rna-ss-lw or rna-ss-ta  profile and hamming distance are on par  compared to enhanced k-means approach  with 3d structures and rmsd.table  <dig> clustering-based rna model quality assessment for farna
rmsd  between the native structure and the closest of top  <dig> centroids, obtained using uqlust:k-means with rmsd distance  or uqlust:rpart with hamming distance and rna-ss-lw profile , are compared with the best possible prediction, i.e., rmsd for the best model in a subset of  <dig> decoys for each target from  <cit>
hierarchical clustering of ribosomal rnas using a fragment-based profile is illustrated in additional file 1: figure s <dig>  a library of  <dig> representative coarse-grained 5-mer backbone  rna fragments, derived from the rna <dig> set of rna structures  <cit>  is used to define an rna fragment-based profile, denoted as rna-fragbag.
such defined profile is then used in conjunction with uqlust:tree and cosine distance, demonstrating high concordance with the three classes of ribosomal rnas included.
finally, we would like to emphasize that by enabling large-scale numerical experiments and benchmarking, uqlust can provide a platform for further refinement of profile-based approaches for macromolecular structure analysis and modeling, including the development of comprehensive rna fragment libraries.
CONCLUSIONS
by combining profile hashing in conjunctions with 1d residue level, fragment-based or arbitrary user defined profiles of proteins and rnas, as well as the 1d-jury linear time complexity ranking algorithm with implicit comparison of all pairs of models  <cit> , uqlust enables ultrafast and low memory footprint clustering  of very large sets of atomistic or coarse-grained models of fixed length using residue profiles, or arbitrary macromolecular structures when using fragment profiles.
at the same time, uqlust yields results on par with methods implying much higher computational cost in both model quality assessment and explicit clustering.
a number of widely used methods and utilities for macromolecular structure analysis, including dssp for protein secondary structure and solvent accessibility assignment  <cit> , rnaview for rna secondary structure and base-pair type assignment  <cit> , and fragbag for fragment-based profile assignment  <cit> , are implemented in uqlust and integrated into workflows for ranking and clustering without the need to use external programs.
the code is freely available to the community and can be used in both batch and interactive modes, providing a versatile, efficient and easy-to-use toolkit for macromolecular structure exploration and analysis.
availability and requirements
the uqlust package is freely available under the gnu general public license at https://github.com/uqlust.
uqlust has been written in c# and should be easily portable between different operating systems.
system independent pre-compiled executables that require .net ver.
<dig>  or higher, or mono ver.
<dig>  on 64-bit windows or linux operating systems, respectively, are provided with the distribution.
additional file
additional file 1: figure s <dig>  1d-jury algorithm for geometric consensus-based model ranking with contact map profiles.
three models  of a hypothetical protein consisting of just  <dig> amino acid residues are considered, with the upper triangle of the inter-residue contact map  arranged as a linear profile.
black squares indicate contacts, while yellow squares indicate pairs of residues that are not in contact.
the calculation of the score for the best scoring m <dig> model that corresponds to the consensus state at  <dig>  profile positions proceeds red arrows.
note that a vector of state counts in each column of the profile can be precomputed in linear time, allowing one to account for all pairwise similarities without the need for a loop over pairs of models.
figure s <dig>  assessment of protein model selection on tasser benchmark using uqlust: hash  with different choices of the number of clusters k, and fraction of data included f. low  rmsd of the top ranking model with respect to the best model available indicates better results.
figure s <dig>  comparison between full  and uqlust:tree  hierarchical clustering of coarse-grained structures obtained using cabs-flex server .
three initial conformations of troponin c are used to generate  <dig> distinct clusters .
figure s <dig>  hierarchical clustering of ribosomal rnas  using the fragment-based rna-fragbag profile, uqlust:tree in conjunction with profile hashing  and cosine distance.
table s <dig>  structural profiles implemented in uqlust.
for each profile, its type , the source of state assignment, the number of states and the size  of the profile are reported.
abbreviations
cacarbon alpha
caspcritical assessment of structure prediction
cathclass, architecture, topology, homologous superfamily classification
cmcontact map
lwleontis and westhof
mqamodel quality assessment
ncnumber of contacts
pdbprotein data bank
rmsdroot mean square deviation
sasolvent accessibility
sssecondary structure

 clustering techniques are widely used in the analysis and interpretation of molecular simulations for biological macromolecules, such as proteins and nucleic acids. for example, markov state and related approaches for conformational space partitioning are being used to analyze trajectories generated by molecular dynamics, e.g., to identify important folding intermediates. clustering is also used, either explicitly or implicitly, in order to identify high quality models generated by protein or rna structure prediction methods. in particular, geometric consensus methods for model quality assessment rank models by comparing their pairs, e.g., by 3d superposition, to find frequently sampled and hence likely well predicted substructures. a number of methods have been developed recently to enable fast ranking and clustering of very large sets of protein models that can be generated by using current hardware in conjunction with simulation and structure prediction methods. assessing structural similarity for pairs of models constitutes the major computational bottleneck in clustering and consensus-based mqa methods. consequently, many ranking and clustering methods attempt to simplify structure-to-structure comparison to avoid 3d superposition, e.g., by projecting the structure into a structural motif frequency profile using a fragment library, by using parallelization to speed-up the loop over pairs of models, or by relying on traditional k-means clustering to limit the computational complexity, as only the distances to k centroids need to be computed. for example, pleiades uses a projection of the backbone into 21-dimensional vectors using gauss integrals, resulting in a fast k-means-based algorithm that compares structures in terms of their 21-dimensional backbone profiles. the fragbag approach, on the other hand, projects 3d structures into a frequency profile to enable fast structure-to-structure comparison and similarity search with a representative library of structural fragments. pconsd, a successful mqa method, computes model ranking by assessing similarity between protein models in terms of their distance matrices while using gpus to speed-up comparison of all pairs of models. parallelization is also used in clusco to enable large scale all-vs-all comparison and enhance both hierarchical and k-means clustering in conjunction with the traditional root mean square deviation superposition. importantly, since k-means approaches do not imply a loop over pairs of models, the overall computation can be broken into data ‘slices’ and therefore easily implemented on modern distributed computing platforms for ‘big data’, such as hadoop or spark implementations of the map/reduce framework. in contrast, traditional hierarchical clustering techniques require that all pairs of structures are compared, making it incompatible with these distributed platforms. in addition, the overall distance matrix needs to be stored in memory, greatly limiting the size of data that can be analyzed using traditional hierarchical clustering approaches. here, we address both of these challenges by combining structural profiles with a linear time geometric consensus-based ranking algorithm and profile hashing. as shown in, by projecting 3d coordinates into a suitable 1d structural profile that assigns each residue to a distinct state, e.g. exposed vs. buried, the 1d-jury method implicitly compares all pairs of models to identify those that share common substructures without the need to perform a loop over pairs of models. thus, 1d-jury provides geometric consensus-based ranking of all models in a set with a linear time complexity algorithm. in addition, 1d-jury provides natural centroids of clusters consisting of models sharing common substructures. it should be also noted that the 1d-jury approach can be generalized to arbitrary structures as long as they can be projected into fixed length structural profiles, such as frequency profiles used by fragbag or gauss integral projections used by pleiades. structural profiles in conjunction with linear time consensus ranking can be further combined with profile hashing to enable efficient hierarchical clustering with a low memory footprint. the main idea is to use structural profiles in order to define hashing keys that map similar structures into the same values of a hash function, and thus enable collating profiles/structures with the same keys into initial micro-clusters. these micro-clusters are subsequently either tuned to obtain a certain number of clusters and data coverage, or aggregated hierarchically using the hamming, cosine or other applicable distance measure. building on these algorithmic engines, we present the uqlust package which combines 1d structural profiles, hashing and linear time ranking to enable ultrafast clustering of very large sets of atomistic or coarse-grained protein or rna structures.fig. schematic representation of approximate hierarchical clustering with profile hashing to generate ‘micro-clusters’ that are subsequently hierarchically clustered, starting from the representative structures in each micro-cluster, using an applicable distance measure, such as hamming, cosine or rmsd implementation structural profiles the following versatile residue-level projections of 3d structures are implemented in uqlust:i) ss-sa or secondary structure – solvent accessibility profile, which assigns each amino acid residue to one of three secondary structures, and one of up to nsa =  solvent accessibility states; the dssp utility is integrated with uqlust to assign ss and rsa states; ii) ca-nc or approximate distance dependent secondary structure – solvent accessibility profile, which can be used for cα only models, and assigns pseudo-secondary structure states based on distances between cα atoms – for details see supplementary materials and uqlust manual; iii) ca-cm, which is also applicable to both atomistic and reduced models, and consists of the top triangle of the binary contact map, where d <  ang, |i-j| >  analogously to protein profiles, 1d rna profiles for ranking and clustering are built either using a backbone phosphorus atom contact map where d <  ang, |i-j| >  or by considering a combination of secondary structure and base pairing states generated by using rnaview. namely, a simplified secondary structure assignment is combined with a coarse-grained leontis and westhof classification of base-pairs into one of different types based on nucleotide pairs, glycosidic bond orientation, interacting edges, resulting in distinct states. another type of profile available in uqlust uses a structural motif/fragment frequency profile to represent arbitrary structures. for proteins, uqlust uses the fragbag library of backbone fragments of length residues, while its custom developed rna-fragbag counterpart is used for rnas. a user-defined, protein or rna, residue level or fragment-based profile can also be used in uqlust, in conjunction with an external application, such as dssr. a pre-defined workflow combines simple secondary structure state assignment with distinct torsional angle states, defined as combinations of dssr epsilon-zeta bi and bii backbone states with chi syn- and anti- states. the resulting distinct states can be further split based on base-pair type assignment, similar to that used for rna-ss-lw. such defined profiles, as listed in additional file 1: table s can be used for either model assessment using 1d-jury, or explicit clustering with profile hashing, using hash keys generated with a profile of choice to provide an initial ‘slicing’ of data. profile hashing profile hashing is used in conjunction with 1d-jury to achieve ultrafast clustering heuristics with a low memory footprint. binary hash keys are generated with a 1d profile of choice by comparing each profile with a reference profile that obtains the maximum 1d-jury score. the hash key for a profile is defined at each position as follows: is added to the key if a given profile is in the same state as the reference profile at that position, is added otherwise. since the best 1d-jury score reference profile is expected to represent a natural geometric consensus for a substantial subset of models, one can also expect that many of such largely consistent models will likely obtain the same hash key, resulting in less granular partitioning into micro-clusters compared with a random reference structure, or a direct use of multi-state profile as opposed to binary ‘geometric consensus’ keys. clustering heuristics for big macromolecular data the first heuristic discussed here is a profile hashing-based clustering that directly draws from the above considerations. it is referred to as uqlust:hash, where k defines the number of target clusters, and f denotes the fraction of data that should be contained within those k clusters. hash starts by slicing data into micro-clusters with the same hashing function value. subsequent agglomeration into k clusters is obtained by simply changing the granularity of hash keys, which is achieved by removing a sufficient number of the most variable profile hash key positions characterized by high entropy across all data vectors. another heuristic in uqclust is a form of reference-based partitioning, which is referred to as uqlust:rpart. as before, this new heuristic relies on the initial identification of 1d-jury ‘centroid’ for the entire data set, as a suitable reference conformation. for efficiency and granularity, rpart also represents all profiles in terms of binary hash keys. however, the subsequent partitioning of data proceeds very differently. rather than aggregating hashing-based micro-clusters, rpart recursively identifies macro-clusters centered on a reference profile by adjusting the radius of clustering to achieve k clusters comprising f% of data. specifically, hamming distances to the reference profile hash key are computed to identify a central inner sphere that contains data points closer than the radius of clustering to the reference vector. such defined sphere constitutes a candidate for a macro-cluster. the profile with the highest 1d-jury score in the outer layer is then selected as the next reference structure. next, the radius of clustering is reset to its distance from the original 1d-jury reference, and the process is repeated on the remainder of the data, considering only points at distances less than twice the current radius of clustering from the original 1d-jury reference. if after k iterations less than f% of data points are covered by such defined k candidate macro-clusters, then the size of the radius of clustering is increased, and the process is repeated. the process stops when no further improvement towards the targeted f is observed. finally, in the case of approximate hierarchical clustering, which is referred to as uqlust:tree, the first step is analogous to that used for rpart or hash, except that a large k is used to induce a large number of small clusters and f is set to 100% to include all data. while k can be modified by the user to set the tradeoff between speed and accuracy, its default value is set to k =  to provide sufficient granularity in both conformational space partitioning and model clustering for quality assessment. in the next step, a 1d-jury centroid is computed for each micro-cluster, and from this level traditional average distance agglomerative hierarchical clustering with either hamming or cosine distance, or rmsd can be applied. as a result, effectively linear complexity in the number of structures, nstruct, is achieved when nstruct > > k. implementation details uqlust is written in c# and should be easily portable between different operating systems. multithreading is implemented to speed-up profile pre-processing, ranking and clustering. fast methods for rmsd and maxsub structure similarity measures are implemented to speed-up structure to structure comparison when profiles are not used. for vector hashing, c# dictionary type with a hash function default method gethashcode() is used. work is in progress to enable the use of uqlust in conjunction with hadoop map/reduce framework, using the microsoft azure plugin for c#.  linear time ranking of macromolecular models as shown in, by projecting macromolecular 3d coordinates into a suitable 1d profile and profile pre-processing to compute the state frequency vector at each profile position, one can implicitly compare all pairs of models to compute their overall geometric consensus ranking with a linear time complexity algorithm. the resulting 1d-jury approach enables ultrafast ranking of large sets of models, while yielding results on par with quadratic complexity methods, such as 3d-jury or pconsd. this is illustrated in additional file 1: figure s here, uqlust is evaluated in terms of ranking and model assessment using casp and tasser benchmarks for proteins. only those targets/models that were successfully processed by all methods are used for comparison. several well performing profiles, including a simple 1d-ss-sa and a contact map profile 1d-ca-cm, motivated by the success of pconsd, are assessed. as can be seen from table  the running times indeed scale linearly with the number of structures for uqlust-1d-ca-cm, as opposed to quadratic scaling for pconsd. furthermore, as can be seen from table  the results of uqlust-1d-ca-cm and more compact uqlust-1d-ss-sa profile based ranking are on par with pconsd in terms of selection of top models. interestingly, using centroids of explicitly identified clusters as top models leads to further improvements, especially for hashing and reference-based uqlust heuristics that outperform k-means approaches on casp, while hierarchical uqlust:tree clustering works best on tasser.table running times for model ranking on tasser target 256b_a profile preprocessing uqlust:1d-ca-cm time in cpu sec on a server with intel core q6600@ ghz cpus, 4 gb, and linux version ubuntu. pconsd was allowed to use all cpus and the tesla c graphical card with gpus, while times for uqlust are for cpu only to demonstrate its linear scaling uqlust:1d-ca-cm / / uqlust:1d-ss-sa / / uqlust: hash / / uqlust: rpart / / uqlust:tree / / average maxsub similarity score between top ranking and best models, and fraction of good models are reported for both casp and tasser targets. the fraction of good models is defined as the fraction of targets with the top ranking model less than maxsub score from the best model for casp, and less than ang rmsd for tasser. centroids of the largest clusters are considered for clustering methods, and f = 60% of data is used for uqlust ultrafast clustering with profile hashing traditional and profile hashing-based hierarchical clustering techniques are compared in terms of time and memory usage in table  we used coarse-grained models generated using the cabs-flex server for three distinct conformers of troponin c, increasing the number of models for each conformer to obtain a series of data sets of growing size, each consisting of distinct clusters of equal number of structures. note that, unlike for other hierarchical clustering methods tested, the running time and memory usage grow essentially linearly with the size of the problem for uqlust:tree to define initial micro-clusters). running times and memory allocation can be further reduced by replacing the ca-cm profile used here with a much more compact ss-sa profile.table time and memory usage for hierarchical clustering methods time 104 241 581 1604 3743 time 70 92 168 310 488 memory cpu times and memory usage for approximate uqlust:tree vs. full hierarchical clustering, obtained by using clusco or maxclust. all calculations were performed on a server with intel xeon e5-2680-0@ ghz cpus, 132gb, and linux version.32-. el centos.plus.x86_64 it should be emphasized that there is a very high degree of concordance between full hierarchical and ca-cm profile-based uqlust:tree, as indicated by the rand index of and illustrated in additional file 1: figure s very similar results can also be obtained using the compact pseudo-secondary structure/contact number profile, ca-nc, illustrating the versatility of uqlust. it should be also noted that rmsd can also be used in uqust:tree to aggregate micro-clusters, providing in this case virtually identical results to those of full hierarchical clustering, without affecting significantly running times since only representative structures need to be superimposed. in addition to applications to large scale structure prediction and molecular simulations of a target protein or rna, uqlust can also be used in conjunction with the fragbag structural motif frequency profile for analysis and clustering of arbitrary structures, including an interactive exploration of the entire pdb. this is illustrated by performing hierarchical clustering of about protein chains from the pdb that were assigned no more than one cath fold level annotation to avoid ambiguous class assignment. in order to perform the task on a linux intel i7-30610qm  ghz core laptop, uqlust:tree requires less than  gb of ram and about and cpu hours for profile generation and hierarchical clustering, respectively, using the fragbag profile, rpart micro-clusters and cosine similarity measure. for comparison, a simple hashing-based clustering with uqlust: hash takes only about cpu seconds, resulting in small clusters largely consistent at the superfamily level. it should be also noted that cosine similarity is more appropriate for frequency profiles that are characterized by large differences in counts and the overall profile vector norm, as opposed to hamming distance that works well for residue level or contact map profiles. note that cath contains over thousand folds and about superfamilies, requiring a large number of micro-clusters for these highly granular data. the results are illustrated in fig. 2: the three main classes of proteins cluster largely together, while within the micro-clusters the majority voting results in over 91%, 88% and 87% classification accuracy at the level of cath class, architecture, and fold assignment, respectively.fig. hierarchical clustering of protein chains from the protein data bank, using the fragment-based fragbag profile and the uqlust:tree algorithm. the initial micro-clusters of structures deemed as closely related constitute the leaves in the tree. cath assignment at the class level for majority alpha, alpha/beta and beta clusters are shown as red, blue and yellow bars, respectively. it should be noted that the uqlust graphical user interface enables interactive exploration of such generated dendograms and other representations of large data sets thus, despite large differences in length and significant variation in the secondary structure content within cath fold or superfamily members, a simple fragbag profile can capture important global characteristics of the hierarchy of protein folds. on the other hand, the fragbag library had been primarily designed to enable fast retrieval of similar structures from pdb, rather than the overall structural classification. importantly, the resolution and accuracy achieved here can be further improved by combining fragbag with other types of profiles, such as the gauss integral representation of the backbone trace used by pleiades. such extensions can be implemented by using a user defined profile in uqlust, and will be a subject of a future investigation. clustering and ranking of rna structures we briefly illustrate the use of uqlust to cluster and rank rna structures, using the farna benchmark, and a set of 23s, 16s and 5s ribosomal rnas, collected from the scor database and augmented by additional structures obtained from pdb. the results for six farna targets, with a subset of models each, obtained using clustering to identify centroids of largest clusters as top scoring models, are summarized in table  the performance of uqlust: rpart with either rna-ss-lw or rna-ss-ta profile and hamming distance are on par compared to enhanced k-means approach with 3d structures and rmsd.table clustering-based rna model quality assessment for farna rmsd between the native structure and the closest of top centroids, obtained using uqlust:k-means with rmsd distance or uqlust:rpart with hamming distance and rna-ss-lw profile, are compared with the best possible prediction, i.e., rmsd for the best model in a subset of decoys for each target from hierarchical clustering of ribosomal rnas using a fragment-based profile is illustrated in additional file 1: figure s a library of representative coarse-grained 5-mer backbone rna fragments, derived from the rna set of rna structures is used to define an rna fragment-based profile, denoted as rna-fragbag. such defined profile is then used in conjunction with uqlust:tree and cosine distance, demonstrating high concordance with the three classes of ribosomal rnas included. finally, we would like to emphasize that by enabling large-scale numerical experiments and benchmarking, uqlust can provide a platform for further refinement of profile-based approaches for macromolecular structure analysis and modeling, including the development of comprehensive rna fragment libraries.  by combining profile hashing in conjunctions with 1d residue level, fragment-based or arbitrary user defined profiles of proteins and rnas, as well as the 1d-jury linear time complexity ranking algorithm with implicit comparison of all pairs of models, uqlust enables ultrafast and low memory footprint clustering of very large sets of atomistic or coarse-grained models of fixed length using residue profiles, or arbitrary macromolecular structures when using fragment profiles. at the same time, uqlust yields results on par with methods implying much higher computational cost in both model quality assessment and explicit clustering. a number of widely used methods and utilities for macromolecular structure analysis, including dssp for protein secondary structure and solvent accessibility assignment, rnaview for rna secondary structure and base-pair type assignment, and fragbag for fragment-based profile assignment, are implemented in uqlust and integrated into workflows for ranking and clustering without the need to use external programs. the code is freely available to the community and can be used in both batch and interactive modes, providing a versatile, efficient and easy-to-use toolkit for macromolecular structure exploration and analysis. availability and requirements the uqlust package is freely available under the gnu general public license at https://github.com/uqlust. uqlust has been written in c# and should be easily portable between different operating systems. system independent pre-compiled executables that require.net ver. or higher, or mono ver. on 64-bit windows or linux operating systems, respectively, are provided with the distribution. additional file additional file 1: figure s 1d-jury algorithm for geometric consensus-based model ranking with contact map profiles. three models of a hypothetical protein consisting of just amino acid residues are considered, with the upper triangle of the inter-residue contact map arranged as a linear profile. black squares indicate contacts, while yellow squares indicate pairs of residues that are not in contact. the calculation of the score for the best scoring m model that corresponds to the consensus state at profile positions proceeds red arrows. note that a vector of state counts in each column of the profile can be precomputed in linear time, allowing one to account for all pairwise similarities without the need for a loop over pairs of models. figure s assessment of protein model selection on tasser benchmark using uqlust: hash with different choices of the number of clusters k, and fraction of data included f. low rmsd of the top ranking model with respect to the best model available indicates better results. figure s comparison between full and uqlust:tree hierarchical clustering of coarse-grained structures obtained using cabs-flex server. three initial conformations of troponin c are used to generate distinct clusters. figure s hierarchical clustering of ribosomal rnas using the fragment-based rna-fragbag profile, uqlust:tree in conjunction with profile hashing and cosine distance. table s structural profiles implemented in uqlust. for each profile, its type, the source of state assignment, the number of states and the size of the profile are reported. abbreviations cacarbon alpha caspcritical assessment of structure prediction cathclass, architecture, topology, homologous superfamily classification cmcontact map lwleontis and westhof mqamodel quality assessment ncnumber of contacts pdbprotein data bank rmsdroot mean square deviation sasolvent accessibility sssecondary structure 
uqlust makes use of structural profiles of proteins and nucleic acids, while combining a linear-time algorithm for implicit comparison of all pairs of models with profile hashing to enable efficient clustering of large data sets with a low memory footprint. the uqlust package is freely available under the gnu general public license at https://github.com/uqlust. uqlust represents a drastic reduction in the computational complexity and memory requirements with respect to existing clustering and model quality assessment methods for macromolecular structure analysis, while yielding results on par with traditional approaches for both proteins and rnas. the quickly growing number of experimentally resolved structures, and databases such as the protein data bank, also implies large scale structural similarity analyses to retrieve and classify macromolecular data. for example, hierarchical clustering of the entire pdb using profile hashing can be performed on a typical laptop, thus opening an avenue for structural explorations previously limited to dedicated resources. consequently, the computational cost of structure comparison and clustering for large sets of macromolecular structures has become a bottleneck that necessitates further algorithmic improvements and development of efficient software solutions. protein structurerna structureprofile hashinghierarchical clusteringmodel quality assessmentmacromolecular structure analysishttp://dx.doi.org/ /100000002national institutes of healthr21ai097936r01mh107487r21es024807u54hl127624p30es006096ul1tr001425meller jarek issue-copyright-statement© the author 2016
 advances in computing have enabled current protein and rna structure prediction and molecular simulation methods to dramatically increase their sampling of conformational spaces. the quickly growing number of experimentally resolved structures, and databases such as the protein data bank, also implies large scale structural similarity analyses to retrieve and classify macromolecular data. consequently, the computational cost of structure comparison and clustering for large sets of macromolecular structures has become a bottleneck that necessitates further algorithmic improvements and development of efficient software solutions.  uqlust is a versatile and easy-to-use tool for ultrafast ranking and clustering of macromolecular structures. uqlust makes use of structural profiles of proteins and nucleic acids, while combining a linear-time algorithm for implicit comparison of all pairs of models with profile hashing to enable efficient clustering of large data sets with a low memory footprint. in addition to ranking and clustering of large sets of models of the same protein or rna molecule, uqlust can also be used in conjunction with fragment-based profiles in order to cluster structures of arbitrary length. for example, hierarchical clustering of the entire pdb using profile hashing can be performed on a typical laptop, thus opening an avenue for structural explorations previously limited to dedicated resources. the uqlust package is freely available under the gnu general public license at https://github.com/uqlust.  uqlust represents a drastic reduction in the computational complexity and memory requirements with respect to existing clustering and model quality assessment methods for macromolecular structure analysis, while yielding results on par with traditional approaches for both proteins and rnas. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords protein structurerna structureprofile hashinghierarchical clusteringmodel quality assessmentmacromolecular structure analysishttp://dx.doi.org/ /100000002national institutes of healthr21ai097936r01mh107487r21es024807u54hl127624p30es006096ul1tr001425meller jarek issue-copyright-statement© the author 2016 