deps/kb_meme/meme-5.0.1/src/starts.c
/**
 * global_search
 *
 * Perform substring search, followed by optional branching search. Modifies
 * sp_matrix as a result.
 *
 */
global_search
Perform substring search, followed by optional branching search. Modifies
sp_matrix as a result.
global_search Perform substring search followed by optional branching search . Modifies sp_matrix as a result .
static void global_search (
  SP_MATRIX *sp_matrix,
  DATASET *primary, 
  DATASET *control, 
  MODEL *model 
) {
  HASH_TABLE evaluated_seed_ht = NULL;
  if (primary->branch_params->w_branch == true ||
     primary->branch_params->point_branch != NO_POINT_B) {
     Calculate rough upper bound on the number of novel seeds that could be
     found by substring search and branching search...
     NOTE: The same branching factor is currently used for width-branching and
      x-branching alike. This was done because w-branching is not a default
      parameter, and so its performance has not been optimised.
    int bfactor = primary->branch_params->bfactor;
    int n_central_w = get_num_central_widths(sp_matrix);
    int n_nsites = sp_get_num_cols(sp_matrix);
     Get the number of letters that can be branched to moves tried in point
     branching:
    int point_br_alen;
    if (primary->branch_params->point_branch == NORMAL) {
      point_br_alen = alph_size_core(primary->alph);
    } else if (primary->branch_params->point_branch == ALL) {
      point_br_alen = alph_size_wild(primary->alph);
    } else if (primary->branch_params->point_branch == NO_POINT_B) {
      point_br_alen = 0;
    } else {
      point_br_alen = 1;  X only branching
    }
     Calculate max novel seeds generated for each seed branched from:
    double avg_w =
      (((double)get_max_width(sp_matrix) + get_min_width(sp_matrix))/2);
    int seeds_per_branch = (avg_w*point_br_alen);
    if (primary->branch_params->w_branch) {
      seeds_per_branch = seeds_per_branch + (2 * alph_size_wild(primary->alph));
    }
     Calculate approximate upper bound on number of novel seeds produced:
    int max_novel =
      (primary->total_res*n_central_w) +
      3*primary->main_hs*bfactor*n_central_w*n_nsites*seeds_per_branch;
     make the number odd, in the hope of landing on a prime number
     because prime numbers apparently cause less hash collisions
    if (max_novel % 2 == 0) max_novel += 1;
     Placing an upper limit on the amount of memory used by the hashtable bins.
     Note that a dynamically-resized hashtable could also be used to deal with
     memory usage concerns. This did not appear necessary in our studies.
    int n_bins = MIN(max_novel, MAX_BINS);
    evaluated_seed_ht = hash_create(n_bins, NULL);
  }
   Perform substring search:
  substring_search(sp_matrix, primary, control, evaluated_seed_ht, model);
   Use a new BRANCH_PARAMS object to control branching:
  BRANCH_PARAMS branch_params;
  if (primary->branch_params->w_branch == true) {
     User requested width-branching => Set up branching parameters accordingly
     and commence branching:
    branch_params.point_branch = NO_POINT_B;
    branch_params.w_branch = true;
    branch_params.bfactor = primary->branch_params->bfactor;
    branching_search(&branch_params, model, primary, sp_matrix, evaluated_seed_ht);
    transfer_final_scores(primary->alph, sp_matrix);
  }
  if (primary->branch_params->point_branch != NO_POINT_B) {
     User requested point-wise branching => Set up branching parameters
     accordingly and commence branching:
    branch_params.point_branch = primary->branch_params->point_branch;
    branch_params.w_branch = false;
    branch_params.bfactor = primary->branch_params->bfactor;
    branching_search(&branch_params, model, primary, sp_matrix, evaluated_seed_ht);
    transfer_final_scores(primary->alph, sp_matrix);
  }
   Branching has finished => free the memory associated with the hash table.
  if (evaluated_seed_ht) hash_destroy(evaluated_seed_ht);
   At this stage, the top of each of the heaps of the s_points contains the
   (hopefully) best starting point for the respective combination of w and
   nsites0. Set the attributes in each of the s_point objects accordingly:
  transfer_final_scores(primary->alph, sp_matrix);
}
static void global_search ( SP_MATRIX * sp_matrix , DATASET * primary , DATASET * control , MODEL * model ) { HASH_TABLE evaluated_seed_ht = NULL ; if ( primary -> branch_params -> w_branch == true || primary -> branch_params -> point_branch != NO_POINT_B ) { int bfactor = primary -> branch_params -> bfactor ; int n_central_w = get_num_central_widths ( sp_matrix ) ; int n_nsites = sp_get_num_cols ( sp_matrix ) ; int point_br_alen ; if ( primary -> branch_params -> point_branch == NORMAL ) { point_br_alen = alph_size_core ( primary -> alph ) ; } else if ( primary -> branch_params -> point_branch == ALL ) { point_br_alen = alph_size_wild ( primary -> alph ) ; } else if ( primary -> branch_params -> point_branch == NO_POINT_B ) { point_br_alen = 0 ; } else { point_br_alen = 1 ; } double avg_w = ( ( ( double ) get_max_width ( sp_matrix ) + get_min_width ( sp_matrix ) ) / 2 ) ; int seeds_per_branch = ( avg_w * point_br_alen ) ; if ( primary -> branch_params -> w_branch ) { seeds_per_branch = seeds_per_branch + ( 2 * alph_size_wild ( primary -> alph ) ) ; } int max_novel = ( primary -> total_res * n_central_w ) + 3 * primary -> main_hs * bfactor * n_central_w * n_nsites * seeds_per_branch ; if ( max_novel % 2 == 0 ) max_novel += 1 ; int n_bins = MIN ( max_novel , MAX_BINS ) ; evaluated_seed_ht = hash_create ( n_bins , NULL ) ; } substring_search ( sp_matrix , primary , control , evaluated_seed_ht , model ) ; BRANCH_PARAMS branch_params ; if ( primary -> branch_params -> w_branch == true ) { branch_params . point_branch = NO_POINT_B ; branch_params . w_branch = true ; branch_params . bfactor = primary -> branch_params -> bfactor ; branching_search ( & branch_params , model , primary , sp_matrix , evaluated_seed_ht ) ; transfer_final_scores ( primary -> alph , sp_matrix ) ; } if ( primary -> branch_params -> point_branch != NO_POINT_B ) { branch_params . point_branch = primary -> branch_params -> point_branch ; branch_params . w_branch = false ; branch_params . bfactor = primary -> branch_params -> bfactor ; branching_search ( & branch_params , model , primary , sp_matrix , evaluated_seed_ht ) ; transfer_final_scores ( primary -> alph , sp_matrix ) ; } if ( evaluated_seed_ht ) hash_destroy ( evaluated_seed_ht ) ; transfer_final_scores ( primary -> alph , sp_matrix ) ; }
global_search
 Perform substring search, followed by optional branching search.
global_search Perform substring search followed by optional branching search .
// Matrix of spoints each with different n and w values // Primary sequences // Control sequences // The motif model (nascent) // Allocate memory for a hash table recording which seeds have already // been evaluated... // Maximum number of entries in hash table (after branching search has // also been performed) is: // (Number of seeds evaluated in substring search) + // (Number of seeds evaluated during branching search). // // Calculate rough upper bound on the number of novel seeds that could be // found by substring search and branching search... // NOTE: The same branching factor is currently used for width-branching and //  x-branching alike. This was done because w-branching is not a default //  parameter, and so its performance has not been optimised. // Get the number of letters that can be branched to moves tried in point // branching: // X only branching // Calculate max novel seeds generated for each seed branched from: // Calculate approximate upper bound on number of novel seeds produced: // make the number odd, in the hope of landing on a prime number // because prime numbers apparently cause less hash collisions // Placing an upper limit on the amount of memory used by the hashtable bins. // Note that a dynamically-resized hashtable could also be used to deal with // memory usage concerns. This did not appear necessary in our studies. // Perform substring search: // Use a new BRANCH_PARAMS object to control branching: // User requested width-branching => Set up branching parameters accordingly // and commence branching: // User requested point-wise branching => Set up branching parameters // accordingly and commence branching: // Branching has finished => free the memory associated with the hash table. // At this stage, the top of each of the heaps of the s_points contains the // (hopefully) best starting point for the respective combination of w and // nsites0. Set the attributes in each of the s_point objects accordingly: