NCBI C++ ToolKit
Macros | Functions
blast_traceback.c File Reference

Functions responsible for the traceback stage of the BLAST algorithm. More...

#include <algo/blast/core/blast_traceback.h>
#include <algo/blast/core/blast_util.h>
#include <algo/blast/core/blast_encoding.h>
#include <algo/blast/core/link_hsps.h>
#include <algo/blast/core/blast_setup.h>
#include <algo/blast/core/blast_kappa.h>
#include <algo/blast/core/blast_sw.h>
#include <algo/blast/core/blast_seqsrc.h>
#include <algo/blast/core/blast_seqsrc_impl.h>
#include <algo/blast/core/phi_gapalign.h>
#include <algo/blast/core/gencode_singleton.h>
#include "blast_gapalign_priv.h"
#include "blast_psi_priv.h"
#include "blast_hits_priv.h"
#include "blast_itree.h"
#include "blast_traceback_mt_priv.h"
#include "blast_hspstream_mt_utils.h"
+ Include dependency graph for blast_traceback.c:

Go to the source code of this file.

Go to the SVN repository for this file.

Macros

#define HSP_MAX_WINDOW   11
 Window size used to scan HSP for highest score region, where gapped extension starts. More...
 
#define RPS_K_MULT   1.2
 Factor to multiply the Karlin-Altschul K parameter by for RPS BLAST, to make e-values more conservative. More...
 

Functions

Int2 Blast_HSPUpdateWithTraceback (BlastGapAlignStruct *gap_align, BlastHSP *hsp)
 Modifies the HSP data after the final gapped alignment. More...
 
static void s_HSPListRescaleScores (BlastHSPList *hsp_list, double scale_factor)
 Remove scaling from scores previously calculated on the hsp_list. More...
 
static void s_BlastHSPRPSUpdate (BlastHSP *hsp)
 Swaps insertions and deletions in an edit script for RPS BLAST search. More...
 
static void s_BlastHSPListRPSUpdate (EBlastProgramType program, BlastHSPList *hsplist)
 Switches back the query and subject in all HSPs in an HSP list; also reassigns contexts to indicate query context, needed to pick correct Karlin block later in the code. More...
 
static Int2 s_HSPListPostTracebackUpdate (EBlastProgramType program_number, BlastHSPList *hsp_list, const BlastQueryInfo *query_info, const BlastScoringParameters *score_params, const BlastHitSavingParameters *hit_params, const BlastScoreBlk *sbp, Int4 subject_length)
 Updates the e-values after the traceback alignment. More...
 
Int2 Blast_TracebackFromHSPList (EBlastProgramType program_number, BlastHSPList *hsp_list, const BLAST_SequenceBlk *query_blk, BLAST_SequenceBlk *subject_blk, const BlastQueryInfo *query_info_in, BlastGapAlignStruct *gap_align, const BlastScoreBlk *sbp, const BlastScoringParameters *score_params, const BlastExtensionOptions *ext_options, const BlastHitSavingParameters *hit_params, const Uint1 *gen_code_string, Boolean *fence_hit)
 Compute gapped alignment with traceback for all HSPs from a single query/subject sequence pair. More...
 
static Int2 s_PHITracebackFromHSPList (EBlastProgramType program_number, BlastHSPList *hsp_list, BLAST_SequenceBlk *query_blk, BLAST_SequenceBlk *subject_blk, BlastGapAlignStruct *gap_align, BlastScoreBlk *sbp, const BlastScoringParameters *score_params, const BlastHitSavingParameters *hit_params, const BlastQueryInfo *query_info, SPHIPatternSearchBlk *pattern_blk)
 Performs traceback alignment for one HSP list in a PHI BLAST search. More...
 
EBlastEncoding Blast_TracebackGetEncoding (EBlastProgramType program_number)
 Get the subject sequence encoding type for the traceback, given a program number. More...
 
static void s_FilterBlastResults (BlastHSPResults *results, const BlastHitSavingOptions *hit_options, const BlastQueryInfo *query_info, EBlastProgramType program_number)
 Delete hsps below query coverage percentage. More...
 
static void s_BlastPruneExtraHits (BlastHSPResults *results, Int4 hitlist_size)
 Delete extra subject sequences hits, if after-traceback hit list size is smaller than preliminary hit list size. More...
 
void RPSPsiMatrixAttach (BlastScoreBlk *sbp, Int4 **rps_pssm, Int4 alphabet_size)
 Modify a BlastScoreBlk structure so that it can be used in RPS-BLAST. More...
 
void RPSPsiMatrixDetach (BlastScoreBlk *sbp)
 Remove the artificially built SPsiBlastScoreMatrix structure allocated by RPSPsiMatrixAttach. More...
 
static Int2 s_RPSGapAlignDataPrepare (BlastQueryInfo *concat_db_info, BlastGapAlignStruct *gap_align, const BlastRPSInfo *rps_info, Int4 ***rps_freq)
 Prepares an auxiliary BlastQueryInfo structure for the concatenated database and creates a memory mapped PSSM for RPS BLAST traceback. More...
 
static void s_RPSFillFreqRatiosInPsiMatrix (SPsiBlastScoreMatrix *psi_matrix, Int4 **freq, Int4 ncol)
 
static Int2 s_RPSComputeTraceback (EBlastProgramType program_number, BlastHSPStream *hsp_stream, const BlastSeqSrc *seq_src, Int4 default_db_genetic_code, BLAST_SequenceBlk *query, const BlastQueryInfo *query_info, BlastGapAlignStruct *gap_align, BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, const BlastHitSavingParameters *hit_params, const BlastRPSInfo *rps_info, const PSIBlastOptions *psi_options, BlastHSPResults *results, TInterruptFnPtr interrupt_search, SBlastProgress *progress_info)
 Compute traceback information for alignments found by an RPS blast search. More...
 
BlastSeqSrcSetRangesArgBLAST_SetupPartialFetching (EBlastProgramType program_number, BlastSeqSrc *seq_src, const BlastHSPList **hsplist_array, Int4 num_hsplists)
 Attempts to set up partial fetching, if it fails (e.g. More...
 
Int2 BLAST_ComputeTraceback (EBlastProgramType program_number, BlastHSPStream *hsp_stream, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, const BlastSeqSrc *seq_src, BlastGapAlignStruct *gap_align, BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, BlastHitSavingParameters *hit_params, BlastEffectiveLengthsParameters *eff_len_params, const BlastDatabaseOptions *db_options, const PSIBlastOptions *psi_options, const BlastRPSInfo *rps_info, SPHIPatternSearchBlk *pattern_blk, BlastHSPResults **results_out, TInterruptFnPtr interrupt_search, SBlastProgress *progress_info)
 Given the preliminary alignment results from a database search, redo the gapped alignment with traceback, if it has not yet been done. More...
 
static void s_SThreadLocalDataArraySetGapXDropoffFinal (SThreadLocalDataArray *array)
 Set the raw X-dropoff value for the final gapped extension with traceback. More...
 
Int2 BLAST_ComputeTraceback_MT (EBlastProgramType program_number, BlastHSPStream *hsp_stream, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, SThreadLocalDataArray *thread_data, const BlastDatabaseOptions *db_options, const PSIBlastOptions *psi_options, const BlastRPSInfo *rps_info, SPHIPatternSearchBlk *pattern_blk, BlastHSPResults **results_out, TInterruptFnPtr interrupt_search, SBlastProgress *progress_info)
 Identical in function to BLAST_ComputeTraceback, but this performs its task in a multi-threaded manner if OpenMP is available. More...
 
Int2 Blast_RunTracebackSearch (EBlastProgramType program, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, const BlastSeqSrc *seq_src, const BlastScoringOptions *score_options, const BlastExtensionOptions *ext_options, const BlastHitSavingOptions *hit_options, const BlastEffectiveLengthsOptions *eff_len_options, const BlastDatabaseOptions *db_options, const PSIBlastOptions *psi_options, BlastScoreBlk *sbp, BlastHSPStream *hsp_stream, const BlastRPSInfo *rps_info, SPHIPatternSearchBlk *pattern_blk, BlastHSPResults **results, size_t num_threads)
 Entry point from the API level to perform the traceback stage of a BLAST search, given the source of HSP lists, obtained from the preliminary stage. More...
 
Int2 Blast_RunTracebackSearchWithInterrupt (EBlastProgramType program, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, const BlastSeqSrc *seq_src, const BlastScoringOptions *score_options, const BlastExtensionOptions *ext_options, const BlastHitSavingOptions *hit_options, const BlastEffectiveLengthsOptions *eff_len_options, const BlastDatabaseOptions *db_options, const PSIBlastOptions *psi_options, BlastScoreBlk *sbp, BlastHSPStream *hsp_stream, const BlastRPSInfo *rps_info, SPHIPatternSearchBlk *pattern_blk, BlastHSPResults **results, TInterruptFnPtr interrupt_search, SBlastProgress *progress_info, size_t num_threads)
 Entry point from the API level to perform the traceback stage of a BLAST search, given the source of HSP lists, obtained from the preliminary stage. More...
 

Detailed Description

Functions responsible for the traceback stage of the BLAST algorithm.

The hierarchy of function calls for performing traceback is:
   Blast_RunTracebackSearch
       BLAST_GapAlignSetUp
       BLAST_ComputeTraceback
           if ( RPS BLAST )
               s_RPSComputeTraceback
                   for ( all HSP lists )
                       Blast_TracebackFromHSPList
           else if ( composition based statistics )
               Blast_RedoAlignmentCore
           else
               for ( all HSP lists )
                   if ( PHI BLAST)
                       s_PHITracebackFromHSPList
                   else
                       Blast_TracebackFromHSPList

Definition in file blast_traceback.c.

Macro Definition Documentation

◆ HSP_MAX_WINDOW

#define HSP_MAX_WINDOW   11

Window size used to scan HSP for highest score region, where gapped extension starts.

Definition at line 75 of file blast_traceback.c.

◆ RPS_K_MULT

#define RPS_K_MULT   1.2

Factor to multiply the Karlin-Altschul K parameter by for RPS BLAST, to make e-values more conservative.

Definition at line 1011 of file blast_traceback.c.

Function Documentation

◆ BLAST_ComputeTraceback()

Int2 BLAST_ComputeTraceback ( EBlastProgramType  program_number,
BlastHSPStream hsp_stream,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
const BlastSeqSrc seq_src,
BlastGapAlignStruct gap_align,
BlastScoringParameters score_params,
const BlastExtensionParameters ext_params,
BlastHitSavingParameters hit_params,
BlastEffectiveLengthsParameters eff_len_params,
const BlastDatabaseOptions db_options,
const PSIBlastOptions psi_options,
const BlastRPSInfo rps_info,
SPHIPatternSearchBlk pattern_blk,
BlastHSPResults **  results,
TInterruptFnPtr  interrupt_search,
SBlastProgress progress_info 
)

Given the preliminary alignment results from a database search, redo the gapped alignment with traceback, if it has not yet been done.

Parameters
program_numberType of the BLAST program [in]
hsp_streamA stream for reading HSP lists [in]
queryThe query sequence [in]
query_infoInformation about the query [in]
seq_srcSource of subject sequences [in]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsScoring parameters (esp. scale factor) [in]
ext_paramsGapped extension parameters [in]
hit_paramsParameters for saving hits. Can change if not a database search [in]
eff_len_paramsParameters for recalculating effective search space. Can change if not a database search. [in]
db_optionsOptions containing database genetic code string [in]
psi_optionsOptions for iterative searches [in]
rps_infoRPS BLAST auxiliary data structure [in]
pattern_blkPHI BLAST auxiliary data structure [in]
resultsAll results from the BLAST search [out]
interrupt_searchfunction callback to allow interruption of BLAST search [in, optional]
progress_infocontains information about the progress of the current BLAST search [in|out]
Returns
nonzero indicates failure, otherwise zero

Definition at line 1378 of file blast_traceback.c.

References BLAST_ComputeTraceback_MT(), BLASTERR_MEMORY, BlastExtensionParameters::options, BlastHitSavingParameters::options, BlastScoringParameters::options, BlastEffectiveLengthsParameters::options, query, BlastGapAlignStruct::sbp, SThreadLocalDataArrayFree(), SThreadLocalDataArrayNew(), and SThreadLocalDataArraySetup().

Referenced by Blast_RunFullSearch(), and CTracebackTestFixture::x_ComputeTracebak().

◆ BLAST_ComputeTraceback_MT()

Int2 BLAST_ComputeTraceback_MT ( EBlastProgramType  program_number,
BlastHSPStream hsp_stream,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
SThreadLocalDataArray thread_data,
const BlastDatabaseOptions db_options,
const PSIBlastOptions psi_options,
const BlastRPSInfo rps_info,
SPHIPatternSearchBlk pattern_blk,
BlastHSPResults **  results_out,
TInterruptFnPtr  interrupt_search,
SBlastProgress progress_info 
)

Identical in function to BLAST_ComputeTraceback, but this performs its task in a multi-threaded manner if OpenMP is available.

Definition at line 1436 of file blast_traceback.c.

References BlastHSPStreamResultsBatchArray::array_of_batches, ASSERT, Blast_HSPListFree(), Blast_HSPListGetBitScores(), Blast_HSPResultsApplyMasklevel(), Blast_HSPResultsFree(), Blast_HSPResultsInsertHSPList(), Blast_HSPResultsNew(), Blast_HSPResultsSortByEvalue(), Blast_HSPStreamResultBatchReset(), BLAST_OneSubjectUpdateParameters(), Blast_ProgramIsPhiBlast(), Blast_ProgramIsRpsBlast(), Blast_RedoAlignmentCore_MT(), BLAST_SetupPartialFetching(), Blast_SubjectIsTranslated(), Blast_TracebackFromHSPList(), Blast_TracebackGetEncoding(), BLASTERR_INTERRUPTED, BlastHSPStreamResultsBatchArrayFree(), BlastHSPStreamTBackClose(), BlastHSPStreamToHSPStreamResultsBatch(), BlastSeqSrcGetSequence(), BlastSeqSrcGetSupportsPartialFetching(), BlastSeqSrcGetTotLen(), BlastSeqSrcReleaseSequence(), BlastSeqSrcSetRangesArgFree(), BlastSequenceBlkFree(), BlastSeqSrcGetSeqArg::check_oid_exclusion, BlastExtensionOptions::compositionBasedStats, SThreadLocalData::eff_len_params, BlastSeqSrcGetSeqArg::encoding, eSmithWatermanTbck, BlastExtensionOptions::eTbackExt, eTracebackSearch, SThreadLocalData::ext_params, FALSE, SThreadLocalData::gap_align, BlastScoringOptions::gapped_calculation, BLAST_SequenceBlk::gen_code_string, GenCodeSingletonFind(), BlastDatabaseOptions::genetic_code, SThreadLocalData::hit_params, BlastHitSavingOptions::hitlist_size, BlastHitSavingOptions::hsp_filt_opt, BlastHSPList::hspcnt, BlastHSPStreamResultBatch::hsplist_array, i, BLAST_SequenceBlk::length, BlastHitSavingParameters::mask_level, MAX, BlastHitSavingOptions::max_hsps_per_subject, MIN, NULL, BlastHSPStreamResultsBatchArray::num_batches, SThreadLocalDataArray::num_elems, BlastHSPStreamResultBatch::num_hsplists, BlastQueryInfo::num_queries, BlastHSPList::oid, BlastSeqSrcGetSeqArg::oid, BlastExtensionParameters::options, BlastHitSavingParameters::options, BlastScoringParameters::options, query, BlastHitSavingOptions::query_cov_hsp_perc, SThreadLocalData::query_info, BlastSeqSrcGetSeqArg::ranges, BlastSeqSrcGetSeqArg::reset_ranges, SThreadLocalData::results, results, s_BlastPruneExtraHits(), s_FilterBlastResults(), s_PHITracebackFromHSPList(), s_RPSComputeTraceback(), s_SThreadLocalDataArraySetGapXDropoffFinal(), BlastGapAlignStruct::sbp, SThreadLocalData::score_params, BlastSeqSrcGetSeqArg::seq, SThreadLocalData::seqsrc, SBlastProgress::stage, SThreadLocalDataArrayConsolidateResults(), SThreadLocalDataArrayTrim(), BlastHSPFilteringOptions::subject_besthit_opts, SThreadLocalDataArray::tld, and TRUE.

Referenced by BLAST_ComputeTraceback(), and Blast_RunTracebackSearchWithInterrupt().

◆ Blast_HSPUpdateWithTraceback()

Int2 Blast_HSPUpdateWithTraceback ( BlastGapAlignStruct gap_align,
BlastHSP hsp 
)

Modifies the HSP data after the final gapped alignment.

Input includes only data that likely needs modification. This function could be static in blast_traceback.c, but for a unit test which checks its functionality.

Parameters
gap_alignStructure containing gapped alignment information [in]
hspOriginal HSP from the preliminary stage [in] [out]

Definition at line 78 of file blast_traceback.c.

References BlastGapAlignStruct::edit_script, BlastSeg::end, BlastHSP::gap_info, NULL, BlastSeg::offset, BlastHSP::query, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, BlastGapAlignStruct::score, BlastHSP::score, BlastHSP::subject, BlastGapAlignStruct::subject_start, and BlastGapAlignStruct::subject_stop.

Referenced by Blast_TracebackFromHSPList(), BOOST_AUTO_TEST_CASE(), and s_PHITracebackFromHSPList().

◆ Blast_RunTracebackSearch()

Int2 Blast_RunTracebackSearch ( EBlastProgramType  program,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
const BlastSeqSrc seq_src,
const BlastScoringOptions score_options,
const BlastExtensionOptions ext_options,
const BlastHitSavingOptions hit_options,
const BlastEffectiveLengthsOptions eff_len_options,
const BlastDatabaseOptions db_options,
const PSIBlastOptions psi_options,
BlastScoreBlk sbp,
BlastHSPStream hsp_stream,
const BlastRPSInfo rps_info,
SPHIPatternSearchBlk pattern_blk,
BlastHSPResults **  results,
size_t  num_threads 
)

Entry point from the API level to perform the traceback stage of a BLAST search, given the source of HSP lists, obtained from the preliminary stage.

The parameters internal to the engine are calculated here independently of the similar calculation in the preliminary stage, effectively making the two stages independent of each other.

Parameters
programBLAST program type [in]
queryQuery sequence(s) structure [in]
query_infoAdditional query information [in]
seq_srcSource of subject sequences [in]
score_optionsScoring options [in]
ext_optionsWord extension options, needed for cutoff scores calculation only [in]
hit_optionsHit saving options [in]
eff_len_optionsOptions for calculating effective lengths [in]
db_optionsDatabase options (database genetic code) [in]
psi_optionsPSI BLAST options [in]
sbpScoring block with statistical parameters and matrix [in]
hsp_streamSource of HSP lists. [in]
rps_infoRPS database information structure [in]
pattern_blkPHI BLAST auxiliary data structure [in]
resultsWhere to save the results after traceback. [out]
num_threadsMaximum number of threads to spawn [in]

Definition at line 1789 of file blast_traceback.c.

References Blast_RunTracebackSearchWithInterrupt(), NULL, query, and results.

◆ Blast_RunTracebackSearchWithInterrupt()

Int2 Blast_RunTracebackSearchWithInterrupt ( EBlastProgramType  program,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
const BlastSeqSrc seq_src,
const BlastScoringOptions score_options,
const BlastExtensionOptions ext_options,
const BlastHitSavingOptions hit_options,
const BlastEffectiveLengthsOptions eff_len_options,
const BlastDatabaseOptions db_options,
const PSIBlastOptions psi_options,
BlastScoreBlk sbp,
BlastHSPStream hsp_stream,
const BlastRPSInfo rps_info,
SPHIPatternSearchBlk pattern_blk,
BlastHSPResults **  results,
TInterruptFnPtr  interrupt_search,
SBlastProgress progress_info,
size_t  num_threads 
)

Entry point from the API level to perform the traceback stage of a BLAST search, given the source of HSP lists, obtained from the preliminary stage.

The parameters internal to the engine are calculated here independently of the similar calculation in the preliminary stage, effectively making the two stages independent of each other.

Parameters
programBLAST program type [in]
queryQuery sequence(s) structure [in]
query_infoAdditional query information [in]
seq_srcSource of subject sequences [in]
score_optionsScoring options [in]
ext_optionsWord extension options, needed for cutoff scores calculation only [in]
hit_optionsHit saving options [in]
eff_len_optionsOptions for calculating effective lengths [in]
db_optionsDatabase options (database genetic code) [in]
psi_optionsPSI BLAST options [in]
sbpScoring block with statistical parameters and matrix [in]
hsp_streamSource of HSP lists. [in]
rps_infoRPS database information structure [in]
pattern_blkPHI BLAST auxiliary data structure [in]
resultsWhere to save the results after traceback. [out]
interrupt_searchUser specified function to interrupt search [in]
progress_infoUser supplied data structure to aid interrupt [in]
num_threadsMaximum number of threads to spawn [in]

Definition at line 1809 of file blast_traceback.c.

References BLAST_ComputeTraceback_MT(), BLASTERR_MEMORY, BlastHSPCBSStreamClose(), BlastHSPStreamClose(), BlastExtensionOptions::compositionBasedStats, BlastHitSavingOptions::hitlist_size, NULL, query, results, SThreadLocalDataArrayFree(), SThreadLocalDataArrayNew(), and SThreadLocalDataArraySetup().

Referenced by Blast_RunTracebackSearch(), CBlastTracebackSearch::Run(), and CBlastTracebackSearch::RunSimple().

◆ BLAST_SetupPartialFetching()

BlastSeqSrcSetRangesArg* BLAST_SetupPartialFetching ( EBlastProgramType  program_number,
BlastSeqSrc seq_src,
const BlastHSPList **  hsplist_array,
Int4  num_hsplists 
)

◆ Blast_TracebackFromHSPList()

Int2 Blast_TracebackFromHSPList ( EBlastProgramType  program_number,
BlastHSPList hsp_list,
const BLAST_SequenceBlk query_blk,
BLAST_SequenceBlk subject_blk,
const BlastQueryInfo query_info,
BlastGapAlignStruct gap_align,
const BlastScoreBlk sbp,
const BlastScoringParameters score_params,
const BlastExtensionOptions ext_options,
const BlastHitSavingParameters hit_params,
const Uint1 gen_code_string,
Boolean fence_hit 
)

Compute gapped alignment with traceback for all HSPs from a single query/subject sequence pair.

Final e-values are calculated here, except when sum statistics is used, in which case this is done in file link_hsps.c:

See also
{ BLAST_LinkHsps }
Parameters
program_numberType of BLAST program [in]
hsp_listList of HSPs [in]
query_blkThe query sequence [in]
subject_blkThe subject sequence [in]
query_infoQuery information, needed to get pointer to the start of this query within the concatenated sequence [in]
gap_alignAuxiliary structure used for gapped alignment [in]
sbpStatistical parameters [in]
score_paramsScoring parameters (esp. scale factor) [in]
ext_optionsGapped extension options [in]
hit_paramsHit saving parameters [in]
gen_code_stringspecifies genetic code [in]
fence_hitTrue is returned here if overrun is detected. [in|out]

Definition at line 259 of file blast_traceback.c.

References AdjustSubjectRange(), BlastHSPList::allocated, BlastScoreBlk::alphabet_size, ASSERT, BLAST_FrameToContext(), BLAST_GappedAlignmentWithTraceback(), BLAST_GreedyGappedAlignment(), Blast_HSPAdjustSubjectOffset(), Blast_HSPFree(), Blast_HSPGetNumIdentitiesAndPositives(), Blast_HSPGetTargetTranslation(), Blast_HSPListFree(), Blast_HSPListIsSortedByScore(), Blast_HSPListPurgeHSPsWithCommonEndpoints(), Blast_HSPListPurgeNullHSPs(), Blast_HSPListSortByScore(), Blast_HSPListSwap(), Blast_HSPNew(), Blast_HSPReevaluateWithAmbiguitiesGapped(), Blast_HSPTest(), Blast_HSPTestIdentityAndLength(), Blast_HSPUpdateWithTraceback(), Blast_IntervalTreeFree(), Blast_IntervalTreeInit(), Blast_IntervalTreeReset(), Blast_ProgramIsRpsBlast(), Blast_SubjectIsTranslated(), BlastGetOffsetsForGappedAlignment(), BlastGetStartForGappedAlignmentNucl(), BlastHSPListDup(), BlastIntervalTreeAddHSP(), BlastIntervalTreeContainsHSP(), BlastMemDup(), BlastTargetTranslationFree(), BlastTargetTranslationNew(), CODON_LENGTH, BlastScoreBlk::complexity_adjusted_scoring, BlastHSP::context, context, ContextOffsetsToOffsetArray(), BlastQueryInfo::contexts, count, BlastGappedCutoffs::cutoff_score, BlastHitSavingParameters::cutoffs, eBlastTypeBlastn, eBlastTypeBlastx, eBlastTypeMapping, eBlastTypeRpsBlast, eBlastTypeRpsTblastn, BlastGapAlignStruct::edit_script, eGapAlignIns, eGapAlignSub, eGreedyTbck, eQueryAndSubject, eSmithWatermanTbckFull, BlastExtensionOptions::eTbackExt, FALSE, BlastQueryInfo::first_context, BlastSeg::frame, SBlastScoreMatrix::freqs, GapEditScriptDelete(), BlastSeg::gapped_start, BlastHSPList::hsp_array, BlastHSPList::hspcnt, INT4_MIN, BlastScoringOptions::is_ooframe, SBlastScoreMatrix::lambda, BlastQueryInfo::last_context, BLAST_SequenceBlk::length, log, malloc(), BlastScoreBlk::matrix, BlastHitSavingOptions::min_diag_separation, NULL, GapEditScript::num, NUM_FRAMES, BlastQueryInfo::num_queries, BlastSeg::offset, OffsetArrayToContextOffsets(), offsets, BLAST_SequenceBlk::oof_sequence, GapEditScript::op_type, BlastHitSavingParameters::options, BlastScoringParameters::options, BlastHSP::query, query, BlastHSPList::query_index, BlastContextInfo::query_length, BlastContextInfo::query_offset, BlastGapAlignStruct::query_start, s_HSPListPostTracebackUpdate(), BlastGapAlignStruct::score, BLAST_SequenceBlk::sequence, BLAST_SequenceBlk::sequence_nomask, sfree, GapEditScript::size, SmithWatermanScoreWithTraceback(), BlastHSP::subject, subject, BlastGapAlignStruct::subject_start, and TRUE.

Referenced by BLAST_ComputeTraceback_MT(), and s_RPSComputeTraceback().

◆ Blast_TracebackGetEncoding()

EBlastEncoding Blast_TracebackGetEncoding ( EBlastProgramType  program_number)

Get the subject sequence encoding type for the traceback, given a program number.

Definition at line 819 of file blast_traceback.c.

References Blast_SubjectIsProtein(), Blast_SubjectIsTranslated(), eBlastEncodingNcbi4na, eBlastEncodingNucleotide, and eBlastEncodingProtein.

Referenced by BLAST_ComputeTraceback_MT(), BOOST_AUTO_TEST_CASE(), s_ComputeNumIdentities(), and s_RPSComputeTraceback().

◆ RPSPsiMatrixAttach()

void RPSPsiMatrixAttach ( BlastScoreBlk sbp,
Int4 **  rps_pssm,
Int4  alphabet_size 
)

Modify a BlastScoreBlk structure so that it can be used in RPS-BLAST.

This involves allocating a SPsiBlastScoreMatrix structure so that the PSSMs memory mapped from the RPS-BLAST database files can be assigned to that structure.

Parameters
sbpBlastScoreBlk structure to modify [in|out]
rps_pssmPSSMs in RPS-BLAST database to use [in]
alphabet_sizeElements in one pssm row [in]

Definition at line 895 of file blast_traceback.c.

References ASSERT, calloc(), SBlastScoreMatrix::data, SBlastScoreMatrix::nrows, BlastScoreBlk::psi_matrix, and SPsiBlastScoreMatrix::pssm.

Referenced by s_RPSGapAlignDataPrepare(), and s_RPSPreliminarySearchEngine().

◆ RPSPsiMatrixDetach()

void RPSPsiMatrixDetach ( BlastScoreBlk sbp)

Remove the artificially built SPsiBlastScoreMatrix structure allocated by RPSPsiMatrixAttach.

Parameters
sbpBlastScoreBlk structure to modify [in|out]

Definition at line 916 of file blast_traceback.c.

References ASSERT, SBlastScoreMatrix::data, SPsiBlastScoreMatrix::freq_ratios, NULL, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, and sfree.

Referenced by s_RPSComputeTraceback(), and s_RPSPreliminarySearchEngine().

◆ s_BlastHSPListRPSUpdate()

static void s_BlastHSPListRPSUpdate ( EBlastProgramType  program,
BlastHSPList hsplist 
)
static

Switches back the query and subject in all HSPs in an HSP list; also reassigns contexts to indicate query context, needed to pick correct Karlin block later in the code.

Parameters
programProgram type: RPS or RPS tblastn [in]
hsplistList of HSPs [in] [out]

Definition at line 155 of file blast_traceback.c.

References BLAST_FrameToContext(), Blast_HSPListSortByScore(), Blast_ProgramIsRpsBlast(), BlastHSP::context, eBlastTypeRpsTblastn, BlastHSPList::hsp_array, BlastHSPList::hspcnt, i, BlastHSP::query, query, s_BlastHSPRPSUpdate(), BlastHSP::subject, and tmp.

Referenced by s_HSPListPostTracebackUpdate(), and s_RPSComputeTraceback().

◆ s_BlastHSPRPSUpdate()

static void s_BlastHSPRPSUpdate ( BlastHSP hsp)
static

Swaps insertions and deletions in an edit script for RPS BLAST search.

This is necessary because query and subject are switched during the traceback alignment, and must be switched back.

Parameters
hspHSP structure to fix. [in] [out]

Definition at line 131 of file blast_traceback.c.

References eGapAlignDel, eGapAlignIns, BlastHSP::gap_info, NULL, GapEditScript::op_type, and GapEditScript::size.

Referenced by s_BlastHSPListRPSUpdate().

◆ s_BlastPruneExtraHits()

static void s_BlastPruneExtraHits ( BlastHSPResults results,
Int4  hitlist_size 
)
static

Delete extra subject sequences hits, if after-traceback hit list size is smaller than preliminary hit list size.

Parameters
resultsAll results after traceback, assumed already sorted by best e-value [in] [out]
hitlist_sizeFinal hit list size [in]

Definition at line 878 of file blast_traceback.c.

References Blast_HSPListFree(), BlastHitList::hsplist_array, BlastHitList::hsplist_count, MIN, and results.

Referenced by BLAST_ComputeTraceback_MT().

◆ s_FilterBlastResults()

static void s_FilterBlastResults ( BlastHSPResults results,
const BlastHitSavingOptions hit_options,
const BlastQueryInfo query_info,
EBlastProgramType  program_number 
)
static

◆ s_HSPListPostTracebackUpdate()

static Int2 s_HSPListPostTracebackUpdate ( EBlastProgramType  program_number,
BlastHSPList hsp_list,
const BlastQueryInfo query_info,
const BlastScoringParameters score_params,
const BlastHitSavingParameters hit_params,
const BlastScoreBlk sbp,
Int4  subject_length 
)
static

Updates the e-values after the traceback alignment.

Also includes relinking of HSPs in case of sum statistics and calculation of bit scores.

Parameters
program_numberType of BLAST program [in]
hsp_listHSPList obtained after a traceback alignment [in] [out]
query_infoQuery information structure [in]
score_paramsScoring parameters [in]
hit_paramsHit saving parameters [in]
sbpScoring block [in]
subject_lengthLength of the subject sequence - needed for linking HSPs [in]

Definition at line 199 of file blast_traceback.c.

References Blast_HSPListAdjustOddBlastnScores(), Blast_HSPListGetBitScores(), Blast_HSPListGetEvalues(), Blast_HSPListReapByEvalue(), BLAST_LinkHsps(), Blast_ProgramIsRpsBlast(), FALSE, BlastScoringOptions::gapped_calculation, BlastHitSavingParameters::link_hsp_params, BlastHitSavingParameters::options, BlastScoringParameters::options, s_BlastHSPListRPSUpdate(), s_HSPListRescaleScores(), and BlastScoringParameters::scale_factor.

Referenced by Blast_TracebackFromHSPList().

◆ s_HSPListRescaleScores()

static void s_HSPListRescaleScores ( BlastHSPList hsp_list,
double  scale_factor 
)
static

Remove scaling from scores previously calculated on the hsp_list.

Parameters
hsp_listlist of HPSs with the score field calculated [in|out]
scale_factorfactor by which scores are scaled, for everything other than RPS-BLAST this should be 1 [in]

Definition at line 106 of file blast_traceback.c.

References Blast_HSPListSortByScore(), BlastHSPList::hsp_array, BlastHSPList::hspcnt, and BlastHSP::score.

Referenced by s_HSPListPostTracebackUpdate().

◆ s_PHITracebackFromHSPList()

static Int2 s_PHITracebackFromHSPList ( EBlastProgramType  program_number,
BlastHSPList hsp_list,
BLAST_SequenceBlk query_blk,
BLAST_SequenceBlk subject_blk,
BlastGapAlignStruct gap_align,
BlastScoreBlk sbp,
const BlastScoringParameters score_params,
const BlastHitSavingParameters hit_params,
const BlastQueryInfo query_info,
SPHIPatternSearchBlk pattern_blk 
)
static

Performs traceback alignment for one HSP list in a PHI BLAST search.

Parameters
program_numbereBlastTypePhiBlastn or eBlastTypePhiBlastp [in]
hsp_listHSP list for a single query/subject pair, with preliminary alignment information [in]
query_blkQuery sequence [in]
subject_blkSubject sequence [in]
gap_alignGapped alignment structure [in]
sbpScoring block [in]
score_paramsScoring parameters [in]
hit_paramsHit saving parameters [in]
query_infoQuery information, including pattern occurrences in query [in]
pattern_blkPattern information and auxiliary structures [in]

Definition at line 740 of file blast_traceback.c.

References ASSERT, Blast_HSPFree(), Blast_HSPListIsSortedByScore(), Blast_HSPListPHIGetBitScores(), Blast_HSPListPHIGetEvalues(), Blast_HSPListPurgeNullHSPs(), Blast_HSPListReapByEvalue(), Blast_HSPListSortByScore(), Blast_HSPUpdateWithTraceback(), Blast_ProgramIsPhiBlast(), BlastHitSavingParameters::cutoff_score_min, BlastGapAlignStruct::edit_script, GapEditScriptDelete(), BlastSeg::gapped_start, BlastHSPList::hsp_array, BlastHSPList::hspcnt, SPHIHspInfo::index, BLAST_SequenceBlk::length, SPHIHspInfo::length, NULL, BlastHitSavingParameters::options, BlastHSP::pat_info, BlastQueryInfo::pattern_info, pattern_info(), PHIGappedAlignmentWithTraceback(), BlastHSP::query, query, BlastGapAlignStruct::score, BLAST_SequenceBlk::sequence, BlastHSP::subject, and subject.

Referenced by BLAST_ComputeTraceback_MT().

◆ s_RPSComputeTraceback()

static Int2 s_RPSComputeTraceback ( EBlastProgramType  program_number,
BlastHSPStream hsp_stream,
const BlastSeqSrc seq_src,
Int4  default_db_genetic_code,
BLAST_SequenceBlk query,
const BlastQueryInfo query_info,
BlastGapAlignStruct gap_align,
BlastScoringParameters score_params,
const BlastExtensionParameters ext_params,
const BlastHitSavingParameters hit_params,
const BlastRPSInfo rps_info,
const PSIBlastOptions psi_options,
BlastHSPResults results,
TInterruptFnPtr  interrupt_search,
SBlastProgress progress_info 
)
static

Compute traceback information for alignments found by an RPS blast search.

This function performs two major tasks:

  • Computes a composition-specific PSSM to be used during the traceback computation (non-translated searches only)
  • After traceback is computed, switch query offsets with subject offsets and switch the edit blocks that describe the alignment. This is required because the entire RPS search was performed with these quatities reversed. This call is also the first time that enough information exists to compute E-values for alignments that are found.
Parameters
program_numberType of the BLAST program [in]
hsp_streamA stream for reading HSP lists [in]
seq_srcSource of RPS database consensus sequences; needed only to calculate number of identities in alignments [in]
queryThe original query sequence [in]
query_infoInformation associated with the original query. Only used for the search space [in]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsScoring parameters (esp. scale factor) [in]
ext_paramsGapped extension parameters [in]
hit_paramsParameters for saving hits. Can change if not a database search [in]
rps_infoExtra information about RPS database. [in]
resultsResults structure containing all HSPs, with added traceback information. [out]
interrupt_searchfunction callback to allow interruption of BLAST search [in, optional]
progress_infocontains information about the progress of the current BLAST search [in|out]
Returns
nonzero indicates failure, otherwise zero

Definition at line 1046 of file blast_traceback.c.

References _PSIAllocateMatrix(), _PSIDeallocateMatrix(), ASSERT, BlastRPSInfo::aux_info, Blast_GetOneQueryStructs(), Blast_HSPListFree(), Blast_HSPResultsInsertHSPList(), Blast_HSPResultsSortByEvalue(), Blast_KarlinBlkCopy(), Blast_KarlinBlkNew(), Blast_RedoAlignmentCore(), Blast_TracebackFromHSPList(), Blast_TracebackGetEncoding(), BLASTAA_SIZE, BLASTERR_INTERRUPTED, BlastHSPStreamRead(), BlastHSPStreamTBackClose(), BlastQueryInfoFree(), BlastQueryInfoNew(), BlastSeqSrcGetSequence(), BlastSeqSrcReleaseSequence(), BlastSequenceBlkFree(), BlastExtensionOptions::compositionBasedStats, BlastQueryInfo::contexts, SBlastScoreMatrix::data, eBlastTypeRpsTblastn, BlastSeqSrcGetSeqArg::encoding, FALSE, BlastQueryInfo::first_context, SPsiBlastScoreMatrix::freq_ratios, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastHitSavingOptions::hitlist_size, BlastHSPList::hspcnt, Blast_KarlinBlk::K, BlastRPSAuxInfo::karlin_k, kBlastHSPStream_Eof, BlastScoreBlk::kbp_gap, BlastScoreBlk::kbp_gap_psi, BlastScoreBlk::kbp_psi, BlastQueryInfo::last_context, BLAST_SequenceBlk::length, log, Blast_KarlinBlk::logK, BlastQueryInfo::max_length, NULL, BlastRPSProfileHeader::num_profiles, BlastQueryInfo::num_queries, BlastScoreBlk::number_of_contexts, OffsetArrayToContextOffsets(), offsets, BlastHSPList::oid, BlastSeqSrcGetSeqArg::oid, BlastExtensionParameters::options, BlastHitSavingParameters::options, BlastGapAlignStruct::positionBased, BlastRPSInfo::profile_header, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, query, BlastHSPList::query_index, BlastContextInfo::query_offset, results, RPS_K_MULT, RPSPsiMatrixDetach(), RPSRescalePssm(), s_BlastHSPListRPSUpdate(), s_RPSFillFreqRatiosInPsiMatrix(), s_RPSGapAlignDataPrepare(), BlastGapAlignStruct::sbp, BlastScoringParameters::scale_factor, BlastSeqSrcGetSeqArg::seq, BLAST_SequenceBlk::sequence, sfree, BlastScoringParameters::shift_pen, and TRUE.

Referenced by BLAST_ComputeTraceback_MT().

◆ s_RPSFillFreqRatiosInPsiMatrix()

static void s_RPSFillFreqRatiosInPsiMatrix ( SPsiBlastScoreMatrix psi_matrix,
Int4 **  freq,
Int4  ncol 
)
static

◆ s_RPSGapAlignDataPrepare()

static Int2 s_RPSGapAlignDataPrepare ( BlastQueryInfo concat_db_info,
BlastGapAlignStruct gap_align,
const BlastRPSInfo rps_info,
Int4 ***  rps_freq 
)
static

Prepares an auxiliary BlastQueryInfo structure for the concatenated database and creates a memory mapped PSSM for RPS BLAST traceback.

Parameters
concat_db_infoBlastQueryInfo structure to fill. [out]
gap_alignGapped alignment structure to modify [in] [out]
rps_infoRPS BLAST information structure [in]

Definition at line 932 of file blast_traceback.c.

References ASSERT, eBlastTypeRpsBlast, BlastRPSInfo::freq_ratios_header, BlastRPSProfileHeader::magic_number, malloc(), NULL, BlastRPSProfileHeader::num_profiles, OffsetArrayToContextOffsets(), BlastGapAlignStruct::positionBased, BlastRPSInfo::profile_header, RPS_MAGIC_NUM, RPSPsiMatrixAttach(), BlastGapAlignStruct::sbp, BlastRPSProfileHeader::start_offsets, BlastRPSFreqRatiosHeader::start_offsets, and TRUE.

Referenced by s_RPSComputeTraceback().

◆ s_SThreadLocalDataArraySetGapXDropoffFinal()

static void s_SThreadLocalDataArraySetGapXDropoffFinal ( SThreadLocalDataArray array)
static

Set the raw X-dropoff value for the final gapped extension with traceback.

Definition at line 1424 of file blast_traceback.c.

References i.

Referenced by BLAST_ComputeTraceback_MT().

Modified on Fri Sep 20 14:57:43 2024 by modify_doxy.py rev. 669887