## 2 Results and Discussion
### Methods
#### 2.1.1 Algorithm
Each compound is checked for the presence of a fragment to form a bit vector. If the fragment is present, 1 is assigned to the corresponding component of the bit vector, otherwise the value is 0. In earlier studies [27], we found that a sphere with radius 2 is sufficient for molecular similarity and diversity calculations. On average, each compound in the studied databases has 35 unique fragments [20]. A fragment is hashed into the 12-byte variable [20] to form key values. These values are sorted and stored in memory to form dictionary of all fragments. One cannot get any connection matrix from hashed value, but, optionally, connection matrix can be stored at hard drive with corresponding hashed value. It was experimentally found, that large, diverse databases contain several hundreds of thousands of unique fragments. So, the dictionary never exceeds 12M RAM and this value does not affect the calculation performance. The use of the dictionary of a large size (some hundred thousands of  
Figure 3: Divisive clustering with \(Rd\)=0.1 (10-step clustering). fragments) instead of fixed-length fingerprint is the main difference from circular SciTegic fingerprints [28] which has fixed restricted length. The dictionary is formed during run-time when reading the database. Indexes of fragments in the dictionary are calculated and stored for each compound. To define similarity between two compounds, the numbers of identical and number of different indexes in the glossary are calculated. It allows considerable increasing of computer memory usage efficiency. Thus, 140 bytes of RAM are required on average to store screens for a single compound. Using this type of storing information allows PC RAM to upload the dataset of some millions of compounds. To find indexes of fragments for new compound quickly, the dictionary is sorted and bisection search algorithm is used. If a fragment is not found, it is added to dictionary. In this case re-sorting is required to use bisection search algorithm, which decreases performance. To improve the performance it was suggested [29] to re-sort dictionary after several fragments addition. Non-sorted fragments in dictionary are compared with probe value step-by-step. Optimal productivity is achieved by sorting after addition of 128 fragments approximately [29]  
The cosine measure was used to calculate similarities between compounds \(I\) and \(J\):  
\[SIMILARITY\left(I,J\right)=\frac{\sum_{K=1}^{F}M_{\;I}\left(K\right)\times M_{ \;J}\left(K\right)}{\sqrt{\sum_{K=1}^{F}M_{\;I}\left(K\right)^{2}\times\sum_{ K=1}^{F}M_{\;J}\left(K\right)^{2}}}\]  
where \(M_{I}\) and \(M_{J}\) are bit vectors for compounds \(I\) and \(J\), \(F\) is the number of components in the bit vector. Cosine coefficient allows the diversity sorting with fast centroid algorithm [30], but it is more rarely used than the commonly applied Tanimoto [31] metric. Cosine similarity coefficient can vary from 0 (totally dissimilar compounds) to 1 (identical compounds). This variability range is divided into several steps, the number of steps being user-defined parameter. For example, if the number of steps equals 10, then the similarity thresholds are 0.0, 0.1, 0.2...0.8, 0.9, 1.0. Several clusters are generated for each level. The similarity of each compound to a probe molecule in the cluster equals or exceeds the predefined similarity threshold. With the increasing similarity value, the cluster splits into several clusters forming a cluster tree. Diversity sorting is repeatedly performed in each cluster to select a set of probe molecules. One-time sorting of the input database may not be sufficient because of the order of compounds in the sorted set is changed after removal of selected compounds. Diversity sorting is a reiterated procedure. As a result of splitting clusters in building hierarchical tree, some compounds' similarity to the probe molecules may be below the predefined similarity threshold. Such compounds are joined with the set of probe molecules to form a new cluster; therefore the probe set can be expanded dynamically.