NCBI C++ ToolKit
|
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"
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... | |
BlastSeqSrcSetRangesArg * | BLAST_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... | |
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.
#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.
#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.
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.
program_number | Type of the BLAST program [in] |
hsp_stream | A stream for reading HSP lists [in] |
query | The query sequence [in] |
query_info | Information about the query [in] |
seq_src | Source of subject sequences [in] |
gap_align | The auxiliary structure for gapped alignment [in] |
score_params | Scoring parameters (esp. scale factor) [in] |
ext_params | Gapped extension parameters [in] |
hit_params | Parameters for saving hits. Can change if not a database search [in] |
eff_len_params | Parameters for recalculating effective search space. Can change if not a database search. [in] |
db_options | Options containing database genetic code string [in] |
psi_options | Options for iterative searches [in] |
rps_info | RPS BLAST auxiliary data structure [in] |
pattern_blk | PHI BLAST auxiliary data structure [in] |
results | All results from the BLAST search [out] |
interrupt_search | function callback to allow interruption of BLAST search [in, optional] |
progress_info | contains information about the progress of the current BLAST search [in|out] |
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().
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().
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.
gap_align | Structure containing gapped alignment information [in] |
hsp | Original 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().
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.
program | BLAST program type [in] |
query | Query sequence(s) structure [in] |
query_info | Additional query information [in] |
seq_src | Source of subject sequences [in] |
score_options | Scoring options [in] |
ext_options | Word extension options, needed for cutoff scores calculation only [in] |
hit_options | Hit saving options [in] |
eff_len_options | Options for calculating effective lengths [in] |
db_options | Database options (database genetic code) [in] |
psi_options | PSI BLAST options [in] |
sbp | Scoring block with statistical parameters and matrix [in] |
hsp_stream | Source of HSP lists. [in] |
rps_info | RPS database information structure [in] |
pattern_blk | PHI BLAST auxiliary data structure [in] |
results | Where to save the results after traceback. [out] |
num_threads | Maximum number of threads to spawn [in] |
Definition at line 1789 of file blast_traceback.c.
References Blast_RunTracebackSearchWithInterrupt(), NULL, query, and results.
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.
program | BLAST program type [in] |
query | Query sequence(s) structure [in] |
query_info | Additional query information [in] |
seq_src | Source of subject sequences [in] |
score_options | Scoring options [in] |
ext_options | Word extension options, needed for cutoff scores calculation only [in] |
hit_options | Hit saving options [in] |
eff_len_options | Options for calculating effective lengths [in] |
db_options | Database options (database genetic code) [in] |
psi_options | PSI BLAST options [in] |
sbp | Scoring block with statistical parameters and matrix [in] |
hsp_stream | Source of HSP lists. [in] |
rps_info | RPS database information structure [in] |
pattern_blk | PHI BLAST auxiliary data structure [in] |
results | Where to save the results after traceback. [out] |
interrupt_search | User specified function to interrupt search [in] |
progress_info | User supplied data structure to aid interrupt [in] |
num_threads | Maximum 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().
BlastSeqSrcSetRangesArg* BLAST_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.
: due to memory allocation failure), it cleans up and exits silently.
Definition at line 1324 of file blast_traceback.c.
References ASSERT, Blast_SubjectIsTranslated(), BlastSeqSrcGetSeqLen(), BlastSeqSrcGetSupportsPartialFetching(), BlastSeqSrcSetRangesArgAddRange(), BlastSeqSrcSetRangesArgBuild(), BlastSeqSrcSetRangesArgFree(), BlastSeqSrcSetRangesArgNew(), CODON_LENGTH, BlastSeg::end, FALSE, BlastSeg::frame, BlastHSPList::hsp_array, BlastHSPList::hspcnt, i, len, NULL, BlastSeg::offset, BlastHSPList::oid, BlastSeqSrcSetRangesArg::oid, BlastHSP::subject, and TRUE.
Referenced by BLAST_ComputeTraceback_MT(), Blast_RedoAlignmentCore_MT(), and BOOST_AUTO_TEST_CASE().
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:
program_number | Type of BLAST program [in] |
hsp_list | List of HSPs [in] |
query_blk | The query sequence [in] |
subject_blk | The subject sequence [in] |
query_info | Query information, needed to get pointer to the start of this query within the concatenated sequence [in] |
gap_align | Auxiliary structure used for gapped alignment [in] |
sbp | Statistical parameters [in] |
score_params | Scoring parameters (esp. scale factor) [in] |
ext_options | Gapped extension options [in] |
hit_params | Hit saving parameters [in] |
gen_code_string | specifies genetic code [in] |
fence_hit | True 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().
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().
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.
sbp | BlastScoreBlk structure to modify [in|out] |
rps_pssm | PSSMs in RPS-BLAST database to use [in] |
alphabet_size | Elements 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().
void RPSPsiMatrixDetach | ( | BlastScoreBlk * | sbp | ) |
Remove the artificially built SPsiBlastScoreMatrix structure allocated by RPSPsiMatrixAttach.
sbp | BlastScoreBlk 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().
|
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.
program | Program type: RPS or RPS tblastn [in] |
hsplist | List 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().
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.
hsp | HSP 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().
|
static |
Delete extra subject sequences hits, if after-traceback hit list size is smaller than preliminary hit list size.
results | All results after traceback, assumed already sorted by best e-value [in] [out] |
hitlist_size | Final 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().
|
static |
Delete hsps below query coverage percentage.
results | All results after traceback [in] [out] |
hit_options | hits options [in] |
query_info | query info [in] |
program_number | blast program number [in] |
Definition at line 837 of file blast_traceback.c.
References Blast_HitListPurgeNullHSPLists(), Blast_HSPListFree(), Blast_HSPListReapByQueryCoverage(), Blast_HSPListSubjectBestHit(), Blast_TrimHSPListByMaxHsps(), BlastHitSavingOptions::hsp_filt_opt, BlastHSPList::hspcnt, BlastHitList::hsplist_array, BlastHitList::hsplist_count, BlastHitSavingOptions::max_hsps_per_subject, NULL, BlastHitSavingOptions::query_cov_hsp_perc, results, and BlastHSPFilteringOptions::subject_besthit_opts.
Referenced by BLAST_ComputeTraceback_MT().
|
static |
Updates the e-values after the traceback alignment.
Also includes relinking of HSPs in case of sum statistics and calculation of bit scores.
program_number | Type of BLAST program [in] |
hsp_list | HSPList obtained after a traceback alignment [in] [out] |
query_info | Query information structure [in] |
score_params | Scoring parameters [in] |
hit_params | Hit saving parameters [in] |
sbp | Scoring block [in] |
subject_length | Length 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().
|
static |
Remove scaling from scores previously calculated on the hsp_list.
hsp_list | list of HPSs with the score field calculated [in|out] |
scale_factor | factor 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().
|
static |
Performs traceback alignment for one HSP list in a PHI BLAST search.
program_number | eBlastTypePhiBlastn or eBlastTypePhiBlastp [in] |
hsp_list | HSP list for a single query/subject pair, with preliminary alignment information [in] |
query_blk | Query sequence [in] |
subject_blk | Subject sequence [in] |
gap_align | Gapped alignment structure [in] |
sbp | Scoring block [in] |
score_params | Scoring parameters [in] |
hit_params | Hit saving parameters [in] |
query_info | Query information, including pattern occurrences in query [in] |
pattern_blk | Pattern 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().
|
static |
Compute traceback information for alignments found by an RPS blast search.
This function performs two major tasks:
program_number | Type of the BLAST program [in] |
hsp_stream | A stream for reading HSP lists [in] |
seq_src | Source of RPS database consensus sequences; needed only to calculate number of identities in alignments [in] |
query | The original query sequence [in] |
query_info | Information associated with the original query. Only used for the search space [in] |
gap_align | The auxiliary structure for gapped alignment [in] |
score_params | Scoring parameters (esp. scale factor) [in] |
ext_params | Gapped extension parameters [in] |
hit_params | Parameters for saving hits. Can change if not a database search [in] |
rps_info | Extra information about RPS database. [in] |
results | Results structure containing all HSPs, with added traceback information. [out] |
interrupt_search | function callback to allow interruption of BLAST search [in, optional] |
progress_info | contains information about the progress of the current BLAST search [in|out] |
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().
|
static |
Definition at line 991 of file blast_traceback.c.
References _PSIAllocateMatrix(), BLASTAA_SIZE, FREQ_RATIO_SCALE, SPsiBlastScoreMatrix::freq_ratios, SBlastScoreMatrix::ncols, SBlastScoreMatrix::nrows, and SPsiBlastScoreMatrix::pssm.
Referenced by s_RPSComputeTraceback().
|
static |
Prepares an auxiliary BlastQueryInfo structure for the concatenated database and creates a memory mapped PSSM for RPS BLAST traceback.
concat_db_info | BlastQueryInfo structure to fill. [out] |
gap_align | Gapped alignment structure to modify [in] [out] |
rps_info | RPS 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().
|
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().