NCBI C++ ToolKit
Functions
blast_traceback.h File Reference

Functions to do gapped alignment with traceback. More...

#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/blast_export.h>
#include <algo/blast/core/blast_program.h>
#include <algo/blast/core/blast_def.h>
#include <algo/blast/core/blast_options.h>
#include <algo/blast/core/blast_parameters.h>
#include <algo/blast/core/blast_gapalign.h>
#include <algo/blast/core/blast_encoding.h>
#include <algo/blast/core/blast_hits.h>
#include <algo/blast/core/blast_seqsrc.h>
#include <algo/blast/core/blast_hspstream.h>
#include <algo/blast/core/pattern.h>
+ Include dependency graph for blast_traceback.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Go to the SVN repository for this file.

Functions

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. More...
 
EBlastEncoding Blast_TracebackGetEncoding (EBlastProgramType program_number)
 Get the subject sequence encoding type for the traceback, given a program number. More...
 
Int2 Blast_HSPUpdateWithTraceback (BlastGapAlignStruct *gap_align, BlastHSP *hsp)
 Modifies the HSP data after the final gapped alignment. 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, 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...
 
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...
 
BlastSeqSrcSetRangesArgBLAST_SetupPartialFetching (EBlastProgramType program_number, BlastSeqSrc *seq_src, const BlastHSPList **hsp_list, Int4 num_hsplists)
 Attempts to set up partial fetching, if it fails (e.g. More...
 

Detailed Description

Functions to do gapped alignment with traceback.

Definition in file blast_traceback.h.

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_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 1788 of file blast_traceback.c.

References Blast_RunTracebackSearchWithInterrupt(), NULL, and query.

◆ 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 1808 of file blast_traceback.c.

References BLAST_ComputeTraceback_MT(), BLASTERR_MEMORY, BlastHSPCBSStreamClose(), BlastHSPStreamClose(), BlastExtensionOptions::compositionBasedStats, BlastHitSavingOptions::hitlist_size, NULL, query, 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, 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(), 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().

Modified on Wed Apr 17 13:10:11 2024 by modify_doxy.py rev. 669887