NCBI C++ ToolKit
Macros | Enumerations | Functions
blast_gapalign.c File Reference

Functions to perform gapped alignment. More...

#include <algo/blast/core/ncbi_math.h>
#include <algo/blast/core/blast_gapalign.h>
#include <algo/blast/core/blast_util.h>
#include <algo/blast/core/greedy_align.h>
#include "blast_gapalign_priv.h"
#include "blast_hits_priv.h"
#include "blast_itree.h"
#include "jumper.h"
+ Include dependency graph for blast_gapalign.c:

Go to the source code of this file.

Go to the SVN repository for this file.

Macros

#define MININT   INT4_MIN/2
 Lower bound for scores. More...
 
#define CHUNKSIZE   2097152
 Minimal size of a chunk for state array allocation. More...
 
#define RESTRICT_SIZE   10
 For restricted gapped alignment, gaps may only start once in this many sequence offsets. More...
 
#define MAX_SUBJECT_OFFSET   90000
 Maximal subject length after which the offsets are adjusted to a subsequence. More...
 
#define MAX_TOTAL_GAPS   3000
 Approximate upper bound on a number of gaps in an HSP, needed to determine the length of the subject subsequence to be retrieved for alignment with traceback. More...
 

Enumerations

enum  {
  SCRIPT_SUB = eGapAlignSub , SCRIPT_GAP_IN_A = eGapAlignDel , SCRIPT_GAP_IN_B = eGapAlignIns , SCRIPT_OP_MASK = 0x07 ,
  SCRIPT_EXTEND_GAP_A = 0x10 , SCRIPT_EXTEND_GAP_B = 0x40
}
 Values for the editing script operations in traceback. More...
 
enum  {
  SCRIPT_AHEAD_ONE_FRAME = 1 , SCRIPT_AHEAD_TWO_FRAMES = 2 , SCRIPT_NEXT_IN_FRAME = 3 , SCRIPT_NEXT_PLUS_ONE_FRAME = 4 ,
  SCRIPT_NEXT_PLUS_TWO_FRAMES = 5 , SCRIPT_OOF_OPEN_GAP = 0x08
}
 Editing script operations for out-of-frame traceback. More...
 

Functions

static Int2 s_BlastDynProgNtGappedAlignment (BLAST_SequenceBlk *query_blk, BLAST_SequenceBlk *subject_blk, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, BlastInitHSP *init_hsp)
 Performs dynamic programming style gapped extension, given an initial HSP (offset pair), two sequence blocks and scoring and extension options. More...
 
static Int4 s_BlastAlignPackedNucl (Uint1 *B, Uint1 *A, Int4 N, Int4 M, Int4 *b_offset, Int4 *a_offset, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Boolean reverse_sequence, Int4 x_dropoff)
 Aligns two nucleotide sequences, one (A) should be packed in the same way as the BLAST databases, the other (B) should contain one basepair/byte. More...
 
static Int2 s_BlastProtGappedAlignment (EBlastProgramType program, BLAST_SequenceBlk *query_blk, BLAST_SequenceBlk *subject_blk, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, BlastInitHSP *init_hsp, Boolean restricted_alignment, Boolean *fence_hit)
 Performs gapped extension for protein sequences, given two sequence blocks, scoring and extension options, and an initial HSP with information from the previously performed ungapped extension. More...
 
static GapStateArrayStructs_GapGetState (GapStateArrayStruct **head, Int4 length)
 Retrieve the state structure corresponding to a given length. More...
 
static Boolean s_GapPurgeState (GapStateArrayStruct *state_struct)
 Remove a state from a state structure. More...
 
static SGreedyAlignMems_BlastGreedyAlignsFree (SGreedyAlignMem *gamp)
 Deallocate the memory for greedy gapped alignment. More...
 
static SGreedyAlignMems_BlastGreedyAlignMemAlloc (const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, Int4 max_d, Int4 Xdrop)
 Allocate memory for the greedy gapped alignment algorithm. More...
 
BlastGapAlignStructBLAST_GapAlignStructFree (BlastGapAlignStruct *gap_align)
 Deallocates memory in the BlastGapAlignStruct structure. More...
 
Int2 BLAST_GapAlignStructNew (const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, Uint4 max_subject_length, BlastScoreBlk *sbp, BlastGapAlignStruct **gap_align_ptr)
 Initializes the BlastGapAlignStruct structure. More...
 
Int4 ALIGN_EX (const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed, Boolean reverse_sequence, Boolean *fence_hit)
 Low level function to perform dynamic programming gapped extension with traceback. More...
 
Int4 Blast_SemiGappedAlign (const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed, Boolean reverse_sequence, Boolean *fence_hit)
 Low level function to perform gapped extension in one direction with or without traceback. More...
 
static Int4 s_RestrictedGappedAlign (const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reverse_sequence)
 Low level function to perform score-only gapped extension in one direction. More...
 
static Int4 s_OutOfFrameAlignWithTraceback (const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed)
 Low level function to perform gapped extension with out-of-frame gapping with traceback. More...
 
static Int4 s_OutOfFrameGappedAlign (const Uint1 *A, const Uint1 *B, Int4 M, Int4 N, Int4 *a_offset, Int4 *b_offset, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 query_offset, Boolean reversed)
 Low level function to perform gapped extension with out-of-frame gapping with or without traceback. More...
 
static NCBI_INLINE Int4 s_GetUngappedHSPContext (const BlastQueryInfo *query_info, const BlastInitHSP *init_hsp)
 Simple wrapper around binary search function for BlastQueryInfo structure to obtain the context in which this initial ungapped HSP is found. More...
 
static NCBI_INLINE void s_AdjustInitialHSPOffsets (BlastInitHSP *init_hsp, Int4 query_start)
 Adjust the HSP offsets in the initial ungapped HSP structure given the query start. More...
 
static void s_SetUpLocalBlastSequenceBlk (const BLAST_SequenceBlk *concatenated_query, const BlastQueryInfo *query_info, Int4 context, BLAST_SequenceBlk *single_query, Int4 *query_start)
 Set up a BLAST_SequenceBlk structure for a single query sequence. More...
 
static void s_AdjustHspOffsetsAndGetQueryData (const BLAST_SequenceBlk *query, const BlastQueryInfo *query_info, BlastInitHSP *init_hsp, BLAST_SequenceBlk *query_out, Int4 *context)
 Find the HSP offsets relative to the individual query sequence instead of the concatenated sequence and retrieve relevant portions of the query sequence data. More...
 
GapEditScriptBlast_PrelimEditBlockToGapEditScript (GapPrelimEditBlock *rev_prelim_tback, GapPrelimEditBlock *fwd_prelim_tback)
 Convert the initial list of traceback actions from a non-OOF gapped alignment into a blast edit script. More...
 
static Int2 s_BlastGreedyGapAlignStructFill (BlastGapAlignStruct *gap_align, Int4 q_start, Int4 s_start, Int4 q_end, Int4 s_end, Int4 q_seed_start, Int4 s_seed_start, Int4 score, GapEditScript *esp)
 Fills the BlastGapAlignStruct structure with the results of a greedy gapped extension. More...
 
static void s_UpdateEditScript (GapEditScript *esp, int pos, int bf, int af)
 
static void s_RebuildEditScript (GapEditScript *esp)
 
static void s_ReduceGaps (GapEditScript *esp, const Uint1 *q, const Uint1 *s, const Uint1 *qf, const Uint1 *sf)
 
Int2 BLAST_GreedyGappedAlignment (const Uint1 *query, const Uint1 *subject, Int4 query_length, Int4 subject_length, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 q_off, Int4 s_off, Boolean compressed_subject, Boolean do_traceback, Boolean *fence_hit)
 Greedy gapped alignment, with or without traceback. More...
 
Boolean BlastGetOffsetsForGappedAlignment (const Uint1 *query, const Uint1 *subject, const BlastScoreBlk *sbp, BlastHSP *hsp, Int4 *q_retval, Int4 *s_retval)
 Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the middle of this. More...
 
void BlastGetStartForGappedAlignmentNucl (const Uint1 *query, const Uint1 *subject, BlastHSP *hsp)
 Function to look for the longest identity match run (up to size HSP_MAX_IDENT_RUN) in an HSP and return the middle of this. More...
 
Int4 BlastGetStartForGappedAlignment (const Uint1 *query, const Uint1 *subject, const BlastScoreBlk *sbp, Uint4 q_start, Uint4 q_length, Uint4 s_start, Uint4 s_length)
 Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the middle of this. More...
 
Int2 BLAST_GetGappedScore (EBlastProgramType program_number, BLAST_SequenceBlk *query, BlastQueryInfo *query_info, BLAST_SequenceBlk *subject, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, const BlastExtensionParameters *ext_params, const BlastHitSavingParameters *hit_params, BlastInitHitList *init_hitlist, BlastHSPList **hsp_list_ptr, BlastGappedStats *gapped_stats, Boolean *fence_hit)
 Performs gapped extension for all non-Mega BLAST programs, given that ungapped extension has been done earlier. More...
 
static Int4 s_OutOfFrameSemiGappedAlignWrap (const Uint1 *query, const Uint1 *subject, Int4 q_off, Int4 s_off, Int4 *private_q_start, Int4 *private_s_start, Boolean score_only, GapPrelimEditBlock *edit_block, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 psi_offset, Boolean reversed, Boolean switch_seq)
 Out-of-frame gapped alignment wrapper function. More...
 
void AdjustSubjectRange (Int4 *subject_offset_ptr, Int4 *subject_length_ptr, Int4 query_offset, Int4 query_length, Int4 *start_shift)
 Adjusts range of subject sequence to be passed for gapped extension, taking into account the length and starting position of the alignment in query. More...
 
static Int2 s_BlastOOFTracebackToGapEditScript (GapPrelimEditBlock *rev_prelim_tback, GapPrelimEditBlock *fwd_prelim_tback, Int4 nucl_align_length, GapEditScript **edit_script_ptr)
 Converts OOF traceback from a gapped alignment to a GapEditScript. More...
 
Int2 BLAST_GappedAlignmentWithTraceback (EBlastProgramType program, const Uint1 *query, const Uint1 *subject, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 q_start, Int4 s_start, Int4 query_length, Int4 subject_length, Boolean *fence_hit)
 Perform a gapped alignment with traceback. More...
 
Int2 BLAST_GetUngappedHSPList (BlastInitHitList *init_hitlist, BlastQueryInfo *query_info, BLAST_SequenceBlk *subject, const BlastHitSavingOptions *hit_options, BlastHSPList **hsp_list_ptr)
 Convert initial HSP list to an HSP list: to be used in ungapped search. More...
 

Detailed Description

Functions to perform gapped alignment.

Definition in file blast_gapalign.c.

Macro Definition Documentation

◆ CHUNKSIZE

#define CHUNKSIZE   2097152

Minimal size of a chunk for state array allocation.

Definition at line 61 of file blast_gapalign.c.

◆ MAX_SUBJECT_OFFSET

#define MAX_SUBJECT_OFFSET   90000

Maximal subject length after which the offsets are adjusted to a subsequence.

Definition at line 3910 of file blast_gapalign.c.

◆ MAX_TOTAL_GAPS

#define MAX_TOTAL_GAPS   3000

Approximate upper bound on a number of gaps in an HSP, needed to determine the length of the subject subsequence to be retrieved for alignment with traceback.

Definition at line 3915 of file blast_gapalign.c.

◆ MININT

#define MININT   INT4_MIN/2

Lower bound for scores.

Divide by two to prevent underflows.

Definition at line 58 of file blast_gapalign.c.

◆ RESTRICT_SIZE

#define RESTRICT_SIZE   10

For restricted gapped alignment, gaps may only start once in this many sequence offsets.

Definition at line 958 of file blast_gapalign.c.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Values for the editing script operations in traceback.

Enumerator
SCRIPT_SUB 

Substitution.

SCRIPT_GAP_IN_A 

Deletion.

SCRIPT_GAP_IN_B 

Insertion.

SCRIPT_OP_MASK 

Mask for edit script operations.

SCRIPT_EXTEND_GAP_A 

continue a gap in A

SCRIPT_EXTEND_GAP_B 

continue a gap in B

Definition at line 355 of file blast_gapalign.c.

◆ anonymous enum

anonymous enum

Editing script operations for out-of-frame traceback.

Enumerator
SCRIPT_AHEAD_ONE_FRAME 

Shift 1 frame in sequence A (gap 2 nucleotides)

SCRIPT_AHEAD_TWO_FRAMES 

Shift 2 frames in sequence A (gap 1 nucleotide)

SCRIPT_NEXT_IN_FRAME 

Shift to next base (substitution)

SCRIPT_NEXT_PLUS_ONE_FRAME 

Shift to next base plus 1 frame (gap 1 nucleotide in sequence B)

SCRIPT_NEXT_PLUS_TWO_FRAMES 

Shift to next base plus 2 frames (gap 2 nucleotides in sequence B)

SCRIPT_OOF_OPEN_GAP 

Opening a gap.

Definition at line 1295 of file blast_gapalign.c.

Function Documentation

◆ AdjustSubjectRange()

void AdjustSubjectRange ( Int4 subject_offset_ptr,
Int4 subject_length_ptr,
Int4  query_offset,
Int4  query_length,
Int4 start_shift 
)

Adjusts range of subject sequence to be passed for gapped extension, taking into account the length and starting position of the alignment in query.

Parameters
subject_offset_ptrStart of the subject range [out]
subject_length_ptrLength of the subject range [out]
query_offsetOffset in query from which alignment starts [in]
query_lengthLength of the query sequence [in]
start_shiftThe offset by which the output range is shifted with respect to the full subject sequence [out]

Definition at line 3918 of file blast_gapalign.c.

References MAX_SUBJECT_OFFSET, MAX_TOTAL_GAPS, and MIN.

Referenced by Blast_TracebackFromHSPList(), and s_BlastProtGappedAlignment().

◆ ALIGN_EX()

Int4 ALIGN_EX ( const Uint1 A,
const Uint1 B,
Int4  M,
Int4  N,
Int4 a_offset,
Int4 b_offset,
GapPrelimEditBlock edit_block,
BlastGapAlignStruct gap_align,
const BlastScoringParameters scoringParams,
Int4  query_offset,
Boolean  reversed,
Boolean  reverse_sequence,
Boolean hit_fence 
)

Low level function to perform dynamic programming gapped extension with traceback.

Parameters
AThe query sequence [in]
BThe subject sequence [in]
MMaximal extension length in query [in]
NMaximal extension length in subject [in]
a_offsetResulting starting offset in query [out]
b_offsetResulting starting offset in subject [out]
edit_blockStructure to hold traceback generated [out]
gap_alignStructure holding various information and allocated memory for the gapped alignment [in]
scoringParamsParameters related to scoring [in]
query_offsetThe starting offset in query [in]
reversedHas the sequence been reversed? Used for psi-blast [in]
reverse_sequenceDo reverse the sequence [in]
hit_fenceIf NULL, set to TRUE if the extension encountered sequence letters that indicate finding a region of B that is uninitialized [out]
Returns
The best alignment score found.

Definition at line 366 of file blast_gapalign.c.

References A, BlastGapDP::best, BlastGapDP::best_gap, SBlastScoreMatrix::data, done, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, FENCE_SENTRY, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, GapPrelimEditBlockAdd(), i, malloc(), BlastScoreBlk::matrix, MAX, MININT, N, NULL, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, s_GapGetState(), s_GapPurgeState(), BlastGapAlignStruct::sbp, SCRIPT_EXTEND_GAP_A, SCRIPT_EXTEND_GAP_B, SCRIPT_GAP_IN_A, SCRIPT_GAP_IN_B, SCRIPT_OP_MASK, SCRIPT_SUB, sfree, GapStateArrayStruct::state_array, BlastGapAlignStruct::state_struct, and GapStateArrayStruct::used.

Referenced by BLAST_GappedAlignmentWithTraceback(), Blast_SemiGappedAlign(), and s_SWFindFinalEndsUsingXdrop().

◆ BLAST_GapAlignStructFree()

BlastGapAlignStruct* BLAST_GapAlignStructFree ( BlastGapAlignStruct gap_align)

◆ BLAST_GapAlignStructNew()

Int2 BLAST_GapAlignStructNew ( const BlastScoringParameters score_params,
const BlastExtensionParameters ext_params,
Uint4  max_subject_length,
BlastScoreBlk sbp,
BlastGapAlignStruct **  gap_align_ptr 
)

Initializes the BlastGapAlignStruct structure.

Parameters
score_paramsParameters related to scoring alignments [in]
ext_paramsparameters related to gapped extension [in]
max_subject_lengthMaximum length of any subject sequence (needed for greedy extension allocation only) [in]
sbpThe scoring information block [in]
gap_align_ptrThe BlastGapAlignStruct structure [out]

Definition at line 291 of file blast_gapalign.c.

References BLAST_GapAlignStructFree(), calloc(), BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, eDynProgScoreOnly, eJumperWithTraceback, BlastExtensionOptions::ePrelimGapExt, BlastGapAlignStruct::fwd_prelim_tback, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, BlastExtensionParameters::gap_x_dropoff, GapPrelimEditBlockNew(), BlastGapAlignStruct::greedy_align_mem, GREEDY_MAX_COST, GREEDY_MAX_COST_FRACTION, BlastGapAlignStruct::jumper, JumperGapAlignNew(), malloc(), MAX, MAX_DBSEQ_LEN, BlastGapAlignStruct::max_mismatches, BlastExtensionOptions::max_mismatches, MIN, BlastGapAlignStruct::mismatch_window, BlastExtensionOptions::mismatch_window, NULL, BlastExtensionParameters::options, BlastScoringParameters::penalty, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, BlastGapAlignStruct::rev_prelim_tback, s_BlastGreedyAlignMemAlloc(), and BlastGapAlignStruct::sbp.

Referenced by BLAST_GapAlignSetUp(), Blast_RedoAlignmentCore_MT(), BOOST_AUTO_TEST_CASE(), and CBlastExtendTestFixture::setupStructures().

◆ BLAST_GappedAlignmentWithTraceback()

Int2 BLAST_GappedAlignmentWithTraceback ( EBlastProgramType  program,
const Uint1 query,
const Uint1 subject,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  q_start,
Int4  s_start,
Int4  query_length,
Int4  subject_length,
Boolean fence_hit 
)

Perform a gapped alignment with traceback.

Parameters
programType of BLAST program [in]
queryThe query sequence [in]
subjectThe subject sequence [in]
gap_alignThe gapped alignment structure [in] [out]
score_paramsScoring parameters [in]
q_startOffset in query where to start alignment [in]
s_startOffset in subject where to start alignment [in]
query_lengthMaximal allowed extension in query [in]
subject_lengthMaximal allowed extension in subject [in]
fence_hitTrue is returned here if overrun is detected. [in]

Definition at line 4304 of file blast_gapalign.c.

References ALIGN_EX(), ASSERT, Blast_PrelimEditBlockToGapEditScript(), CODON_LENGTH, eBlastTypeBlastx, BlastGapAlignStruct::edit_script, eGapAlignDel, eGapAlignSub, FALSE, BlastGapAlignStruct::fwd_prelim_tback, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, GapPrelimEditBlockReset(), i, BlastScoringOptions::is_ooframe, NULL, GapEditScript::num, GapEditScript::op_type, BlastScoringParameters::options, query, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, BlastGapAlignStruct::rev_prelim_tback, s_BlastOOFTracebackToGapEditScript(), s_OutOfFrameSemiGappedAlignWrap(), BlastGapAlignStruct::score, GapEditScript::size, subject, BlastGapAlignStruct::subject_start, BlastGapAlignStruct::subject_stop, and TRUE.

Referenced by Blast_TracebackFromHSPList(), and s_RedoOneAlignment().

◆ BLAST_GetGappedScore()

Int2 BLAST_GetGappedScore ( EBlastProgramType  program_number,
BLAST_SequenceBlk query,
BlastQueryInfo query_info,
BLAST_SequenceBlk subject,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
const BlastExtensionParameters ext_params,
const BlastHitSavingParameters hit_params,
BlastInitHitList init_hitlist,
BlastHSPList **  hsp_list_ptr,
BlastGappedStats gapped_stats,
Boolean fence_hit 
)

Performs gapped extension for all non-Mega BLAST programs, given that ungapped extension has been done earlier.

Sorts initial HSPs by score (from ungapped extension); Deletes HSPs that are included in already extended HSPs; Performs gapped extension; Saves HSPs into an HSP list.

Parameters
program_numberType of BLAST program [in]
queryThe query sequence block [in]
query_infoQuery information structure, containing offsets into the concatenated sequence [in]
subjectThe subject sequence block [in]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsOptions and parameters related to scoring [in]
ext_paramsOptions and parameters related to extensions [in]
hit_paramsOptions related to saving hits [in]
init_hitlistList of initial HSPs (offset pairs with additional information from the ungapped alignment performed earlier) [in]
hsp_list_ptrStructure containing all saved HSPs [out]
gapped_statsReturn statistics (not filled if NULL) [out]
fence_hitTrue is returned here if overrun is detected. [in]

Definition at line 3434 of file blast_gapalign.c.

References ASSERT, BLAST_FrameToContext(), Blast_GetQueryIndexFromContext(), Blast_GetQueryIndexFromQueryOffset(), BLAST_GreedyGappedAlignment(), Blast_HSPFree(), Blast_HSPInit(), Blast_HSPListFree(), Blast_HSPListNew(), Blast_HSPListSaveHSP(), Blast_InitHitListIsSortedByScore(), Blast_IntervalTreeFree(), Blast_IntervalTreeInit(), Blast_IntervalTreeReset(), Blast_ProgramIsRpsBlast(), Blast_SubjectIsTranslated(), BLASTERR_MEMORY, BlastGetStartForGappedAlignment(), BlastHspNumMax(), BlastIntervalTreeAddHSP(), BlastIntervalTreeContainsHSP(), Boolean, calloc(), CODON_LENGTH, BlastHSP::context, context, BlastQueryInfo::contexts, BlastGappedCutoffs::cutoff_score, BlastHitSavingParameters::cutoffs, SBlastScoreMatrix::data, eBlastTypeBlastn, eBlastTypeBlastx, eBlastTypeMapping, eBlastTypePhiBlastn, eBlastTypeRpsBlast, eBlastTypeTblastn, BlastGapAlignStruct::edit_script, eGreedyScoreOnly, BlastSeg::end, BlastExtensionOptions::ePrelimGapExt, eQueryAndSubject, BlastGappedStats::extensions, FALSE, BlastQueryInfo::first_context, BlastSeg::frame, BlastContextInfo::frame, free(), GapEditScriptDelete(), BlastGapAlignStruct::greedy_query_seed_start, BlastGapAlignStruct::greedy_subject_seed_start, BlastHSPList::hsp_array, BlastHSPList::hspcnt, i, BlastInitHitList::init_hsp_array, INT4_MIN, BlastScoringOptions::is_ooframe, BlastQueryInfo::last_context, BLAST_SequenceBlk::length, BlastUngappedData::length, BlastHitSavingParameters::low_score, BlastHitSavingOptions::min_diag_separation, NULL, NUM_FRAMES, BlastQueryInfo::num_queries, BlastSeg::offset, BlastInitHSP::offsets, BlastExtensionParameters::options, BlastHitSavingParameters::options, BlastScoringParameters::options, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, BlastOffsetPair::q_off, BlastUngappedData::q_start, BlastOffsetPair::qs_offsets, BlastHSP::query, query, BlastContextInfo::query_length, BlastContextInfo::query_offset, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, BlastHitSavingParameters::restricted_align, s_AdjustHspOffsetsAndGetQueryData(), s_BlastDynProgNtGappedAlignment(), s_BlastProtGappedAlignment(), BlastOffsetPair::s_off, BlastUngappedData::s_start, BlastGapAlignStruct::sbp, BlastUngappedData::score, BlastGapAlignStruct::score, BlastHSP::score, BLAST_SequenceBlk::sequence, sfree, BlastHSP::subject, subject, BlastGapAlignStruct::subject_start, BlastGapAlignStruct::subject_stop, BlastInitHitList::total, TRUE, and BlastInitHSP::ungapped_data.

Referenced by BOOST_AUTO_TEST_CASE(), and s_BlastSetUpAuxStructures().

◆ BLAST_GetUngappedHSPList()

Int2 BLAST_GetUngappedHSPList ( BlastInitHitList init_hitlist,
BlastQueryInfo query_info,
BLAST_SequenceBlk subject,
const BlastHitSavingOptions hit_options,
BlastHSPList **  hsp_list_ptr 
)

Convert initial HSP list to an HSP list: to be used in ungapped search.

Ungapped data must be available in the initial HSP list for this function to work.

Parameters
init_hitlistList of initial HSPs with ungapped extension information [in]
query_infoQuery information structure, containing offsets into the concatenated queries/strands/frames [in]
subjectSubject sequence block containing frame information [in]
hit_optionsHit saving options [in]
hsp_list_ptrHSPs in the final form [out]

Definition at line 4474 of file blast_gapalign.c.

References Blast_HSPInit(), Blast_HSPListNew(), Blast_HSPListSaveHSP(), Blast_HSPListSortByScore(), BlastHspNumMax(), context, BlastQueryInfo::contexts, FALSE, BlastContextInfo::frame, BlastHSPList::hspcnt, BlastInitHitList::init_hsp_array, BlastUngappedData::length, NULL, BlastInitHSP::offsets, BlastOffsetPair::q_off, BlastUngappedData::q_start, BlastOffsetPair::qs_offsets, BlastContextInfo::query_offset, s_AdjustInitialHSPOffsets(), s_GetUngappedHSPContext(), BlastOffsetPair::s_off, BlastUngappedData::s_start, BlastUngappedData::score, subject, BlastInitHitList::total, and BlastInitHSP::ungapped_data.

Referenced by s_BlastSearchEngineOneContext().

◆ BLAST_GreedyGappedAlignment()

Int2 BLAST_GreedyGappedAlignment ( const Uint1 query,
const Uint1 subject,
Int4  query_length,
Int4  subject_length,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  q_off,
Int4  s_off,
Boolean  compressed_subject,
Boolean  do_traceback,
Boolean fence_hit 
)

Greedy gapped alignment, with or without traceback.

Given two sequences, relevant options and an offset pair, fills the gap_align structure with alignment endpoints and, if traceback is performed, gap information.

Parameters
queryThe query sequence [in]
subjectThe subject sequence [in]
query_lengthThe query sequence length [in]
subject_lengthThe subject sequence length [in]
gap_alignThe structure holding various information and memory needed for gapped alignment [in] [out]
score_paramsParameters related to scoring alignments [in]
q_offStarting offset in query [in]
s_offStarting offset in subject [in]
compressed_subjectIs subject sequence compressed? [in]
do_tracebackShould traceback be saved? [in]
fence_hitTrue is returned here if overrun is detected. [in]

Definition at line 2754 of file blast_gapalign.c.

References ASSERT, BLAST_AffineGreedyAlign(), BLAST_GapAlignStructFree(), Blast_PrelimEditBlockToGapEditScript(), FALSE, BlastGapAlignStruct::fwd_prelim_tback, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, GapPrelimEditBlockReset(), BlastGapAlignStruct::greedy_align_mem, SGreedySeed::match_length, SGreedyAlignMem::max_dist, MIN, NULL, BlastScoringParameters::penalty, query, BlastGapAlignStruct::rev_prelim_tback, BlastScoringParameters::reward, s_BlastGreedyAlignMemAlloc(), s_BlastGreedyAlignsFree(), s_BlastGreedyGapAlignStructFill(), s_ReduceGaps(), SGreedySeed::start_q, SGreedySeed::start_s, subject, TRUE, and SGreedyAlignMem::xdrop.

Referenced by BLAST_GetGappedScore(), and Blast_TracebackFromHSPList().

◆ Blast_PrelimEditBlockToGapEditScript()

GapEditScript* Blast_PrelimEditBlockToGapEditScript ( GapPrelimEditBlock rev_prelim_tback,
GapPrelimEditBlock fwd_prelim_tback 
)

Convert the initial list of traceback actions from a non-OOF gapped alignment into a blast edit script.

Note that this routine assumes the input edit blocks have not been reversed or rearranged by calling code

Parameters
rev_prelim_tbackTraceback from extension to the left [in]
fwd_prelim_tbackTraceback from extension to the right [in]
Returns
Pointer to the resulting edit script, or NULL if there are no traceback actions specified

Definition at line 2473 of file blast_gapalign.c.

References GapPrelimEditBlock::edit_ops, FALSE, GapEditScriptNew(), i, NULL, GapEditScript::num, GapPrelimEditScript::num, GapPrelimEditBlock::num_ops, GapEditScript::op_type, GapPrelimEditScript::op_type, ncbi::grid::netcache::search::fields::size, and TRUE.

Referenced by BLAST_GappedAlignmentWithTraceback(), BLAST_GreedyGappedAlignment(), PHIGappedAlignmentWithTraceback(), s_BlastOOFTracebackToGapEditScript(), and s_NewAlignmentUsingXdrop().

◆ Blast_SemiGappedAlign()

Int4 Blast_SemiGappedAlign ( const Uint1 A,
const Uint1 B,
Int4  M,
Int4  N,
Int4 a_offset,
Int4 b_offset,
Boolean  score_only,
GapPrelimEditBlock edit_block,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  query_offset,
Boolean  reversed,
Boolean  reverse_sequence,
Boolean fence_hit 
)

Low level function to perform gapped extension in one direction with or without traceback.

Parameters
AThe query sequence [in]
BThe subject sequence [in]
MMaximal extension length in query [in]
NMaximal extension length in subject [in]
a_offsetResulting starting offset in query [out]
b_offsetResulting starting offset in subject [out]
score_onlyOnly find the score, without saving traceback [in]
edit_blockStructure to hold generated traceback [out]
gap_alignStructure holding various information and allocated memory for the gapped alignment [in]
score_paramsParameters related to scoring [in]
query_offsetThe starting offset in query [in]
reversedHas the sequence been reversed? Used for psi-blast [in]
reverse_sequenceDo reverse the sequence [in]
fence_hitIf NULL, set to TRUE if the extension encountered sequence letters that indicate finding a region of B that is uninitialized [out]
Returns
The best alignment score found.

Definition at line 728 of file blast_gapalign.c.

References A, ALIGN_EX(), BlastGapDP::best, BlastGapDP::best_gap, SBlastScoreMatrix::data, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, i, malloc(), BlastScoreBlk::matrix, MAX, MININT, N, NULL, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, BlastGapAlignStruct::sbp, and sfree.

Referenced by PHIGappedAlignmentWithTraceback(), s_BlastProtGappedAlignment(), and s_PHIGappedAlignment().

◆ BlastGetOffsetsForGappedAlignment()

Boolean BlastGetOffsetsForGappedAlignment ( const Uint1 query,
const Uint1 subject,
const BlastScoreBlk sbp,
BlastHSP hsp,
Int4 q_retval,
Int4 s_retval 
)

Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the middle of this.

Used by the gapped-alignment functions to start the gapped alignments. Should be used instead of BlastGetStartForGappedAlignment

Parameters
queryThe query sequence [in]
subjectThe subject sequence [in]
sbpScoring block, containing matrix [in]
hspstart and stops of HSP [in]
q_retvalquery offset to use [out]
s_retvalsubject offset to use [out]

Definition at line 3240 of file blast_gapalign.c.

References SBlastScoreMatrix::data, BlastSeg::end, FALSE, HSP_MAX_WINDOW, BlastScoreBlk::matrix, MIN, NULL, BlastSeg::offset, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, BlastHSP::query, query, BlastHSP::subject, subject, and TRUE.

Referenced by Blast_TracebackFromHSPList(), and BOOST_AUTO_TEST_CASE().

◆ BlastGetStartForGappedAlignment()

Int4 BlastGetStartForGappedAlignment ( const Uint1 query,
const Uint1 subject,
const BlastScoreBlk sbp,
Uint4  q_start,
Uint4  q_length,
Uint4  s_start,
Uint4  s_length 
)

Function to look for the highest scoring window (of size HSP_MAX_WINDOW) in an HSP and return the middle of this.

Used by the gapped-alignment functions to start the gapped alignments.

Parameters
queryThe query sequence [in]
subjectThe subject sequence [in]
sbpScoring block, containing matrix [in]
q_startStarting offset in query [in]
q_lengthLength of HSP in query [in]
s_startStarting offset in subject [in]
s_lengthLength of HSP in subject [in]
Returns
The offset at which alignment should be started [out]

Definition at line 3385 of file blast_gapalign.c.

References SBlastScoreMatrix::data, HSP_MAX_WINDOW, BlastScoreBlk::matrix, MIN, NULL, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, query, and subject.

Referenced by BLAST_GetGappedScore().

◆ BlastGetStartForGappedAlignmentNucl()

void BlastGetStartForGappedAlignmentNucl ( const Uint1 query,
const Uint1 subject,
BlastHSP hsp 
)

Function to look for the longest identity match run (up to size HSP_MAX_IDENT_RUN) in an HSP and return the middle of this.

Used by the gapped-alignment functions to start the gapped alignments.

Parameters
queryThe query sequence [in]
subjectThe subject sequence [in]
hspOn return, the gapped_start will be filled. [in][out]

Definition at line 3315 of file blast_gapalign.c.

References BlastSeg::end, FALSE, BlastSeg::gapped_start, match(), MIN, BlastSeg::offset, offset, BlastHSP::query, query, BlastHSP::subject, and subject.

Referenced by Blast_TracebackFromHSPList().

◆ s_AdjustHspOffsetsAndGetQueryData()

static void s_AdjustHspOffsetsAndGetQueryData ( const BLAST_SequenceBlk query,
const BlastQueryInfo query_info,
BlastInitHSP init_hsp,
BLAST_SequenceBlk query_out,
Int4 context 
)
static

Find the HSP offsets relative to the individual query sequence instead of the concatenated sequence and retrieve relevant portions of the query sequence data.

Parameters
queryQuery sequence block [in]
query_infoQuery information structure, including context offsets array [in]
init_hspInitial HSP, this will be modified to hold the adjusted offsets [in] [out]
query_outquery sequence block with modified sequence pointer and sequence length [out]
contextWhich context this HSP belongs to? [out]

Definition at line 2438 of file blast_gapalign.c.

References ASSERT, context, NULL, BlastUngappedData::q_start, query, s_AdjustInitialHSPOffsets(), s_GetUngappedHSPContext(), s_SetUpLocalBlastSequenceBlk(), and BlastInitHSP::ungapped_data.

Referenced by BLAST_GetGappedScore().

◆ s_AdjustInitialHSPOffsets()

static NCBI_INLINE void s_AdjustInitialHSPOffsets ( BlastInitHSP init_hsp,
Int4  query_start 
)
static

Adjust the HSP offsets in the initial ungapped HSP structure given the query start.

Parameters
init_hspInitial HSP [in|out]
query_startStarting offset of the query sequence in the query info structure [in]

Definition at line 2376 of file blast_gapalign.c.

References ASSERT, NULL, BlastInitHSP::offsets, BlastOffsetPair::q_off, BlastUngappedData::q_start, BlastOffsetPair::qs_offsets, and BlastInitHSP::ungapped_data.

Referenced by BLAST_GetUngappedHSPList(), and s_AdjustHspOffsetsAndGetQueryData().

◆ s_BlastAlignPackedNucl()

static Int4 s_BlastAlignPackedNucl ( Uint1 B,
Uint1 A,
Int4  N,
Int4  M,
Int4 b_offset,
Int4 a_offset,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Boolean  reverse_sequence,
Int4  x_dropoff 
)
static

Aligns two nucleotide sequences, one (A) should be packed in the same way as the BLAST databases, the other (B) should contain one basepair/byte.

Traceback is not done in this function.

Parameters
BThe query sequence [in]
AThe subject sequence [in]
NMaximal extension length in query [in]
MMaximal extension length in subject [in]
b_offsetResulting starting offset in query [out]
a_offsetResulting starting offset in subject [out]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsParameters related to scoring [in]
reverse_sequenceReverse the sequence.
Returns
The best alignment score found.

Definition at line 3026 of file blast_gapalign.c.

References A, BlastGapDP::best, BlastGapDP::best_gap, SBlastScoreMatrix::data, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, i, malloc(), BlastScoreBlk::matrix, MAX, MININT, N, NCBI2NA_UNPACK_BASE, BlastGapAlignStruct::sbp, and sfree.

Referenced by s_BlastDynProgNtGappedAlignment().

◆ s_BlastDynProgNtGappedAlignment()

static Int2 s_BlastDynProgNtGappedAlignment ( BLAST_SequenceBlk query_blk,
BLAST_SequenceBlk subject_blk,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
BlastInitHSP init_hsp 
)
static

Performs dynamic programming style gapped extension, given an initial HSP (offset pair), two sequence blocks and scoring and extension options.

Note: traceback is not done in this function.

Parameters
query_blkThe query sequence [in]
subject_blkThe subject sequence [in]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsParameters related to scoring [in]
init_hspThe initial HSP that needs to be extended [in]

Definition at line 2941 of file blast_gapalign.c.

References COMPRESSION_RATIO, FALSE, BlastGapAlignStruct::gap_x_dropoff, BLAST_SequenceBlk::length, BlastInitHSP::offsets, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, query, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, s_BlastAlignPackedNucl(), BlastOffsetPair::s_off, BlastUngappedData::score, BlastGapAlignStruct::score, BLAST_SequenceBlk::sequence, subject, BlastGapAlignStruct::subject_start, BlastGapAlignStruct::subject_stop, TRUE, and BlastInitHSP::ungapped_data.

Referenced by BLAST_GetGappedScore().

◆ s_BlastGreedyAlignMemAlloc()

static SGreedyAlignMem* s_BlastGreedyAlignMemAlloc ( const BlastScoringParameters score_params,
const BlastExtensionParameters ext_params,
Int4  max_d,
Int4  Xdrop 
)
static

Allocate memory for the greedy gapped alignment algorithm.

Parameters
score_paramsParameters related to scoring [in]
ext_paramsOptions and parameters related to the extension [in]
max_dThe maximum distance to search [in]
XdropThe Xdrop value [in]
Returns
The allocated SGreedyAlignMem structure

Definition at line 171 of file blast_gapalign.c.

References BLAST_Gdb3(), calloc(), SGreedyAlignMem::diag_bounds, ErrPostEx, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastExtensionParameters::gap_x_dropoff, BlastExtensionParameters::gap_x_dropoff_final, i, if(), SGreedyAlignMem::last_seq2_off, SGreedyAlignMem::last_seq2_off_affine, malloc(), MAX, SGreedyAlignMem::max_dist, SGreedyAlignMem::max_score, MBSpaceNew(), NULL, BlastScoringParameters::penalty, BlastScoringParameters::reward, s_BlastGreedyAlignsFree(), SEV_WARNING, sfree, SGreedyAlignMem::space, and SGreedyAlignMem::xdrop.

Referenced by BLAST_GapAlignStructNew(), and BLAST_GreedyGappedAlignment().

◆ s_BlastGreedyAlignsFree()

static SGreedyAlignMem* s_BlastGreedyAlignsFree ( SGreedyAlignMem gamp)
static

◆ s_BlastGreedyGapAlignStructFill()

static Int2 s_BlastGreedyGapAlignStructFill ( BlastGapAlignStruct gap_align,
Int4  q_start,
Int4  s_start,
Int4  q_end,
Int4  s_end,
Int4  q_seed_start,
Int4  s_seed_start,
Int4  score,
GapEditScript esp 
)
static

Fills the BlastGapAlignStruct structure with the results of a greedy gapped extension.

Parameters
gap_alignthe initialized gapped alignment structure [in] [out]
q_startThe starting offset in query [in]
s_startThe starting offset in subject [in]
q_endThe ending offset in query [in]
s_endThe ending offset in subject [in]
q_seed_startThe query offset of the alignment start point [in]
s_seed_startThe subject offset of the alignment start point [in]
scoreThe alignment score [in]
espThe edit script containing the traceback information [in]

Definition at line 2544 of file blast_gapalign.c.

References BlastGapAlignStruct::edit_script, BlastGapAlignStruct::greedy_query_seed_start, BlastGapAlignStruct::greedy_subject_seed_start, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, BlastGapAlignStruct::score, BlastGapAlignStruct::subject_start, and BlastGapAlignStruct::subject_stop.

Referenced by BLAST_GreedyGappedAlignment().

◆ s_BlastOOFTracebackToGapEditScript()

static Int2 s_BlastOOFTracebackToGapEditScript ( GapPrelimEditBlock rev_prelim_tback,
GapPrelimEditBlock fwd_prelim_tback,
Int4  nucl_align_length,
GapEditScript **  edit_script_ptr 
)
static

Converts OOF traceback from a gapped alignment to a GapEditScript.

This function is for out-of-frame gapping.

Parameters
rev_prelim_tbackTraceback operations for left extension [in]
fwd_prelim_tbackTraceback operations for right extension [in]
nucl_align_lengthLength of alignment on the translated nucleotide sequence [in]
edit_script_ptrThe resulting edit block [out]
Returns
Always zero

Definition at line 4117 of file blast_gapalign.c.

References Blast_PrelimEditBlockToGapEditScript(), GapPrelimEditBlock::edit_ops, eGapAlignDel, eGapAlignIns, eGapAlignSub, GapEditScriptDelete(), GapEditScriptNew(), GapPrelimEditBlockAdd(), GapPrelimEditBlockFree(), GapPrelimEditBlockNew(), i, MIN, GapEditScript::num, GapPrelimEditScript::num, GapPrelimEditBlock::num_ops, GapEditScript::op_type, GapPrelimEditScript::op_type, and GapEditScript::size.

Referenced by BLAST_GappedAlignmentWithTraceback().

◆ s_BlastProtGappedAlignment()

static Int2 s_BlastProtGappedAlignment ( EBlastProgramType  program,
BLAST_SequenceBlk query_blk,
BLAST_SequenceBlk subject_blk,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
BlastInitHSP init_hsp,
Boolean  restricted_alignment,
Boolean fence_hit 
)
static

Performs gapped extension for protein sequences, given two sequence blocks, scoring and extension options, and an initial HSP with information from the previously performed ungapped extension.

Parameters
programBLAST program [in]
query_blkThe query sequence block [in]
subject_blkThe subject sequence block [in]
gap_alignThe auxiliary structure for gapped alignment [in]
score_paramsParameters related to scoring [in]
init_hspThe initial HSP information [in]
restricted_alignmentIf true and search is not out-of-frame, use a faster approximate gapped alignment algorithm [in]
fence_hitIf not NULL, pointer to a boolean that is set to TRUE if gapped extension reaches a neighborhood of the subject sequence that is not initialized [in][out]

Definition at line 3964 of file blast_gapalign.c.

References AdjustSubjectRange(), ASSERT, Blast_SemiGappedAlign(), CODON_LENGTH, eBlastTypeBlastx, eBlastTypeTblastn, FALSE, BLAST_SequenceBlk::frame, BlastScoringOptions::is_ooframe, BLAST_SequenceBlk::length, NULL, BlastInitHSP::offsets, BLAST_SequenceBlk::oof_sequence, BlastScoringParameters::options, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, query, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, BlastOffsetPair::s_off, s_OutOfFrameSemiGappedAlignWrap(), s_RestrictedGappedAlign(), BlastGapAlignStruct::score, BLAST_SequenceBlk::sequence, subject, BlastGapAlignStruct::subject_start, BlastGapAlignStruct::subject_stop, and TRUE.

Referenced by BLAST_GetGappedScore().

◆ s_GapGetState()

static GapStateArrayStruct* s_GapGetState ( GapStateArrayStruct **  head,
Int4  length 
)
static

Retrieve the state structure corresponding to a given length.

Parameters
headPointer to the first element of the state structures array [in]
lengthThe length for which the state structure has to be found [in]
Returns
The found or created state structure

Definition at line 71 of file blast_gapalign.c.

References CHUNKSIZE, ErrPostEx, head, last(), GapStateArrayStruct::length, malloc(), MAX, GapStateArrayStruct::next, NULL, SEV_ERROR, sfree, GapStateArrayStruct::state_array, and GapStateArrayStruct::used.

Referenced by ALIGN_EX(), and s_OutOfFrameAlignWithTraceback().

◆ s_GapPurgeState()

static Boolean s_GapPurgeState ( GapStateArrayStruct state_struct)
static

Remove a state from a state structure.

Definition at line 128 of file blast_gapalign.c.

References GapStateArrayStruct::next, TRUE, and GapStateArrayStruct::used.

Referenced by ALIGN_EX(), and s_OutOfFrameAlignWithTraceback().

◆ s_GetUngappedHSPContext()

static NCBI_INLINE Int4 s_GetUngappedHSPContext ( const BlastQueryInfo query_info,
const BlastInitHSP init_hsp 
)
static

Simple wrapper around binary search function for BlastQueryInfo structure to obtain the context in which this initial ungapped HSP is found.

Parameters
query_infoQuery information structure [in]
init_hspInitial HSP [in]

Definition at line 2363 of file blast_gapalign.c.

References BSearchContextInfo(), BlastInitHSP::offsets, BlastOffsetPair::q_off, and BlastOffsetPair::qs_offsets.

Referenced by BLAST_GetUngappedHSPList(), and s_AdjustHspOffsetsAndGetQueryData().

◆ s_OutOfFrameAlignWithTraceback()

static Int4 s_OutOfFrameAlignWithTraceback ( const Uint1 A,
const Uint1 B,
Int4  M,
Int4  N,
Int4 a_offset,
Int4 b_offset,
GapPrelimEditBlock edit_block,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  query_offset,
Boolean  reversed 
)
static

Low level function to perform gapped extension with out-of-frame gapping with traceback.

Parameters
AThe query sequence [in]
BThe subject sequence [in]
MMaximal extension length in query [in]
NMaximal extension length in subject [in]
a_offsetResulting starting offset in query [out]
b_offsetResulting starting offset in subject [out]
edit_blockStructure to hold generated traceback [out]
gap_alignStructure holding various information and allocated memory for the gapped alignment [in]
score_paramsParameters related to scoring [in]
query_offsetThe starting offset in query [in]
reversedHas the sequence been reversed? Used for psi-blast [in]
Returns
The best alignment score found.

Definition at line 1325 of file blast_gapalign.c.

References A, BlastGapDP::best, BlastGapDP::best_gap, CODON_LENGTH, SBlastScoreMatrix::data, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, GapPrelimEditBlockAdd(), i, malloc(), BlastScoreBlk::matrix, MAX, MIN, MININT, N, NULL, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, s_GapGetState(), s_GapPurgeState(), BlastGapAlignStruct::sbp, SCRIPT_AHEAD_ONE_FRAME, SCRIPT_AHEAD_TWO_FRAMES, SCRIPT_EXTEND_GAP_A, SCRIPT_EXTEND_GAP_B, SCRIPT_GAP_IN_A, SCRIPT_GAP_IN_B, SCRIPT_NEXT_IN_FRAME, SCRIPT_NEXT_PLUS_ONE_FRAME, SCRIPT_NEXT_PLUS_TWO_FRAMES, SCRIPT_OOF_OPEN_GAP, SCRIPT_OP_MASK, sfree, BlastScoringParameters::shift_pen, GapStateArrayStruct::state_array, BlastGapAlignStruct::state_struct, and GapStateArrayStruct::used.

Referenced by s_OutOfFrameGappedAlign().

◆ s_OutOfFrameGappedAlign()

static Int4 s_OutOfFrameGappedAlign ( const Uint1 A,
const Uint1 B,
Int4  M,
Int4  N,
Int4 a_offset,
Int4 b_offset,
Boolean  score_only,
GapPrelimEditBlock edit_block,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  query_offset,
Boolean  reversed 
)
static

Low level function to perform gapped extension with out-of-frame gapping with or without traceback.

Parameters
AThe query sequence [in]
BThe subject sequence [in]
MMaximal extension length in query [in]
NMaximal extension length in subject [in]
a_offsetResulting starting offset in query [out]
b_offsetResulting starting offset in subject [out]
score_onlyOnly find the score, without saving traceback [in]
edit_blockStructure to hold generated traceback [out]
gap_alignStructure holding various information and allocated memory for the gapped alignment [in]
score_paramsParameters related to scoring [in]
query_offsetThe starting offset in query [in]
reversedHas the sequence been reversed? Used for psi-blast [in]
Returns
The best alignment score found.

Definition at line 1941 of file blast_gapalign.c.

References A, BlastGapDP::best, BlastGapDP::best_gap, CODON_LENGTH, SBlastScoreMatrix::data, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, i, malloc(), BlastScoreBlk::matrix, MAX, MIN, MININT, N, NULL, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, s_OutOfFrameAlignWithTraceback(), BlastGapAlignStruct::sbp, sfree, and BlastScoringParameters::shift_pen.

Referenced by s_OutOfFrameSemiGappedAlignWrap().

◆ s_OutOfFrameSemiGappedAlignWrap()

static Int4 s_OutOfFrameSemiGappedAlignWrap ( const Uint1 query,
const Uint1 subject,
Int4  q_off,
Int4  s_off,
Int4 private_q_start,
Int4 private_s_start,
Boolean  score_only,
GapPrelimEditBlock edit_block,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  psi_offset,
Boolean  reversed,
Boolean  switch_seq 
)
static

Out-of-frame gapped alignment wrapper function.

Parameters
queryQuery sequence [in]
subjectSubject sequence [in]
q_offOffset in query [in]
s_offOffset in subject [in]
private_q_startExtent of alignment in query [out]
private_s_startExtent of alignment in subject [out]
score_onlyReturn score only, without traceback [in]
edit_blockStructure to hold generated traceback [out]
gap_alignGapped alignment information and preallocated memory [in] [out]
score_paramsScoring parameters [in]
psi_offsetStarting position in PSI-BLAST matrix [in]
reversedDirection of the extension [in]
switch_seqSequences need to be switched for blastx, but not for tblastn [in]

Definition at line 3889 of file blast_gapalign.c.

References query, s_OutOfFrameGappedAlign(), and subject.

Referenced by BLAST_GappedAlignmentWithTraceback(), and s_BlastProtGappedAlignment().

◆ s_RebuildEditScript()

static void s_RebuildEditScript ( GapEditScript esp)
static

Definition at line 2626 of file blast_gapalign.c.

References eGapAlignSub, i, GapEditScript::num, GapEditScript::op_type, and GapEditScript::size.

Referenced by s_ReduceGaps().

◆ s_ReduceGaps()

static void s_ReduceGaps ( GapEditScript esp,
const Uint1 q,
const Uint1 s,
const Uint1 qf,
const Uint1 sf 
)
static

◆ s_RestrictedGappedAlign()

static Int4 s_RestrictedGappedAlign ( const Uint1 A,
const Uint1 B,
Int4  M,
Int4  N,
Int4 a_offset,
Int4 b_offset,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4  query_offset,
Boolean  reverse_sequence 
)
static

Low level function to perform score-only gapped extension in one direction.

Gaps in one sequence or the other are only allowed to start at sequence offsets that are a multiple of RESTRICT_SIZE from the alignment start point. For more details see

Michael Cameron, Hugh E. Williams, Adam Cannane, "Improved
Gapped Alignment in BLAST". IEEE/ACM Transactions on Computational
Biology and Bioinformatics, vol 1 #3 (2004) pp 116-129
Parameters
AThe query sequence [in]
BThe subject sequence [in]
MMaximal extension length in query [in]
NMaximal extension length in subject [in]
a_offsetResulting starting offset in query [out]
b_offsetResulting starting offset in subject [out]
gap_alignStructure holding various information and allocated memory for the gapped alignment [in]
score_paramsParameters related to scoring [in]
query_offsetThe starting offset in query [in]
reverse_sequenceDo reverse the sequence [in]
Returns
The best alignment score found.

Definition at line 983 of file blast_gapalign.c.

References A, BlastGapDP::best, BlastGapDP::best_gap, SBlastScoreMatrix::data, BlastGapAlignStruct::dp_mem, BlastGapAlignStruct::dp_mem_alloc, BlastScoringParameters::gap_extend, BlastScoringParameters::gap_open, BlastGapAlignStruct::gap_x_dropoff, i, malloc(), BlastScoreBlk::matrix, MAX, MININT, N, NULL, BlastGapAlignStruct::positionBased, BlastScoreBlk::psi_matrix, SPsiBlastScoreMatrix::pssm, RESTRICT_SIZE, BlastGapAlignStruct::sbp, and sfree.

Referenced by s_BlastProtGappedAlignment().

◆ s_SetUpLocalBlastSequenceBlk()

static void s_SetUpLocalBlastSequenceBlk ( const BLAST_SequenceBlk concatenated_query,
const BlastQueryInfo query_info,
Int4  context,
BLAST_SequenceBlk single_query,
Int4 query_start 
)
static

Set up a BLAST_SequenceBlk structure for a single query sequence.

Parameters
concatenated_queryQuery sequence block for concatenated query [in]
query_infoQuery information structure for concatenated query [in]
contextContext in which the HSP ocurred [in]
single_queryquery Output sequence block which will contain adjusted sequence pointer and sequence length [out]
query_startStarting offset of the single query sequence in the concatenated query [out]

Definition at line 2396 of file blast_gapalign.c.

References CODON_LENGTH, context, BlastQueryInfo::contexts, BLAST_SequenceBlk::length, NULL, BLAST_SequenceBlk::oof_sequence, BlastContextInfo::query_length, BlastContextInfo::query_offset, and BLAST_SequenceBlk::sequence.

Referenced by s_AdjustHspOffsetsAndGetQueryData().

◆ s_UpdateEditScript()

static void s_UpdateEditScript ( GapEditScript esp,
int  pos,
int  bf,
int  af 
)
static
Modified on Mon Apr 22 04:05:38 2024 by modify_doxy.py rev. 669887