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