deps/kb_meme/meme-5.0.1/src/momo-modl.c
/**
 * Creates and stores the motifs found using the modl
 * algorithm for a given mod.
 */
Creates and stores the motifs found using the modl
algorithm for a given mod.
Creates and stores the motifs found using the modl algorithm for a given mod .
void create_modl_motifs(SUMMARY_T* summary,
                        MOMO_OPTIONS_T* options,
                        MOD_INFO_T * mod_info,
                        SEQ_T** all_sequences,
                        int num_sequences) {
  const char* alph_letters = summary->alph_letters;
  int i;
  int j;
  int k;
  int max_motifs = options->max_motifs;
  int max_iterations = options->max_iterations;
  int max_no_decrease = options->max_no_decrease;
  MATRIX_T* bg_freqs = NULL;
  bg_freqs = get_count_matrix(bg_freqs, mod_info->bg_seq_list, NULL, options, summary);
  for (i = 0; i < options->width; ++i ) {
    for (j = 0; j < strlen(alph_letters); ++j) {
      set_matrix_cell(i,j,get_matrix_cell(i,j,bg_freqs)/arraylst_size(mod_info->bg_seq_list),bg_freqs);
    }
  }
  int no_decrease = 0;
  ARRAYLST_T* regexmotifs = arraylst_create();
  ARRAYLST_T* best_ops = arraylst_create();
  double minDL = compute_MDL(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
  MODL_STEP_T* init_step = init_modl_step(INIT_STEP, 0, 0, 0, 0, minDL);
  arraylst_add(init_step, best_ops);
  int n_tests = 0;
  while (arraylst_size(best_ops)-1 <= max_iterations &&
         (((MODL_STEP_T*) arraylst_peek(best_ops))->score == minDL || no_decrease < max_no_decrease)) {
    MODL_STEP_T* merge_step = get_best_merge(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    MODL_STEP_T* last_op = arraylst_peek(best_ops);
    if (merge_step->score < last_op->score) {
      arraylst_add(merge_step, best_ops);
      do_step(merge_step, regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
      if (merge_step->score > minDL) { 
        no_decrease++;
      } else {
        no_decrease = 0;
        minDL = merge_step->score;
      }
    }
    MODL_STEP_T* add_step = get_best_add(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    MODL_STEP_T* append_step = get_best_append(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    MODL_STEP_T* replace_step = get_best_replace(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    MODL_STEP_T* best_add_append_replace = add_step;
    if (arraylst_size(regexmotifs) > 0) {
      if (append_step->score < best_add_append_replace->score) {
        best_add_append_replace = append_step;
      }
      if (replace_step->score < best_add_append_replace->score) {
        best_add_append_replace = replace_step;
      }
    }
    if (best_add_append_replace->score > minDL) {
      no_decrease++;
    } else {
      no_decrease = 0;
      minDL = best_add_append_replace->score;
    }
    arraylst_add(best_add_append_replace, best_ops);
    do_step(best_add_append_replace, regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    MODL_STEP_T* remove_step = get_best_remove(regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
    last_op = arraylst_peek(best_ops);
    if (remove_step->score < best_add_append_replace->score) {
      arraylst_add(remove_step, best_ops);
      do_step(remove_step, regexmotifs, bg_freqs, max_motifs, options, summary, mod_info);
      if (remove_step->score > minDL) {
        no_decrease++;
      } else {
        no_decrease = 0;
        minDL = remove_step->score;
      }
    }
    n_tests++;
  }
  mod_info->modl_ops = best_ops;
  ARRAYLST_T* finalmotifs = get_best_motif_list(best_ops, minDL, bg_freqs, max_motifs, summary, options, mod_info);
  set_motifinfo_list(finalmotifs, minDL, bg_freqs, max_motifs, summary, options, mod_info, n_tests);
  for (i = 0; i < arraylst_size(regexmotifs); ++i) {
    REGEX_MOTIF_T* regexmotif = arraylst_get(i, regexmotifs);
    cleanup_regexmotif(regexmotif);
  }
  arraylst_destroy(NULL, regexmotifs);
  for (i = 0; i < arraylst_size(finalmotifs); ++i) {
    REGEX_MOTIF_T* regexmotif = arraylst_get(i, finalmotifs);
    cleanup_regexmotif(regexmotif);
  }
  arraylst_destroy(NULL, finalmotifs);
  free_matrix(bg_freqs);
}
void create_modl_motifs ( SUMMARY_T * summary , MOMO_OPTIONS_T * options , MOD_INFO_T * mod_info , SEQ_T * * all_sequences , int num_sequences ) { const char * alph_letters = summary -> alph_letters ; int i ; int j ; int k ; int max_motifs = options -> max_motifs ; int max_iterations = options -> max_iterations ; int max_no_decrease = options -> max_no_decrease ; MATRIX_T * bg_freqs = NULL ; bg_freqs = get_count_matrix ( bg_freqs , mod_info -> bg_seq_list , NULL , options , summary ) ; for ( i = 0 ; i < options -> width ; ++ i ) { for ( j = 0 ; j < strlen ( alph_letters ) ; ++ j ) { set_matrix_cell ( i , j , get_matrix_cell ( i , j , bg_freqs ) / arraylst_size ( mod_info -> bg_seq_list ) , bg_freqs ) ; } } int no_decrease = 0 ; ARRAYLST_T * regexmotifs = arraylst_create ( ) ; ARRAYLST_T * best_ops = arraylst_create ( ) ; double minDL = compute_MDL ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * init_step = init_modl_step ( INIT_STEP , 0 , 0 , 0 , 0 , minDL ) ; arraylst_add ( init_step , best_ops ) ; int n_tests = 0 ; while ( arraylst_size ( best_ops ) - 1 <= max_iterations && ( ( ( MODL_STEP_T * ) arraylst_peek ( best_ops ) ) -> score == minDL || no_decrease < max_no_decrease ) ) { MODL_STEP_T * merge_step = get_best_merge ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * last_op = arraylst_peek ( best_ops ) ; if ( merge_step -> score < last_op -> score ) { arraylst_add ( merge_step , best_ops ) ; do_step ( merge_step , regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; if ( merge_step -> score > minDL ) { no_decrease ++ ; } else { no_decrease = 0 ; minDL = merge_step -> score ; } } MODL_STEP_T * add_step = get_best_add ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * append_step = get_best_append ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * replace_step = get_best_replace ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * best_add_append_replace = add_step ; if ( arraylst_size ( regexmotifs ) > 0 ) { if ( append_step -> score < best_add_append_replace -> score ) { best_add_append_replace = append_step ; } if ( replace_step -> score < best_add_append_replace -> score ) { best_add_append_replace = replace_step ; } } if ( best_add_append_replace -> score > minDL ) { no_decrease ++ ; } else { no_decrease = 0 ; minDL = best_add_append_replace -> score ; } arraylst_add ( best_add_append_replace , best_ops ) ; do_step ( best_add_append_replace , regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; MODL_STEP_T * remove_step = get_best_remove ( regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; last_op = arraylst_peek ( best_ops ) ; if ( remove_step -> score < best_add_append_replace -> score ) { arraylst_add ( remove_step , best_ops ) ; do_step ( remove_step , regexmotifs , bg_freqs , max_motifs , options , summary , mod_info ) ; if ( remove_step -> score > minDL ) { no_decrease ++ ; } else { no_decrease = 0 ; minDL = remove_step -> score ; } } n_tests ++ ; } mod_info -> modl_ops = best_ops ; ARRAYLST_T * finalmotifs = get_best_motif_list ( best_ops , minDL , bg_freqs , max_motifs , summary , options , mod_info ) ; set_motifinfo_list ( finalmotifs , minDL , bg_freqs , max_motifs , summary , options , mod_info , n_tests ) ; for ( i = 0 ; i < arraylst_size ( regexmotifs ) ; ++ i ) { REGEX_MOTIF_T * regexmotif = arraylst_get ( i , regexmotifs ) ; cleanup_regexmotif ( regexmotif ) ; } arraylst_destroy ( NULL , regexmotifs ) ; for ( i = 0 ; i < arraylst_size ( finalmotifs ) ; ++ i ) { REGEX_MOTIF_T * regexmotif = arraylst_get ( i , finalmotifs ) ; cleanup_regexmotif ( regexmotif ) ; } arraylst_destroy ( NULL , finalmotifs ) ; free_matrix ( bg_freqs ) ; }
Creates and stores the motifs found using the modl
 algorithm for a given mod.
Creates and stores the motifs found using the modl algorithm for a given mod .
// background frequencies // NOTE: The MoDL implementation from the Ritz Paper does something funny (potential bug?) // no decrease is checked after every time a op is added to best_ops, but the check // for size of ops < max iterations is only checked once everytime in the loop... // NOTE2: Each round through the loop has 3 potential places to add an op... This is // inconsistent with what is described by the paper, which seems to imply you can only have // one op per round through the loop.... It also makes this while loop // unnecessarily long and complicated... //   1. merging (optional) //   2. add, append(+remove), replace(+remove) //   3. remove (optional) // NOTE3: The possible operations are different than as described in the paper... // NOTE4: I dont understand why score of last element == minDL even a condition for loop terminiation ?? // Try merge existing motifs // Do the merge if it decreases the DL (compared to the last DL) // yes... I do realize that >= makes more sense... but apparently this is what modl does ? // Add, append, replace [append and replace have options to remove as well] // Figure out which is the best of the three and apply. // Perform the best_add_append_replace regardless of whether or not there is a decrease in DL... // Try remove a motif if it helps decrease the DL... // Do the remove if it decreases the DL (compared to the last DL) // cleanup