NCBI C++ ToolKit
Functions
aa_ungapped.c File Reference

Functions to iterate over seed hits and perform ungapped extensions. More...

#include <algo/blast/core/aa_ungapped.h>
#include <algo/blast/core/blast_aalookup.h>
#include <algo/blast/core/blast_aascan.h>
#include <algo/blast/core/blast_util.h>
+ Include dependency graph for aa_ungapped.c:

Go to the source code of this file.

Go to the SVN repository for this file.

Functions

static Int2 s_BlastAaWordFinder_TwoHit (const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, const LookupTableWrap *lookup_wrap, Blast_ExtendWord *ewp, Int4 **matrix, const BlastInitialWordParameters *word_params, BlastQueryInfo *query_info, BlastOffsetPair *offset_pairs, Int4 array_size, BlastInitHitList *ungapped_hsps, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits and trigger two-hit extensions. More...
 
static Int2 s_BlastRPSWordFinder_TwoHit (const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, const LookupTableWrap *lookup_wrap, Blast_ExtendWord *ewp, Int4 **matrix, Int4 cutoff, Int4 dropoff, BlastInitHitList *ungapped_hsps, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits and trigger two-hit extensions (specialized for RPS blast). More...
 
static Int2 s_BlastAaWordFinder_OneHit (const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, const LookupTableWrap *lookup_wrap, Blast_ExtendWord *ewp, Int4 **matrix, const BlastInitialWordParameters *word_params, BlastQueryInfo *query_info, BlastOffsetPair *offset_pairs, Int4 array_size, BlastInitHitList *ungapped_hsps, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits and trigger one-hit extensions. More...
 
static Int2 s_BlastRPSWordFinder_OneHit (const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, const LookupTableWrap *lookup_wrap, Blast_ExtendWord *ewp, Int4 **matrix, Int4 cutoff, Int4 dropoff, BlastInitHitList *ungapped_hsps, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits and trigger one-hit extensions (spcialized for RPS blast). More...
 
static Int4 s_BlastAaExtendOneHit (Int4 **matrix, const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, Int4 s_off, Int4 q_off, Int4 dropoff, Int4 *hsp_q, Int4 *hsp_s, Int4 *hsp_len, Int4 word_size, Boolean use_pssm, Int4 *s_last_off)
 Perform a one-hit extension. More...
 
static Int4 s_BlastAaExtendTwoHit (Int4 **matrix, const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, Int4 s_left_off, Int4 s_right_off, Int4 q_right_off, Int4 dropoff, Int4 *hsp_q, Int4 *hsp_s, Int4 *hsp_len, Boolean use_pssm, Int4 word_size, Boolean *right_extend, Int4 *s_last_off)
 Perform a two-hit extension. More...
 
Int2 BlastAaWordFinder (BLAST_SequenceBlk *subject, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, LookupTableWrap *lut_wrap, Int4 **matrix, const BlastInitialWordParameters *word_params, Blast_ExtendWord *ewp, BlastOffsetPair *offset_pairs, Int4 offset_array_size, BlastInitHitList *init_hitlist, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits (blastp) More...
 
Int2 BlastRPSWordFinder (BLAST_SequenceBlk *subject, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, LookupTableWrap *lut_wrap, Int4 **matrix, const BlastInitialWordParameters *word_params, Blast_ExtendWord *ewp, BlastOffsetPair *offset_pairs, Int4 offset_array_size, BlastInitHitList *init_hitlist, BlastUngappedStats *ungapped_stats)
 Scan a subject sequence for word hits (rpsblast and rpstblastn) More...
 
static Int4 s_BlastAaExtendRight (Int4 **matrix, const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, Int4 s_off, Int4 q_off, Int4 dropoff, Int4 *length, Int4 maxscore, Int4 *s_last_off)
 Beginning at s_off and q_off in the subject and query, respectively, extend to the right until the cumulative score becomes negative or drops by at least 'dropoff', or the end of at least one sequence is reached. More...
 
static Int4 s_BlastAaExtendLeft (Int4 **matrix, const BLAST_SequenceBlk *subject, const BLAST_SequenceBlk *query, Int4 s_off, Int4 q_off, Int4 dropoff, Int4 *length, Int4 maxscore)
 Beginning at s_off and q_off in the subject and query, respectively, extend to the left until the cumulative score drops by at least 'dropoff', or the end of at least one sequence is reached. More...
 
static Int4 s_BlastPSSMExtendRight (Int4 **matrix, const BLAST_SequenceBlk *subject, Int4 query_size, Int4 s_off, Int4 q_off, Int4 dropoff, Int4 *length, Int4 maxscore, Int4 *s_last_off)
 Identical to BlastAaExtendRight, except the score matrix is position-specific. More...
 
static Int4 s_BlastPSSMExtendLeft (Int4 **matrix, const BLAST_SequenceBlk *subject, Int4 s_off, Int4 q_off, Int4 dropoff, Int4 *length, Int4 maxscore)
 Identical to BlastAaExtendLeft, except the query is represented by a position-specific score matrix. More...
 

Detailed Description

Functions to iterate over seed hits and perform ungapped extensions.

Definition in file aa_ungapped.c.

Function Documentation

◆ BlastAaWordFinder()

Int2 BlastAaWordFinder ( BLAST_SequenceBlk subject,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
LookupTableWrap lookup,
Int4 **  matrix,
const BlastInitialWordParameters word_params,
Blast_ExtendWord ewp,
BlastOffsetPair offset_pairs,
Int4  offset_array_size,
BlastInitHitList init_hitlist,
BlastUngappedStats ungapped_stats 
)

Scan a subject sequence for word hits (blastp)

Parameters
subjectthe subject sequence [in]
querythe query sequence [in]
query_infoconcatenated query information [in]
lookupthe lookup table [in]
matrixthe substitution matrix [in]
word_paramsword parameters, needed for cutoff and dropoff [in]
ewpextend parameters, needed for diagonal tracking [in]
offset_pairsArray for storing query and subject offsets. [in]
offset_array_sizethe number of elements in each offset array [in]
init_hitlisthsps resulting from the ungapped extension [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 200 of file aa_ungapped.c.

References Blast_InitHitListSortByScore(), Blast_ExtendWord::diag_table, BLAST_DiagTable::multiple_hits, query, s_BlastAaWordFinder_OneHit(), s_BlastAaWordFinder_TwoHit(), and subject.

Referenced by s_BlastSetUpAuxStructures().

◆ BlastRPSWordFinder()

Int2 BlastRPSWordFinder ( BLAST_SequenceBlk subject,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
LookupTableWrap lookup,
Int4 **  matrix,
const BlastInitialWordParameters word_params,
Blast_ExtendWord ewp,
BlastOffsetPair offset_pairs,
Int4  offset_array_size,
BlastInitHitList init_hitlist,
BlastUngappedStats ungapped_stats 
)

Scan a subject sequence for word hits (rpsblast and rpstblastn)

Parameters
subjectthe subject sequence [in]
querythe query sequence [in]
query_infoconcatenated query information [in]
lookupthe lookup table [in]
matrixthe substitution matrix [in]
word_paramsword parameters, needed for cutoff and dropoff [in]
ewpextend parameters, needed for diagonal tracking [in]
offset_pairsArray for storing query and subject offsets. [in]
offset_array_sizethe number of elements in each offset array [in]
init_hitlisthsps resulting from the ungapped extension [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 238 of file aa_ungapped.c.

References BLAST_FrameToContext(), Blast_InitHitListSortByScore(), context, BlastUngappedCutoffs::cutoff_score, BlastInitialWordParameters::cutoffs, Blast_ExtendWord::diag_table, eBlastTypeRpsTblastn, BLAST_DiagTable::multiple_hits, NUM_FRAMES, query, s_BlastRPSWordFinder_OneHit(), s_BlastRPSWordFinder_TwoHit(), subject, and BlastUngappedCutoffs::x_dropoff.

Referenced by s_BlastSetUpAuxStructures().

◆ s_BlastAaExtendLeft()

static Int4 s_BlastAaExtendLeft ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
Int4  s_off,
Int4  q_off,
Int4  dropoff,
Int4 length,
Int4  maxscore 
)
static

Beginning at s_off and q_off in the subject and query, respectively, extend to the left until the cumulative score drops by at least 'dropoff', or the end of at least one sequence is reached.

Parameters
matrixthe substitution matrix [in]
subjectsubject sequence [in]
queryquery sequence [in]
s_offsubject offset [in]
q_offquery offset [in]
dropoffthe X dropoff parameter [in]
lengththe length of the computed extension [out]
maxscorethe best running score from a previous extension; the running score of the current extension must exceed this value if the extension is to be of nonzero size [in]
Returns
The score of the extension

Definition at line 886 of file aa_ungapped.c.

References i, MIN, n, query, and subject.

Referenced by s_BlastAaExtendOneHit(), and s_BlastAaExtendTwoHit().

◆ s_BlastAaExtendOneHit()

static Int4 s_BlastAaExtendOneHit ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
Int4  s_off,
Int4  q_off,
Int4  dropoff,
Int4 hsp_q,
Int4 hsp_s,
Int4 hsp_len,
Int4  word_size,
Boolean  use_pssm,
Int4 s_last_off 
)
static

Perform a one-hit extension.

Beginning at the specified hit, extend to the left, then extend to the right.

Parameters
matrixthe substitution matrix [in]
subjectsubject sequence [in]
queryquery sequence [in]
s_offsubject offset [in]
q_offquery offset [in]
dropoffX dropoff parameter [in]
hsp_qthe offset in the query where the HSP begins [out]
hsp_sthe offset in the subject where the HSP begins [out]
hsp_lenthe length of the HSP [out]
word_sizenumber of letters in the initial word hit [in]
use_pssmTRUE if the scoring matrix is position-specific [in]
s_last_offthe rightmost subject offset examined [out]
Returns
the score of the hsp.

Definition at line 1020 of file aa_ungapped.c.

References i, query, s_BlastAaExtendLeft(), s_BlastAaExtendRight(), s_BlastPSSMExtendLeft(), s_BlastPSSMExtendRight(), and subject.

Referenced by s_BlastAaWordFinder_OneHit(), and s_BlastRPSWordFinder_OneHit().

◆ s_BlastAaExtendRight()

static Int4 s_BlastAaExtendRight ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
Int4  s_off,
Int4  q_off,
Int4  dropoff,
Int4 length,
Int4  maxscore,
Int4 s_last_off 
)
static

Beginning at s_off and q_off in the subject and query, respectively, extend to the right until the cumulative score becomes negative or drops by at least 'dropoff', or the end of at least one sequence is reached.

Parameters
matrixthe substitution matrix [in]
subjectsubject sequence [in]
queryquery sequence [in]
s_offsubject offset [in]
q_offquery offset [in]
dropoffthe X dropoff parameter [in]
lengththe length of the computed extension [out]
maxscorethe score derived from a previous left extension [in]
s_last_offthe rightmost subject offset examined [out]
Returns
The score of the extension

Definition at line 831 of file aa_ungapped.c.

References i, MIN, n, query, and subject.

Referenced by s_BlastAaExtendOneHit(), and s_BlastAaExtendTwoHit().

◆ s_BlastAaExtendTwoHit()

static Int4 s_BlastAaExtendTwoHit ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
Int4  s_left_off,
Int4  s_right_off,
Int4  q_right_off,
Int4  dropoff,
Int4 hsp_q,
Int4 hsp_s,
Int4 hsp_len,
Boolean  use_pssm,
Int4  word_size,
Boolean right_extend,
Int4 s_last_off 
)
static

Perform a two-hit extension.

Given two hits L and R, begin at R and extend to the left. If we do not reach L, abort the extension. Otherwise, begin at R and extend to the right.

Parameters
matrixthe substitution matrix [in]
subjectsubject sequence [in]
queryquery sequence [in]
s_left_offleft subject offset [in]
s_right_offright subject offset [in]
q_right_offright query offset [in]
dropoffX dropoff parameter [in]
hsp_qthe offset in the query where the HSP begins [out]
hsp_sthe offset in the subject where the HSP begins [out]
hsp_lenthe length of the HSP [out]
use_pssmTRUE if the scoring matrix is position-specific [in]
word_sizenumber of letters in one word [in]
right_extendset to TRUE if an extension to the right happened [out]
s_last_offthe rightmost subject offset examined [out]
Returns
the score of the hsp.

Definition at line 1089 of file aa_ungapped.c.

References FALSE, i, MAX, query, s_BlastAaExtendLeft(), s_BlastAaExtendRight(), s_BlastPSSMExtendLeft(), s_BlastPSSMExtendRight(), subject, and TRUE.

Referenced by s_BlastAaWordFinder_TwoHit(), and s_BlastRPSWordFinder_TwoHit().

◆ s_BlastAaWordFinder_OneHit()

static Int2 s_BlastAaWordFinder_OneHit ( const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
const LookupTableWrap lookup_wrap,
Blast_ExtendWord ewp,
Int4 **  matrix,
const BlastInitialWordParameters word_params,
BlastQueryInfo query_info,
BlastOffsetPair offset_pairs,
Int4  array_size,
BlastInitHitList ungapped_hsps,
BlastUngappedStats ungapped_stats 
)
static

Scan a subject sequence for word hits and trigger one-hit extensions.

Parameters
subjectthe subject sequence
querythe query sequence
lookup_wrapthe lookup table
ewpStructure containing the diagonal array [in]
matrixthe substitution matrix [in]
word_paramsstructure containing per-context cutoff information [in]
query_infostructure containing context ranges [in]
offset_pairsArray for storing query and subject offsets. [in]
array_sizethe number of elements in each offset array
ungapped_hspshsps resulting from the ungapped extensions [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 713 of file aa_ungapped.c.

References ASSERT, Blast_ExtendWordExit(), Blast_UngappedStatsUpdate(), BlastSaveInitHsp(), BSearchContextInfo(), BlastUngappedCutoffs::cutoff_score, BlastInitialWordParameters::cutoffs, BLAST_DiagTable::diag_mask, Blast_ExtendWord::diag_table, eAaLookupTable, FALSE, BLAST_DiagTable::hit_level_array, i, DiagStruct::last_hit, lookup(), LookupTableWrap::lut, LookupTableWrap::lut_type, NULL, BLAST_DiagTable::offset, query, s_BlastAaExtendOneHit(), subject, BlastInitHitList::total, and BlastUngappedCutoffs::x_dropoff.

Referenced by BlastAaWordFinder().

◆ s_BlastAaWordFinder_TwoHit()

static Int2 s_BlastAaWordFinder_TwoHit ( const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
const LookupTableWrap lookup_wrap,
Blast_ExtendWord ewp,
Int4 **  matrix,
const BlastInitialWordParameters word_params,
BlastQueryInfo query_info,
BlastOffsetPair offset_pairs,
Int4  array_size,
BlastInitHitList ungapped_hsps,
BlastUngappedStats ungapped_stats 
)
static

Scan a subject sequence for word hits and trigger two-hit extensions.

Parameters
subjectthe subject sequence [in]
querythe query sequence [in]
lookup_wrapthe lookup table [in]
ewpStructure containing the diagonal array
matrixthe substitution matrix [in]
word_paramsstructure containing per-context cutoff information [in]
query_infostructure containing context ranges [in]
offset_pairsArray for storing query and subject offsets. [in]
array_sizethe number of elements in each offset array [in]
ungapped_hspshsps resulting from the ungapped extension [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 440 of file aa_ungapped.c.

References ASSERT, Blast_ExtendWordExit(), Blast_UngappedStatsUpdate(), BlastSaveInitHsp(), BSearchContextInfo(), BlastQueryInfo::contexts, BlastUngappedCutoffs::cutoff_score, BlastInitialWordParameters::cutoffs, BLAST_DiagTable::diag_mask, Blast_ExtendWord::diag_table, eAaLookupTable, FALSE, DiagStruct::flag, BLAST_DiagTable::hit_level_array, i, DiagStruct::last_hit, lookup(), LookupTableWrap::lut, LookupTableWrap::lut_type, NULL, BLAST_DiagTable::offset, query, BlastContextInfo::query_offset, s_BlastAaExtendTwoHit(), subject, BlastInitHitList::total, BLAST_DiagTable::window, and BlastUngappedCutoffs::x_dropoff.

Referenced by BlastAaWordFinder().

◆ s_BlastPSSMExtendLeft()

static Int4 s_BlastPSSMExtendLeft ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
Int4  s_off,
Int4  q_off,
Int4  dropoff,
Int4 length,
Int4  maxscore 
)
static

Identical to BlastAaExtendLeft, except the query is represented by a position-specific score matrix.

Parameters
matrixthe substitution matrix representing the query [in]
subjectsubject sequence [in]
s_offsubject offset [in]
q_offquery offset [in]
dropoffthe X dropoff parameter [in]
lengththe length of the extension [out]
maxscorethe score so far (probably from initial word hit) [in]
Returns
The score of the extension

Definition at line 986 of file aa_ungapped.c.

References i, MIN, n, and subject.

Referenced by s_BlastAaExtendOneHit(), and s_BlastAaExtendTwoHit().

◆ s_BlastPSSMExtendRight()

static Int4 s_BlastPSSMExtendRight ( Int4 **  matrix,
const BLAST_SequenceBlk subject,
Int4  query_size,
Int4  s_off,
Int4  q_off,
Int4  dropoff,
Int4 length,
Int4  maxscore,
Int4 s_last_off 
)
static

Identical to BlastAaExtendRight, except the score matrix is position-specific.

Parameters
matrixthe substitution matrix representing query sequence [in]
subjectsubject sequence [in]
query_sizenumber of rows in the scoring matrix [in]
s_offsubject offset [in]
q_offquery offset [in]
dropoffthe X dropoff parameter [in]
lengththe length of the extension [out]
maxscorethe score derived from a previous left extension [in]
s_last_offthe rightmost subject offset examined [out]
Returns
The score of the extension

Definition at line 938 of file aa_ungapped.c.

References i, MIN, n, and subject.

Referenced by s_BlastAaExtendOneHit(), and s_BlastAaExtendTwoHit().

◆ s_BlastRPSWordFinder_OneHit()

static Int2 s_BlastRPSWordFinder_OneHit ( const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
const LookupTableWrap lookup_wrap,
Blast_ExtendWord ewp,
Int4 **  matrix,
Int4  cutoff,
Int4  dropoff,
BlastInitHitList ungapped_hsps,
BlastUngappedStats ungapped_stats 
)
static

Scan a subject sequence for word hits and trigger one-hit extensions (spcialized for RPS blast).

Parameters
subjectthe subject sequence
querythe query sequence
lookup_wrapthe lookup table
ewpStructure containing the diagonal array [in]
matrixthe substitution matrix [in]
cutoffcutoff score for saving ungapped HSPs [in]
dropoffx dropoff [in]
ungapped_hspshsps resulting from the ungapped extensions [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 622 of file aa_ungapped.c.

References ASSERT, Blast_ExtendWordExit(), Blast_UngappedStatsUpdate(), BlastRPSScanSubject(), BlastSaveInitHsp(), BLAST_DiagTable::diag_mask, Blast_ExtendWord::diag_table, BLAST_DiagTable::hit_level_array, i, DiagStruct::last_hit, lookup(), LookupTableWrap::lut, NULL, RPSBucket::num_filled, BLAST_DiagTable::offset, RPSBucket::offset_pairs, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, query, s_BlastAaExtendOneHit(), BlastOffsetPair::s_off, subject, BlastInitHitList::total, TRUE, and while().

Referenced by BlastRPSWordFinder().

◆ s_BlastRPSWordFinder_TwoHit()

static Int2 s_BlastRPSWordFinder_TwoHit ( const BLAST_SequenceBlk subject,
const BLAST_SequenceBlk query,
const LookupTableWrap lookup_wrap,
Blast_ExtendWord ewp,
Int4 **  matrix,
Int4  cutoff,
Int4  dropoff,
BlastInitHitList ungapped_hsps,
BlastUngappedStats ungapped_stats 
)
static

Scan a subject sequence for word hits and trigger two-hit extensions (specialized for RPS blast).

Parameters
subjectthe subject sequence [in]
querythe query sequence [in]
lookup_wrapthe lookup table [in]
ewpStructure containing the diagonal array [in]
matrixthe substitution matrix [in]
cutoffcutoff score for saving ungapped HSPs [in]
dropoffx dropoff [in]
ungapped_hspshsps resulting from the ungapped extension [out]
ungapped_statsVarious hit counts. Not filled if NULL [out]

Definition at line 287 of file aa_ungapped.c.

References ASSERT, Blast_ExtendWordExit(), Blast_UngappedStatsUpdate(), BlastRPSScanSubject(), BlastSaveInitHsp(), BLAST_DiagTable::diag_mask, Blast_ExtendWord::diag_table, DiagStruct::flag, BLAST_DiagTable::hit_level_array, i, DiagStruct::last_hit, lookup(), LookupTableWrap::lut, NULL, RPSBucket::num_filled, BLAST_DiagTable::offset, RPSBucket::offset_pairs, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, query, s_BlastAaExtendTwoHit(), BlastOffsetPair::s_off, subject, BlastInitHitList::total, TRUE, while(), and BLAST_DiagTable::window.

Referenced by BlastRPSWordFinder().

Modified on Tue Apr 23 07:38:47 2024 by modify_doxy.py rev. 669887