Loading...
Searching...
No Matches
binaryFingerprintMethods.h
Go to the documentation of this file.
// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//
#ifndef BALL_STRUCTURE_BINARYFINGERPRINTMETHODS_H
#define BALL_STRUCTURE_BINARYFINGERPRINTMETHODS_H
#ifndef BALL_COMMON_H
# include <BALL/common.h>
#endif
#ifndef BALL_DATATYPE_OPTIONS_H
# include <BALL/DATATYPE/options.h>
#endif
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/incremental_components.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/thread.hpp>
#include <boost/unordered_set.hpp>
#include <map>
#include <set>
#include <vector>
namespace BALL
{
class BALL_EXPORT BinaryFingerprintMethods
{
struct InvertedIndex;
typedef std::vector<InvertedIndex*> InvertedIndices;
typedef std::vector<std::vector<unsigned short> > FingerprintFeatures;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> SimilarityGraph;
typedef boost::graph_traits<SimilarityGraph>::vertex_descriptor Vertex;
typedef boost::graph_traits<SimilarityGraph>::vertices_size_type VertexIndex;
typedef boost::disjoint_sets<Vertex*, VertexIndex*, boost::find_with_full_path_compression> DisjointSet;
public:
struct BALL_EXPORT Option
{
static const String BLOCKSIZE;
static const String SIM_CUTOFF;
static const String PRECISION;
static const String STORE_NN;
static const String MAX_CLUSTERS;
static const String N_THREADS;
static const String VERBOSITY;
};
struct BALL_EXPORT Default
{
static const unsigned short BLOCKSIZE;
static const float SIM_CUTOFF;
static const float PRECISION;
static const unsigned int MAX_CLUSTERS;
static const bool STORE_NN;
static const unsigned int N_THREADS;
static const int VERBOSITY;
};
BinaryFingerprintMethods();
BinaryFingerprintMethods(const Options& options);
BinaryFingerprintMethods(const Options& options, const FingerprintFeatures& lib_features);
BinaryFingerprintMethods(const Options& options, const FingerprintFeatures& lib_features, const FingerprintFeatures& query_features);
BinaryFingerprintMethods(const BinaryFingerprintMethods& bfm);
virtual ~BinaryFingerprintMethods();
BinaryFingerprintMethods& operator = (const BinaryFingerprintMethods& bfm);
static bool parseBinaryFingerprint(const String& fprint, std::vector<unsigned short>& features, unsigned int fp_type, const char* delim=",");
bool setLibraryFeatures(const FingerprintFeatures& lib_features);
bool setQueryFeatures(const FingerprintFeatures& query_features);
unsigned int getTargetLibrarySize() const;
unsigned int getQueryLibrarySize() const;
const Options& getOptions() const;
void setVerbosityLevel(const int verbosity);
bool cutoffSearch(const float sim_cutoff, const String& outfile_name);
bool connectedComponents(const std::vector<unsigned int>& selection,
std::vector<std::vector<unsigned int> >& ccs,
std::vector<std::vector<std::pair<unsigned int, float> > >& nn_data,
const float cutoff,
const bool store_nns = false);
bool averageLinkageClustering(const std::vector<unsigned int>& selection,
std::vector<std::pair<unsigned int, float> >& nn_data,
std::map<unsigned int, std::vector<unsigned int> >& cluster_selection);
bool calculateSelectionMedoid(const std::vector<unsigned int>& selection, unsigned int& medoid_index, std::vector<float>& avg_sims);
private:
struct ThreadData
{
LongSize first;
LongSize last;
float nn_sim;
unsigned int blocksize;
unsigned int dataset_size;
unsigned int active_iids_size;
unsigned short* cc_row;
unsigned short** cc_matrix;
float* float_array;
double** dprec_matrix;
unsigned int* uint_array;
String outfile_name;
};
struct FeatureList
{
// FeatureID which corresponds in principle to the index of a bit in a 2D fingerprint.
unsigned short feature_id;
// Array which stores the sorted list of all molecules which all share the associated feature_id.
// Molecules are only represented by their positions in the Block they belong to.
unsigned short* block_positions;
};
struct InvertedIndex
{
// Number of molecules in the block.
unsigned int n_molecules;
// Array which stores the number of features of every molecule in the InvertedIndex
unsigned short* n_features;
// Array which stores the ID of the parent cluster to which the molecule at the InvertedIndex position belongs to.
unsigned int* parent_clusters;
// Array of FeatureLists implemented as a skip list.
FeatureList* feature_skip_list;
};
struct Cluster
{
// Molecule ID for leaf nodes. Otherwise internal Cluster ID.
unsigned int c_id;
// Cluster index [0, n_molecules-1] is used to map from 2D matrix to 1D array.
unsigned int c_index;
// Number of leaf nodes inside in the corresponding cluster.
unsigned int c_size;
// Left child. NULL if cluster is a leaf.
Cluster* l_child;
// Right child. NULL if cluster is a leaf.
Cluster* r_child;
// Pointer to the clusters current nearest neigbour.
Cluster* nn;
// Flag for various purposes.
bool is_rnn;
// Sum of all intra-cluster pairwise similarities within this cluster. Used finally for KGS penalty calculation.
double sim_sum;
// Pointer to predecessor cluster in the Nearest Neighbour Chain. NULL if not member of the Nearest Neighbour Chain.
Cluster* predecessor;
// Similarity to predecessor in Nearest Neighbour Chain. 0.0 if not member of Nearest Neighbour Chain.
float predecessor_sim;
// Sum of all inter-cluster pairwise similarities of clusters nn_chain[i] and nn_chain[i-1]. 0.0 if not member of the NNChain.
double predecessor_sim_sum;
// Inverted indices of all leaf molecules within this cluster.
boost::unordered_set<InvertedIndex*> c_members;
// Vector of pointers to FingerprintFeatures in lib_features_ of all leaf molecules within this cluster.
std::vector<const std::vector<unsigned short>* > leaf_members;
};
enum clustering_methods_
{
STORED_DATA_PARALLEL,
STORED_MATRIX
};
DisjointSet* ds;
std::vector<Vertex> parent;
std::vector<VertexIndex> rank;
Options options_;
unsigned int n_threads_;
const FingerprintFeatures* lib_features_;
InvertedIndices lib_iindices_;
const FingerprintFeatures* query_features_;
InvertedIndices query_iindices_;
boost::thread* threads_;
boost::mutex out_mutex_;
ThreadData* thread_data_;
unsigned short blocksize_;
LongSize cc_matrix_size_;
float cutoff_;
float precision_;
bool store_nns_;
LongSize n_comparisons_;
LongSize n_comparisons_backup_;
int verbosity_;
std::vector<Cluster*> leaf_clusters_;
std::map<float, std::vector<Cluster*> > internal_clusters_;
std::vector<Cluster*> vec_actives_;
std::vector<Cluster*> vec_inactives_;
float* sim_matrix_;
double* dprec_sim_matrix_;
std::vector<std::pair<std::vector<InvertedIndex*>, unsigned int> > active_iids_;
unsigned int active_iids_size_;
Cluster* nn_chain_tip_;
unsigned int nn_chain_size_;
std::vector<Cluster*>::iterator current_nn_;
float current_nn_sim_;
unsigned short clustering_method_;
unsigned int n_clusters_;
unsigned int max_clusters_;
void setup(const Options& options);
void clear();
void assign(const BinaryFingerprintMethods& bfm);
bool checkInputData(const std::vector<unsigned int>& selection) const;
void createThreadData(const unsigned int blocksize, const unsigned int dataset_size, const unsigned int active_iids_size);
void destroyThreadData();
InvertedIndex* createInvertedIndex(const std::vector<std::pair<const std::vector<unsigned short>*, unsigned int> >& members);
void destroyInvertedIndex(InvertedIndex* ii);
void destroyInvertedIndices(InvertedIndices& ii_destroy);
void createInvertedIndices(const std::vector<std::pair<const std::vector<unsigned short>*, unsigned int> >& molecules, InvertedIndices& ii_target);
void setBlockSize(const unsigned short blocksize);
void arrayToUpperTriangluarMatrix(LongSize& row, LongSize& col, const LongSize array_index) const;
void arrayToStrictUpperTriangularMatrix(LongSize& row, LongSize& col, const LongSize array_index) const;
LongSize strictUpperTriangularMatrixToArray(const LongSize row, const LongSize col) const;
bool getNextComparisonIndex(LongSize& index);
bool checkSimilaritySwitch(const float a_sim, const float b_sim, const unsigned int a_id, const unsigned int b_id) const;
void calculateCommonCounts_1_1(const FeatureList* ii1, const FeatureList* ii2, unsigned short& cc_count);
void calculateCommonCounts_1_N(const FeatureList* ii1, const FeatureList* ii2, unsigned short* cc_row);
void calculateCommonCounts_M_N(const InvertedIndex* ii_1, const InvertedIndex* ii_2, unsigned short** cc_matrix);
void cutoffSearchSimilarities(const unsigned int query_index, const unsigned int lib_index, unsigned short** cc_matrix, File& outfile);
void cutoffSearchThread(const unsigned int thread_id);
typedef void (BinaryFingerprintMethods::*PairwiseSimilaritiesBase)(const unsigned int ii1_index, const unsigned int ii2_index, ThreadData* t_data);
PairwiseSimilaritiesBase pairwiseSimilaritiesBase;
void pairwiseSimilaritiesNearestNeighbours(const unsigned int ii1_index, const unsigned int ii2_index, ThreadData* t_data);
void pairwiseSimilaritiesStoredMatrix(const unsigned int ii1_index, const unsigned int ii2_index, ThreadData* t_data);
void pairwiseSimilaritiesConnectedComponents(const unsigned int ii1_index, const unsigned int ii2_index, ThreadData* t_data);
void pairwiseSimilaritiesMedoids(const unsigned int ii1_index, const unsigned int ii2_index, ThreadData* t_data);
bool pairwiseSimilarities(const std::vector<unsigned int>& selection, std::vector<std::pair<unsigned int, float> >& nn_data);
void pairwiseSimilaritiesThread(const unsigned int thread_id);
void calculateParallelSimilaritiesActives(const InvertedIndex* ii1, const InvertedIndex* ii2, unsigned short** cc_matrix, double** sim_matrix);
void calculateParallelSimilaritiesActivesThread(const unsigned int thread_id);
void calculateParallelSimilarities(const InvertedIndex* ii1, const InvertedIndex* ii2, unsigned short** cc_matrix, double** sim_matrix);
void calculateParallelSimilaritiesThread(const unsigned int thread_id);
void similarityUpdateAverageLinkage(const Cluster* merged_cluster, const Cluster* current);
void similarityUpdateAverageLinkageThread(const unsigned int thread_id, const Cluster* merged_cluster);
void clusterSimilaritySum_1_N(const InvertedIndex* ii1, const InvertedIndex* ii2, const unsigned short* cc_row, double& sim_sum);
void clusterSimilaritySum_M_N(const InvertedIndex* ii1, const InvertedIndex* ii2, unsigned short** cc_matrix, double& sim_sum);
void similarityMatrixFromClustersThread(const unsigned int thread_id);
void averageLinkageParallel(Cluster*& root);
void NNChainCore(Cluster*& root);
void clusterSelectionKGS(std::map<unsigned int, std::vector<unsigned int> >& cluster_selection);
void enumerateClusterMembers(Cluster* cl, unsigned int cluster_id);
void nextNearestNeighbour();
void moveNearestNeighbour();
Cluster* mergeClusters(Cluster* c1, Cluster* c2, double sim_sum);
Cluster* createCluster();
void switchStorageMethod();
void finalizeClustering();
};
} // namespace BALL
#endif // BALL_STRUCTURE_BINARYFINGERPRINTMETHODS_H
BALL_EXPORT
#define BALL_EXPORT
Definition COMMON/global.h:50
BALL::BinaryFingerprintMethods::BinaryFingerprintMethods
BinaryFingerprintMethods(const Options &options)
BALL::BinaryFingerprintMethods::setQueryFeatures
bool setQueryFeatures(const FingerprintFeatures &query_features)
BALL::BinaryFingerprintMethods::calculateSelectionMedoid
bool calculateSelectionMedoid(const std::vector< unsigned int > &selection, unsigned int &medoid_index, std::vector< float > &avg_sims)
BALL::BinaryFingerprintMethods::setVerbosityLevel
void setVerbosityLevel(const int verbosity)
BALL::BinaryFingerprintMethods::parseBinaryFingerprint
static bool parseBinaryFingerprint(const String &fprint, std::vector< unsigned short > &features, unsigned int fp_type, const char *delim=",")
BALL::BinaryFingerprintMethods::BinaryFingerprintMethods
BinaryFingerprintMethods(const Options &options, const FingerprintFeatures &lib_features)
BALL::BinaryFingerprintMethods::cutoffSearch
bool cutoffSearch(const float sim_cutoff, const String &outfile_name)
BALL::BinaryFingerprintMethods::getOptions
const Options & getOptions() const
BALL::BinaryFingerprintMethods::BinaryFingerprintMethods
BinaryFingerprintMethods(const BinaryFingerprintMethods &bfm)
BALL::BinaryFingerprintMethods::connectedComponents
bool connectedComponents(const std::vector< unsigned int > &selection, std::vector< std::vector< unsigned int > > &ccs, std::vector< std::vector< std::pair< unsigned int, float > > > &nn_data, const float cutoff, const bool store_nns=false)
BALL::BinaryFingerprintMethods::BinaryFingerprintMethods
BinaryFingerprintMethods(const Options &options, const FingerprintFeatures &lib_features, const FingerprintFeatures &query_features)
BALL::BinaryFingerprintMethods::~BinaryFingerprintMethods
virtual ~BinaryFingerprintMethods()
BALL::BinaryFingerprintMethods::getTargetLibrarySize
unsigned int getTargetLibrarySize() const
BALL::BinaryFingerprintMethods::averageLinkageClustering
bool averageLinkageClustering(const std::vector< unsigned int > &selection, std::vector< std::pair< unsigned int, float > > &nn_data, std::map< unsigned int, std::vector< unsigned int > > &cluster_selection)
BALL::BinaryFingerprintMethods::BinaryFingerprintMethods
BinaryFingerprintMethods()
BALL::BinaryFingerprintMethods::getQueryLibrarySize
unsigned int getQueryLibrarySize() const
BALL::BinaryFingerprintMethods::setLibraryFeatures
bool setLibraryFeatures(const FingerprintFeatures &lib_features)
BALL::Options
Definition options.h:48
BALL::String
Definition string.h:57
common.h
BALL
Definition constants.h:13
BALL::LongSize
BALL_ULONG64_TYPE LongSize
Definition COMMON/global.h:192
options.h
BALL::BinaryFingerprintMethods::Default
Definition binaryFingerprintMethods.h:137
BALL::BinaryFingerprintMethods::Default::PRECISION
static const float PRECISION
Definition binaryFingerprintMethods.h:140
BALL::BinaryFingerprintMethods::Default::STORE_NN
static const bool STORE_NN
Definition binaryFingerprintMethods.h:142
BALL::BinaryFingerprintMethods::Default::SIM_CUTOFF
static const float SIM_CUTOFF
Definition binaryFingerprintMethods.h:139
BALL::BinaryFingerprintMethods::Default::VERBOSITY
static const int VERBOSITY
Definition binaryFingerprintMethods.h:144
BALL::BinaryFingerprintMethods::Default::MAX_CLUSTERS
static const unsigned int MAX_CLUSTERS
Definition binaryFingerprintMethods.h:141
BALL::BinaryFingerprintMethods::Default::BLOCKSIZE
static const unsigned short BLOCKSIZE
Definition binaryFingerprintMethods.h:138
BALL::BinaryFingerprintMethods::Default::N_THREADS
static const unsigned int N_THREADS
Definition binaryFingerprintMethods.h:143
BALL::BinaryFingerprintMethods::Option
Definition binaryFingerprintMethods.h:95
BALL::BinaryFingerprintMethods::Option::VERBOSITY
static const String VERBOSITY
Definition binaryFingerprintMethods.h:130
BALL::BinaryFingerprintMethods::Option::PRECISION
static const String PRECISION
Definition binaryFingerprintMethods.h:109
BALL::BinaryFingerprintMethods::Option::N_THREADS
static const String N_THREADS
Definition binaryFingerprintMethods.h:125
BALL::BinaryFingerprintMethods::Option::BLOCKSIZE
static const String BLOCKSIZE
Definition binaryFingerprintMethods.h:99
BALL::BinaryFingerprintMethods::Option::SIM_CUTOFF
static const String SIM_CUTOFF
Definition binaryFingerprintMethods.h:104
BALL::BinaryFingerprintMethods::Option::STORE_NN
static const String STORE_NN
Definition binaryFingerprintMethods.h:114
BALL::BinaryFingerprintMethods::Option::MAX_CLUSTERS
static const String MAX_CLUSTERS
Definition binaryFingerprintMethods.h:120