title: UQlust: combining profile hashing with linear-time ranking for efficient clustering and analysis of big macromolecular data.
abstract: BACKGROUND
  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.
  
  
  RESULTS
  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 .
  
  
  CONCLUSIONS
  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.
authors.affiliation: Department of Informatics, Faculty of Physics, Astronomy and Informatics, Nicolaus Copernicus University, Grudziadzka 5, 87-100, Torun, Poland. raad@is.umk.pl.
authors.forename: Rafal
authors.initials: R
authors.lastname: Adamczak
authors.affiliation: Department of Informatics, Faculty of Physics, Astronomy and Informatics, Nicolaus Copernicus University, Grudziadzka 5, 87-100, Torun, Poland. jmeller@cchmc.org.|Departments of Environmental Health and Electrical Engineering & Computing Systems, University of Cincinnati, Cincinnati, USA. jmeller@cchmc.org.|Division of Biomedical Informatics, Cincinnati Children's Hospital Medical Center, Cincinnati, USA. jmeller@cchmc.org.
authors.forename: Jarek
authors.identifier: http://orcid.org/0000-0002-1162-8253
authors.initials: J
authors.lastname: Meller
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D003627:Data Interpretation, Statistical; D030562:Databases, Protein; D017433:Protein Structure, Secondary; D011506:Proteins / Q000737:chemistry*; D012313:RNA / Q000737:chemistry*; D012984:Software
chemical_list: D011506:Proteins; D012313:RNA
keywords: Hierarchical clustering; Macromolecular structure analysis; Model quality assessment; Profile hashing; Protein structure; RNA structure