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...
BlastSeqSrcSetRangesArg *	BLAST_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_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]

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_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().

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

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.

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

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().

BLAST_SetupPartialFetching()

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().

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_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().

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().