hmmer-3.3/easel/esl_swat.c
/* Function:  esl_swat_Score()
 * Incept:    SRE, Fri Apr 13 16:40:15 2007 [Janelia]
 *
 * Purpose:   Implements Smith/Waterman local sequence alignment, recovering
 *            only a score, not an alignment. Query sequence <x> of length <L>
 *            is aligned to subject sequence <y> of length <M>, using
 *            a scoring system composed of residue alignment scores in matrix
 *            <S>, a gap-open score <gop>, and a gap-extend score <gex>.
 *            
 *            A gap of $k$ residues is scored as <gop> $\times (k-1)$
 *            <gex>.  That is, the gap-open score is applied to the
 *            first residue in the gap, and the gap-extend penalty is
 *            applied to each remaining residue. Additionally, both
 *            <gop> and <gex> should be negative numbers.
 *
 * Returns:   <eslOK> on success, and the raw alignment score is returned in
 *            <ret_sc>. 
 *
 * Throws:    (no abnormal error conditions)
 */


Implements Smith/Waterman local sequence alignment, recovering
only a score, not an alignment. Query sequence  of length 
is aligned to subject sequence  of length , using
a scoring system composed of residue alignment scores in matrix
, a gap-open score , and a gap-extend score .

A gap of $k$ residues is scored as  $\times (k-1)$
.  That is, the gap-open score is applied to the
first residue in the gap, and the gap-extend penalty is
applied to each remaining residue. Additionally, both
 and  should be negative numbers.

 on success, and the raw alignment score is returned in
.

(no abnormal error conditions)
Implements Smith / Waterman local sequence alignment recovering only a score not an alignment . Query sequence of length is aligned to subject sequence of length using a scoring system composed of residue alignment scores in matrix a gap - open score and a gap - extend score . A gap of $k$ residues is scored as $ \ times ( k - 1 ) $ . That is the gap - open score is applied to the first residue in the gap and the gap - extend penalty is applied to each remaining residue . Additionally both and should be negative numbers . on success and the raw alignment score is returned in . ( no abnormal error conditions )
int
esl_swat_Score(ESL_DSQ *x, int L, ESL_DSQ *y, int M, ESL_SCOREMATRIX *S, int gop, int gex, int *ret_sc)
{
  int    status;
  int    i,j;
  int  **rowmem = NULL;
  int   *mc, *mp, *ixc, *ixp, *iyc, *iyp;
  int    maxsc;
  ESL_ALLOC(rowmem,    sizeof(int *) * 6); 
  rowmem[0] = NULL;
  ESL_ALLOC(rowmem[0], sizeof(int) * 6 * (L+1));
  for (i = 1; i < 6; i++) rowmem[i] = rowmem[0] + i*(L+1);
  rowmem[1][0] = 0;
  rowmem[3][0] = eslSWAT_PROHIBIT;
  rowmem[5][0] = eslSWAT_PROHIBIT;
  for (j = 0; j <= L; j++) { 
    rowmem[0][j] = 0;
    rowmem[2][j] = eslSWAT_PROHIBIT;
    rowmem[4][j] = eslSWAT_PROHIBIT;
  }
  maxsc = 0;
  for (i = 1; i <= M; i++)	
    {
      if (i%2) { mp = rowmem[0]; mc = rowmem[1]; ixp = rowmem[2]; ixc = rowmem[3]; iyp = rowmem[4]; iyc = rowmem[5]; }
      else     { mc = rowmem[0]; mp = rowmem[1]; ixc = rowmem[2]; ixp = rowmem[3]; iyc = rowmem[4]; iyp = rowmem[5]; }
      for (j = 1; j <= L; j++)	
	{
	  mc[j] = 0;
	  if (mp[j-1]  > mc[j]) mc[j] = mp[j-1];
	  if (ixp[j-1] > mc[j]) mc[j] = ixp[j-1];
	  if (iyp[j-1] > mc[j]) mc[j] = iyp[j-1];
	  mc[j] += S->s[x[j]][y[i]]; 	 
	  if (mc[j] > maxsc) maxsc = mc[j];
	  ixc[j] = mc[j-1] + gop;
	  if (ixc[j-1] + gex > ixc[j]) ixc[j] = ixc[j-1] + gex;
	  iyc[j] = mp[j] + gop;
	  if (iyp[j] + gex > iyc[j]) iyc[j] = iyp[j] + gex;
	}
    }
  *ret_sc = maxsc;
  free(rowmem[0]);
  free(rowmem);
  return eslOK;
 ERROR:
  *ret_sc = 0;
  if (rowmem != NULL) {
    if (rowmem[0] != NULL) free(rowmem[0]);
    free(rowmem);
  }
  return status;
}
int esl_swat_Score ( ESL_DSQ * x , int L , ESL_DSQ * y , int M , ESL_SCOREMATRIX * S , int gop , int gex , int * ret_sc ) { int status ; int i , j ; int * * rowmem = NULL ; int * mc , * mp , * ixc , * ixp , * iyc , * iyp ; int maxsc ; ESL_ALLOC ( rowmem , sizeof ( int * ) * 6 ) ; rowmem [ 0 ] = NULL ; ESL_ALLOC ( rowmem [ 0 ] , sizeof ( int ) * 6 * ( L + 1 ) ) ; for ( i = 1 ; i < 6 ; i ++ ) rowmem [ i ] = rowmem [ 0 ] + i * ( L + 1 ) ; rowmem [ 1 ] [ 0 ] = 0 ; rowmem [ 3 ] [ 0 ] = eslSWAT_PROHIBIT ; rowmem [ 5 ] [ 0 ] = eslSWAT_PROHIBIT ; for ( j = 0 ; j <= L ; j ++ ) { rowmem [ 0 ] [ j ] = 0 ; rowmem [ 2 ] [ j ] = eslSWAT_PROHIBIT ; rowmem [ 4 ] [ j ] = eslSWAT_PROHIBIT ; } maxsc = 0 ; for ( i = 1 ; i <= M ; i ++ ) { if ( i % 2 ) { mp = rowmem [ 0 ] ; mc = rowmem [ 1 ] ; ixp = rowmem [ 2 ] ; ixc = rowmem [ 3 ] ; iyp = rowmem [ 4 ] ; iyc = rowmem [ 5 ] ; } else { mc = rowmem [ 0 ] ; mp = rowmem [ 1 ] ; ixc = rowmem [ 2 ] ; ixp = rowmem [ 3 ] ; iyc = rowmem [ 4 ] ; iyp = rowmem [ 5 ] ; } for ( j = 1 ; j <= L ; j ++ ) { mc [ j ] = 0 ; if ( mp [ j - 1 ] > mc [ j ] ) mc [ j ] = mp [ j - 1 ] ; if ( ixp [ j - 1 ] > mc [ j ] ) mc [ j ] = ixp [ j - 1 ] ; if ( iyp [ j - 1 ] > mc [ j ] ) mc [ j ] = iyp [ j - 1 ] ; mc [ j ] += S -> s [ x [ j ] ] [ y [ i ] ] ; if ( mc [ j ] > maxsc ) maxsc = mc [ j ] ; ixc [ j ] = mc [ j - 1 ] + gop ; if ( ixc [ j - 1 ] + gex > ixc [ j ] ) ixc [ j ] = ixc [ j - 1 ] + gex ; iyc [ j ] = mp [ j ] + gop ; if ( iyp [ j ] + gex > iyc [ j ] ) iyc [ j ] = iyp [ j ] + gex ; } } * ret_sc = maxsc ; free ( rowmem [ 0 ] ) ; free ( rowmem ) ; return eslOK ; ERROR : * ret_sc = 0 ; if ( rowmem != NULL ) { if ( rowmem [ 0 ] != NULL ) free ( rowmem [ 0 ] ) ; free ( rowmem ) ; } return status ; }
Function:  esl_swat_Score()
 Incept:    SRE, Fri Apr 13 16:40:15 2007 [Janelia]
Function : esl_swat_Score () Incept : SRE Fri Apr 13 16 : 40 : 15 2007 [ Janelia ]
/* DP lattice is organized in rows (0) 1..i..M with target running vertically;
   * columns (0) 1..j..L with query running horizontally.
   */ /* Allocation; 
   * we need two rows of length (L+1) for each of three matrices, M, IX, IY. 
   * in the future, optimize by providing this from the caller. 
   */ /* Initializations.
   */ /* for each position in target... */ /* for each position in query... */ /* Match score at mc[j] aligns xj,yi. We can reach here from M (mp[j-1]), IX (ixp[j-1]), or IY (iyp[j-1]) */ /* IX score at ixc[j] aligns xj to gap (horizontal move). 
	   * We reach here from mc[j-1] (gap-open) or ixc[j-1] (gap-extend).
	   */ /* analogously for vertical move to iyc. */