The mutant-generating algorithm is described in details in the Computational Methods section

a sorted list. In contrast to the hierarchical algorithms that have the quadratic asymptotic running time with respect to the number of objects, k-means produces a number of partitions for every k in a linear time complexity with respect to any aspect of the problem size [54]. The complexity of k-means algorithm is O(nkh), where the number of clusters (k) and the number of interactions (h) are usually less than the number of objects (n). Several works explore the relative accuracy of various clustering algorithms in extracting the right number of clusters from generated data [43]. According to Hartigan et al. [18], we cannot point the best clustering method since different approaches are right for different purposes. Chen and Lonardi [15] say that the more popular methods for clustering MD conformations are agglomerative hierarchical clustering since its linkage method is able to use the attributes for describing the chemical structures. More specifically, linkage is the only method able to PLOS ONE | DOI:10.1371/journal.pone.0133172 July 28, 2015 21 / 25 An Approach for Clustering MD Trajectory Using Cavity-Based Features calculate the dissimilarities between two clusters of chemical structures using Euclidean distance. Alternatively, Shao et al. [16] found that UPGMA, k-means, and SOM outperformed COBWEB, Bayesian, and other hierarchical clustering methods by using the pairwise RMSD distance as measure of similarity. Although our analyses also show hierarchical agglomerative methods as the best choices for all data Oleandrin PubMed ID:http://www.ncbi.nlm.nih.gov/pubmed/19666987 sets, the k-means and k-medoids PubMed ID:http://www.ncbi.nlm.nih.gov/pubmed/19665973 algorithms appear as the worst choice for all data sets. Each study has its own way to generate data and to identify the best clustering algorithm and, therefore, comes with i