deps/kb_meme/meme-5.0.1/src/spamo-scan.c
/**************************************************************************
 * Scans specified regions of a sequence with a PSSM and its reverse 
 * complement and returns a list of matches (positions) that score above
 * the specified threshold.  If best_hit_only is true,
 * it returns the  single best match or randomly selects among ties.
 * The strand of each match is encoded in its position: negative
 * means opposite strand.
 **************************************************************************/
Scans specified regions of a sequence with a PSSM and its reverse
complement and returns a list of matches (positions) that score above
the specified threshold.  If best_hit_only is true,
it returns the  single best match or randomly selects among ties.
The strand of each match is encoded in its position: negative
means opposite strand.
Scans specified regions of a sequence with a PSSM and its reverse complement and returns a list of matches ( positions ) that score above the specified threshold . If best_hit_only is true it returns the single best match or randomly selects among ties . The strand of each match is encoded in its position : negative means opposite strand .
static inline ARRAY_T* best_in_region(
  PSSM_T *pssm,             
  PSSM_T *pssm_rc,          
  SEQUENCE_T *sequence,     
  int *regions,             
  double score_threshold,   
  int *hits,                
  int hits_size,            
  bool best_hit_only   
) {
  int i, region_index, position_index, motif_offset, motif_length, region_end;
  int aindex, success, hit_count;
  char c;
  double lo, lo_rc; 
  double *hits_lo;
  ATYPE best_lo;
  ALPH_T *alph;
  MATRIX_T *pssm_matrix, *pssm_rc_matrix;
  bool revcomp;
  char *seq = sequence->data;
  assert(pssm != NULL);
  assert(pssm_rc == NULL || get_pssm_w(pssm) == get_pssm_w(pssm_rc));
  assert(seq != NULL);
  assert(regions != NULL);
  revcomp = (pssm_rc != NULL);
  hits_lo = best_hit_only ? (double *)mm_malloc(hits_size * sizeof(double)) : NULL;
  alph = pssm->alph;
  best_lo = -BIG;
  hit_count = 0;
  motif_length = get_pssm_w(pssm);
  pssm_matrix = pssm->matrix;
  pssm_rc_matrix = (revcomp ? pssm_rc->matrix : NULL);
  for (region_index = 0; regions[region_index] != -1; region_index += 2) {
    assert(regions[region_index] >= 0);
    assert(region_index == 0 || regions[region_index-1] < regions[region_index]);
    region_end = regions[region_index+1] - motif_length + 1;
    for (position_index = regions[region_index]; position_index <= region_end; ++position_index) {
      success = true; 
      lo = 0; 
      lo_rc = 0;
      for (motif_offset = 0; motif_offset < motif_length; ++motif_offset) {
        c = seq[position_index+motif_offset];
        if(!alph_is_core(alph, c)) {
          success = false;
          break;
        }
        aindex = alph_index(alph, c);
        lo += get_matrix_cell(motif_offset, aindex, pssm_matrix);
        if (revcomp) lo_rc += get_matrix_cell(motif_offset, aindex, pssm_rc_matrix); 
      }
      if (success) {
        lo = get_unscaled_pssm_score(lo, pssm);
        if (revcomp) lo_rc = get_unscaled_pssm_score(lo_rc, pssm);
        double hit_lo;
        int position;
        if (lo >= score_threshold || (revcomp && lo_rc >= score_threshold)) {
          if (revcomp && (lo_rc > lo || (lo_rc == lo && (drand_mt() > 0.5) )))  {
            hit_lo = lo_rc;
            position = -(position_index + 1);   
          } else {
            hit_lo = lo;
            position = position_index + 1;      
          }
          hits[hit_count] = position;         
          if (best_hit_only) hits_lo[hit_count] = hit_lo;     
          if (hit_lo > best_lo) {
            best_lo = hit_lo;
          }
          hit_count++;
        } 
      } 
    } 
  } 
  if (best_lo >= score_threshold) {
    ARRAY_T* hits_array = allocate_array(hit_count);
    for (i=0; i<hit_count; i++) set_array_item(i, (ATYPE)(hits[i]), hits_array); 
    if (best_hit_only) {        
      int nbest = 0;
      int tail = hit_count-1;
      for (i=0; i<hit_count; i++) {
        int index = (hits_lo[i] == best_lo) ? nbest++ : tail--;
        set_array_item(index, (ATYPE)(hits[i]), hits_array);
      }
      if (nbest > 1) {
        int best_index = nbest * drand_mt();
        ATYPE tmp_best_hit = get_array_item(best_index, hits_array);
        ATYPE tmp_first_hit = get_array_item(0, hits_array);
        set_array_item(0, tmp_best_hit, hits_array);
        set_array_item(best_index, tmp_first_hit, hits_array);
      }
    } else {    
      for (i=0; i<hit_count; i++) set_array_item(i, (ATYPE)(hits[i]), hits_array); 
    }
    myfree(hits_lo);
    return hits_array;
  } else {
    return NULL;
  }
}
static inline ARRAY_T * best_in_region ( PSSM_T * pssm , PSSM_T * pssm_rc , SEQUENCE_T * sequence , int * regions , double score_threshold , int * hits , int hits_size , bool best_hit_only ) { int i , region_index , position_index , motif_offset , motif_length , region_end ; int aindex , success , hit_count ; char c ; double lo , lo_rc ; double * hits_lo ; ATYPE best_lo ; ALPH_T * alph ; MATRIX_T * pssm_matrix , * pssm_rc_matrix ; bool revcomp ; char * seq = sequence -> data ; assert ( pssm != NULL ) ; assert ( pssm_rc == NULL || get_pssm_w ( pssm ) == get_pssm_w ( pssm_rc ) ) ; assert ( seq != NULL ) ; assert ( regions != NULL ) ; revcomp = ( pssm_rc != NULL ) ; hits_lo = best_hit_only ? ( double * ) mm_malloc ( hits_size * sizeof ( double ) ) : NULL ; alph = pssm -> alph ; best_lo = - BIG ; hit_count = 0 ; motif_length = get_pssm_w ( pssm ) ; pssm_matrix = pssm -> matrix ; pssm_rc_matrix = ( revcomp ? pssm_rc -> matrix : NULL ) ; for ( region_index = 0 ; regions [ region_index ] != -1 ; region_index += 2 ) { assert ( regions [ region_index ] >= 0 ) ; assert ( region_index == 0 || regions [ region_index - 1 ] < regions [ region_index ] ) ; region_end = regions [ region_index + 1 ] - motif_length + 1 ; for ( position_index = regions [ region_index ] ; position_index <= region_end ; ++ position_index ) { success = true ; lo = 0 ; lo_rc = 0 ; for ( motif_offset = 0 ; motif_offset < motif_length ; ++ motif_offset ) { c = seq [ position_index + motif_offset ] ; if ( ! alph_is_core ( alph , c ) ) { success = false ; break ; } aindex = alph_index ( alph , c ) ; lo += get_matrix_cell ( motif_offset , aindex , pssm_matrix ) ; if ( revcomp ) lo_rc += get_matrix_cell ( motif_offset , aindex , pssm_rc_matrix ) ; } if ( success ) { lo = get_unscaled_pssm_score ( lo , pssm ) ; if ( revcomp ) lo_rc = get_unscaled_pssm_score ( lo_rc , pssm ) ; double hit_lo ; int position ; if ( lo >= score_threshold || ( revcomp && lo_rc >= score_threshold ) ) { if ( revcomp && ( lo_rc > lo || ( lo_rc == lo && ( drand_mt ( ) > 0.5 ) ) ) ) { hit_lo = lo_rc ; position = - ( position_index + 1 ) ; } else { hit_lo = lo ; position = position_index + 1 ; } hits [ hit_count ] = position ; if ( best_hit_only ) hits_lo [ hit_count ] = hit_lo ; if ( hit_lo > best_lo ) { best_lo = hit_lo ; } hit_count ++ ; } } } } if ( best_lo >= score_threshold ) { ARRAY_T * hits_array = allocate_array ( hit_count ) ; for ( i = 0 ; i < hit_count ; i ++ ) set_array_item ( i , ( ATYPE ) ( hits [ i ] ) , hits_array ) ; if ( best_hit_only ) { int nbest = 0 ; int tail = hit_count - 1 ; for ( i = 0 ; i < hit_count ; i ++ ) { int index = ( hits_lo [ i ] == best_lo ) ? nbest ++ : tail -- ; set_array_item ( index , ( ATYPE ) ( hits [ i ] ) , hits_array ) ; } if ( nbest > 1 ) { int best_index = nbest * drand_mt ( ) ; ATYPE tmp_best_hit = get_array_item ( best_index , hits_array ) ; ATYPE tmp_first_hit = get_array_item ( 0 , hits_array ) ; set_array_item ( 0 , tmp_best_hit , hits_array ) ; set_array_item ( best_index , tmp_first_hit , hits_array ) ; } } else { for ( i = 0 ; i < hit_count ; i ++ ) set_array_item ( i , ( ATYPE ) ( hits [ i ] ) , hits_array ) ; } myfree ( hits_lo ) ; return hits_array ; } else { return NULL ; } }
Scans specified regions of a sequence with a PSSM and its reverse
 complement and returns a list of matches (positions) that score above
 the specified threshold.
Scans specified regions of a sequence with a PSSM and its reverse complement and returns a list of matches ( positions ) that score above the specified threshold .
// the motif score matrix // the revese complement motif score matrix // the sequence to score // the regions to scan // the minimum score considered a hit // the pre-allocated hits cache should be large enough to store a hit for every position // the size of the pre-allocatted hits cache. // old SpaMo: used best hit only //basic checks on parameters // check if we're scanning revcomp // init hits list //get the alphabet //initilize the best position: 0 means no match; +ve is match on 5` strand; -ve is match on 3` strand // to make this work an origin of 1 is used. // get the motif length // get the pssm matrixes //scan regions, check for overlaps and those not in sorted order //error checks, so nothing is too suprising //scan a region //scan a position // assume success //reset sums to zero // Check for gaps and ambiguity codes at this site //note these scores are scaled // now revert the scaled lo scores to unscaled // Save hit if it meets threshold. // Determine score and the strand; break ties randomly; negative means reverse strand. //if (revcomp && (lo_rc > lo || (lo_rc == lo && ( ((double)rand()/RAND_MAX) > 0.5) )))  { // negative strand // positive strand // Save all hits, keeping track of index of best one. // Save hit. // Save hit logodds if necessary. // score above threshold // found hit (no ambigs) // position // region // Return an array of all the hits; put a (randomly chosen) best hit first in array. // If best_hit_only, randomly choose among ties for best hit. // put best hits first // Put ties in front of hits_array // Now randomly choose a best hit and move to front of hits_array if there is more than one. //int best_index = nbest * ((double)rand()/RAND_MAX); // otherwise, order of hits doesn't matter