Agglomerative clustering of fragment 3D structures based on pairwise RMSD

International audienceIn structural biology, many fragment-based 3D modeling methods require fragment libraries. They represent the whole set of possible 3D structures (conformations) observed experimentally for each fragment, with a chosen precision. In docking, for this precision, it is important to have as few prototypes as possible inside the libraries.One way to create a library is to cluster all observed conformations in order to retain only the representative prototypes. The most common measure of 3D similarity is the Root Mean Squared Deviation (RMSD) applied after a structural superposition. But this RMSD after alignment is not a metric, which means that distance-based clustering is not applicable.Current alternative methods, based on an approximation of the RMSD or internal coordinates, retrieve too many prototypes.We propose a new type of clustering which meets our needs, based on hierarchical agglomerative clustering. The linkage criterion for agglomerating two clusters is the radius of the minimal ball enclosing them. The prototypes are the centers of the balls at the end of theclustering process. They constitute a cover of all possible conformations within a given RMSD. We discuss the complexity issues associated with solving the quadratic programming problems that produce the minimal enclosing balls