A Geometric Clustering Algorithm with Applications to Structural Data
SHUTAN XU, SHUXUE ZOU, and LINCONG WANG
An important feature of structural data, especially those from structural determination and protein-ligand docking programs, is that their distribution could be mostly uniform. Traditional clustering algorithms developed specifically for nonuniformly distributed data may not be adequate for their classification. Here we present a geometric partitional algorithm that could be applied to both uniformly and nonuniformly distributed data. The algorithm is a top-down approach that recursively selects the outliers as the seeds to form new clusters until all the structures within a cluster satisfy a classification criterion. The algorithm has been evaluated on a diverse set of real structural data and six sets of test data. The results show that it is superior to the previous algorithms for the clustering of structural data and is similar to or better than them for the classification of the test data. The algorithm should be especially useful for the identification of the best but minor clusters and for speeding up an iterative process widely used in NMR structure determination.
Key words: algorithms, distance geometry, drug design, protein structure. 1. INTRODUCTION
Recently, we have witnessed a rapid growth of not only DNA sequencing data but also three-dimensional (3D) structural data such as those from biomolecular nuclear magnetic resonance (NMR) spectroscopy and protein-ligand docking as well as molecular dynamics (MD) simulation and protein structure prediction. These techniques output not a single but an ensemble of structures. A variety of traditional clustering algorithms both of hierarchical and partitional ( Jain et al., 1999; Jain, 2010), being able to first assign the data points to groups (clusters) and then identify a representative for each cluster, have been applied to their analysis and visualization in order to discover or compare common structural features such as protein fold, binding site, and correct pose (May, 1999; Shao et al., 2007; Keller et al., 2010; Bottegoni et al., 2012; Adzhubei et al., 1995; Domingues et al., 2004; Sutcliffe, 1993; Downs and Barnard, 2002). However, it remains unclear which algorithm is most suitable for the clustering of 3D structural data because of the inherent difficulty associated with high dimensionality.* For example, a previous study concluded that there was no perfect ‘‘one size fits all’’ algorithm for the clustering of MD trajectories (Shao et al., 2007; and May, 1999) had questioned whether a hierarchical approach is appropriate for the clustering of structural data by forcing them into a dendrogram.
College of Computer Science and Technology, Jilin University, Changchun, P.R. China. *A structure with Na atoms has dimension d= 3Na.
JOURNAL OF COMPUTATIONAL BIOLOGY
Volume 22, Number 5, 2015 # Mary Ann Liebert, Inc.
DOI: 10.1089/cmb.2014.0162 436
An important feature of structural data, especially those from NMR structural determination and proteinligand docking, is that their distribution could be mostly uniform, and thus may not be properly described by a Gaussian mixture model. Traditional clustering algorithms developed specifically for nonuniformly distributed data may not be adequate for their classification. In this article, we present a novel geometric partitional algorithm that could be applied to both uniformly and nonuniformly distributed data. The algorithm is a top-down approach that recursively partitions all the data points of a previously generated cluster into c new clusters where c is a user-specified number. It stops and then outputs a final set of clusters that satisfy the classification criterion that no metric distances between any pair of data points in any cluster are larger than a certain value. Compared with the previous clustering algorithms, the salient features of our geometric partitional algorithm are (a) it uses the global information in the beginning, (b) it can handle both uniformly and nonuniformly distributed data, and (c) it is deterministic.
We have applied the algorithm to the classification of a diverse set of data: the intermediate structures from an NMR structure determination project, poses from protein-ligand docking, and MD trajectories from an abinitio protein folding simulation (data not shown), as well as six sets of test data that have been used widely for the evaluation of clustering algorithms. We have also compared the algorithm with the following five different clustering algorithms: common nearest-neighbor, bipartition, complete-link, average-link, and kmedoids, on both real structural data and test data. The results show that our algorithm classifies the structural data with a higher accuracy than a k-medoids does. For the structural data sets, though the final set of clusters from our algorithm may be similar to those from a hierarchical algorithm such as complete-link or averagelink, and to those from a nearest-neighbor or bipartition algorithm, the structures assigned to the same cluster by our algorithm are more uniform in terms of their structural and physical properties.
More importantly, our algorithm outperforms the previous ones in singling out the minor clusters with ‘‘good’’ properties (the best or correct clusters) that are often to be overlooked or even discarded by other criteria used for the selection of representative structures. Furthermore, the comparisons of our algorithm with the above five algorithms on the test data sets confirm its generality: the algorithm performs as well as or better than the previous ones in their classification. The rest of the article is organized as follows. In section 2 we first present the algorithm and then describe the real structural data sets. In section 3 we present the results of applying both our algorithm and five previous algorithms to the structural data sets for the identification of the clusters with good scores, and discuss the significance of the geometric algorithm for speeding up the iterative NMR structure determination process and for the selection of accurate docking poses. In section 4 we compare our clustering algorithm with the previous ones from both the theoretical and practical perspectives.