Ungapped extension structures that are common to nucleotide and protein extension routines. More...

#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/blast_parameters.h>
#include <algo/blast/core/lookup_wrap.h>

Include dependency graph for blast_extend.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.

Classes
struct	DiagStruct
	Structure for keeping last hit information for a diagonal. More...

struct	DiagHashCell
	Structure for keeping last hit information for a diagonal in a hash table, when eRight or eRightAndLeft methods are used for initial hit extension. More...

struct	BLAST_DiagTable
	Structure containing parameters needed for initial word extension. More...

struct	BLAST_DiagHash
	Track initial word matches using hashing with chaining. More...

struct	Blast_ExtendWord
	Structure for keeping initial word extension information. More...

struct	BlastUngappedData
	Structure to hold ungapped alignment information. More...

struct	BlastInitHSP
	Structure to hold the initial HSP information. More...

struct	BlastInitHitList
	Structure to hold all initial HSPs for a given subject sequence. More...

Macros
#define	DIAGHASH_NUM_BUCKETS 512
	Number of hash buckets in BLAST_DiagHash. More...

#define	DIAGHASH_CHAIN_LENGTH 256
	Default hash chain length. More...

#define	MIN_INIT_HITLIST_SIZE 100
	Minimal size of an array of initial word hits, allocated up front. More...

Typedefs
typedef struct DiagStruct	DiagStruct
	Structure for keeping last hit information for a diagonal. More...

typedef struct DiagHashCell	DiagHashCell
	Structure for keeping last hit information for a diagonal in a hash table, when eRight or eRightAndLeft methods are used for initial hit extension. More...

typedef struct BLAST_DiagTable	BLAST_DiagTable
	Structure containing parameters needed for initial word extension. More...

typedef struct BLAST_DiagHash	BLAST_DiagHash
	Track initial word matches using hashing with chaining. More...

typedef struct Blast_ExtendWord	Blast_ExtendWord
	Structure for keeping initial word extension information. More...

typedef struct BlastUngappedData	BlastUngappedData
	Structure to hold ungapped alignment information. More...

typedef struct BlastInitHSP	BlastInitHSP
	Structure to hold the initial HSP information. More...

typedef struct BlastInitHitList	BlastInitHitList
	Structure to hold all initial HSPs for a given subject sequence. More...

Functions
Int2	BlastExtendWordNew (Uint4 query_length, const BlastInitialWordParameters word_params, Blast_ExtendWord *ewp_ptr)
	Initializes the word extension structure. More...

Blast_ExtendWord *	BlastExtendWordFree (Blast_ExtendWord *ewp)
	Deallocate memory for the word extension structure. More...

Int2	Blast_ExtendWordExit (Blast_ExtendWord *ewp, Int4 subject_length)
	Update the word extension structure after scanning of each subject sequence. More...

BlastInitHitList *	BLAST_InitHitListNew (void)
	Allocate memory for the BlastInitHitList structure. More...

void	BlastInitHitListMove (BlastInitHitList dst, BlastInitHitList src)
	Move the contents of a BlastInitHitList structure. More...

void	BlastInitHitListReset (BlastInitHitList *init_hitlist)
	Free the ungapped data substructures and reset initial HSP count to 0. More...

BlastInitHitList *	BLAST_InitHitListFree (BlastInitHitList *init_hitlist)
	Free memory for the BlastInitList structure. More...

Boolean	BLAST_SaveInitialHit (BlastInitHitList init_hitlist, Int4 q_off, Int4 s_off, BlastUngappedData ungapped_data)
	Save the initial hit data into the initial hit list structure. More...

void	BlastSaveInitHsp (BlastInitHitList *ungapped_hsps, Int4 q_start, Int4 s_start, Int4 q_off, Int4 s_off, Int4 len, Int4 score)
	Add a new initial (ungapped) HSP to an initial hit list. More...

void	Blast_InitHitListSortByScore (BlastInitHitList *init_hitlist)
	Sort array of initial HSPs by score. More...

Boolean	Blast_InitHitListIsSortedByScore (BlastInitHitList *init_hitlist)
	Check if array of initial HSPs is sorted by score. More...

Detailed Description

Ungapped extension structures that are common to nucleotide and protein extension routines.

Also includes associative data structures used to track progress of extensions on each diagonal. Protein searches only use DiagTable; nucleotide searches can use either DiagTable or DiagHash.

Definition in file blast_extend.h.

Macro Definition Documentation

◆ DIAGHASH_CHAIN_LENGTH

#define DIAGHASH_CHAIN_LENGTH 256

Default hash chain length.

Definition at line 54 of file blast_extend.h.

◆ DIAGHASH_NUM_BUCKETS

#define DIAGHASH_NUM_BUCKETS 512

Number of hash buckets in BLAST_DiagHash.

Definition at line 51 of file blast_extend.h.

◆ MIN_INIT_HITLIST_SIZE

#define MIN_INIT_HITLIST_SIZE 100

Minimal size of an array of initial word hits, allocated up front.

Definition at line 139 of file blast_extend.h.

Typedef Documentation

◆ BLAST_DiagHash

typedef struct BLAST_DiagHash BLAST_DiagHash

Track initial word matches using hashing with chaining.

Can be used in blastn.

◆ BLAST_DiagTable

typedef struct BLAST_DiagTable BLAST_DiagTable

Structure containing parameters needed for initial word extension.

Only one copy of this structure is needed, regardless of how many contexts there are.

◆ Blast_ExtendWord

typedef struct Blast_ExtendWord Blast_ExtendWord

Structure for keeping initial word extension information.

◆ BlastInitHitList

typedef struct BlastInitHitList BlastInitHitList

Structure to hold all initial HSPs for a given subject sequence.

◆ BlastInitHSP

typedef struct BlastInitHSP BlastInitHSP

Structure to hold the initial HSP information.

◆ BlastUngappedData

typedef struct BlastUngappedData BlastUngappedData

Structure to hold ungapped alignment information.

◆ DiagHashCell

typedef struct DiagHashCell DiagHashCell

Structure for keeping last hit information for a diagonal in a hash table, when eRight or eRightAndLeft methods are used for initial hit extension.

◆ DiagStruct

typedef struct DiagStruct DiagStruct

Structure for keeping last hit information for a diagonal.

Function Documentation

◆ Blast_ExtendWordExit()

Int2 Blast_ExtendWordExit	(	Blast_ExtendWord *	ewp,
		Int4	subject_length
	)

Update the word extension structure after scanning of each subject sequence.

Parameters

ewp	The structure holding word extension information [in] [out]
subject_length	The length of the subject sequence that has just been processed [in]

Definition at line 162 of file blast_extend.c.

References BLAST_DiagHash::backbone, Blast_ExtendWord::diag_table, Blast_ExtendWord::hash_table, INT4_MAX, BLAST_DiagHash::num_buckets, BLAST_DiagHash::occupancy, BLAST_DiagTable::offset, BLAST_DiagHash::offset, s_BlastDiagClear(), BLAST_DiagTable::window, and BLAST_DiagHash::window.

Referenced by BlastNaWordFinder(), BOOST_AUTO_TEST_CASE(), s_BlastAaWordFinder_OneHit(), s_BlastAaWordFinder_TwoHit(), s_BlastRPSWordFinder_OneHit(), and s_BlastRPSWordFinder_TwoHit().

◆ BLAST_InitHitListFree()

BlastInitHitList* BLAST_InitHitListFree ( BlastInitHitList * init_hitlist )

Free memory for the BlastInitList structure.

Definition at line 261 of file blast_extend.c.

References NULL, s_BlastInitHitListClean(), and sfree.

Referenced by BOOST_AUTO_TEST_CASE(), s_BlastCoreAuxStructFree(), TestFixture::SkipMaskedRangesCore(), CBlastExtendTestFixture::~CBlastExtendTestFixture(), CDbIndex::CSearchResults::~CSearchResults(), and NuclWordFinderTextFixture::~NuclWordFinderTextFixture().

◆ Blast_InitHitListIsSortedByScore()

Boolean Blast_InitHitListIsSortedByScore ( BlastInitHitList * init_hitlist )

Check if array of initial HSPs is sorted by score.

Parameters

init_hitlist Initial hit list structure to check. [in]

Returns: TRUE if sorted, FALSE otherwise.

Definition at line 312 of file blast_extend.c.

References FALSE, BlastInitHitList::init_hsp_array, score_compare_match(), BlastInitHitList::total, and TRUE.

Referenced by BLAST_GetGappedScore().

◆ BLAST_InitHitListNew()

BlastInitHitList* BLAST_InitHitListNew ( void )

Allocate memory for the BlastInitHitList structure.

Definition at line 216 of file blast_extend.c.

References BlastInitHitList::allocated, calloc(), BlastInitHitList::init_hsp_array, malloc(), and MIN_INIT_HITLIST_SIZE.

Referenced by BOOST_AUTO_TEST_CASE(), s_BlastSetUpAuxStructures(), CTrackedSeeds_Base< NHITS >::SaveSeed(), NuclWordFinderTextFixture::setupAll(), CBlastExtendTestFixture::setupGreedyHitList(), CBlastExtendTestFixture::setupHitList(), and TestFixture::SkipMaskedRangesCore().

◆ Blast_InitHitListSortByScore()

void Blast_InitHitListSortByScore ( BlastInitHitList * init_hitlist )

Sort array of initial HSPs by score.

Parameters

init_hitlist Initial hit list structure to check. [in]

Definition at line 306 of file blast_extend.c.

References BlastInitHitList::init_hsp_array, score_compare_match(), and BlastInitHitList::total.

Referenced by BlastAaWordFinder(), BlastNaWordFinder(), BlastRPSWordFinder(), BOOST_AUTO_TEST_CASE(), MB_IndexedWordFinder(), and s_TranslateHSPsToDNAPCoord().

◆ BLAST_SaveInitialHit()

Boolean BLAST_SaveInitialHit	(	BlastInitHitList *	init_hitlist,
		Int4	q_off,
		Int4	s_off,
		BlastUngappedData *	ungapped_data
	)

Save the initial hit data into the initial hit list structure.

Parameters

init_hitlist	the structure holding all the initial hits information [in] [out]
q_off	The query sequence offset [in]
s_off	The subject sequence offset [in]
ungapped_data	The information about the ungapped extension of this hit [in]

Definition at line 325 of file blast_extend.c.

References BlastInitHitList::allocated, BlastInitHitList::do_not_reallocate, FALSE, BlastInitHitList::init_hsp_array, BlastInitHSP::offsets, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, BlastOffsetPair::s_off, BlastInitHitList::total, TRUE, and BlastInitHSP::ungapped_data.

Referenced by BlastSaveInitHsp(), BOOST_AUTO_TEST_CASE(), s_BlastnDiagHashExtendInitialHit(), s_BlastnDiagTableExtendInitialHit(), s_PHISaveInitialHit(), CTrackedSeeds_Base< NHITS >::SaveSeed(), CBlastExtendTestFixture::setupGreedyHitList(), and CBlastExtendTestFixture::setupHitList().

◆ BlastExtendWordFree()

Blast_ExtendWord* BlastExtendWordFree ( Blast_ExtendWord * ewp )

Deallocate memory for the word extension structure.

Definition at line 203 of file blast_extend.c.

References Blast_ExtendWord::diag_table, Blast_ExtendWord::hash_table, NULL, s_BlastDiagHashFree(), s_BlastDiagTableFree(), and sfree.

Referenced by BOOST_AUTO_TEST_CASE(), s_BlastCoreAuxStructFree(), s_RPSPreliminarySearchEngine(), TestFixture::SkipMaskedRangesCore(), and NuclWordFinderTextFixture::~NuclWordFinderTextFixture().

◆ BlastExtendWordNew()

Int2 BlastExtendWordNew	(	Uint4	query_length,
		const BlastInitialWordParameters *	word_params,
		Blast_ExtendWord **	ewp_ptr
	)

Initializes the word extension structure.

Parameters

query_length	Length of the query sequence [in]
word_params	Parameters for initial word extension [in]
ewp_ptr	Pointer to the word extension structure [out]

Definition at line 110 of file blast_extend.c.

References BLAST_DiagHash::backbone, calloc(), BLAST_DiagHash::capacity, BLAST_DiagHash::chain, BlastInitialWordParameters::container_type, BLAST_DiagTable::diag_array_length, Blast_ExtendWord::diag_table, DIAGHASH_CHAIN_LENGTH, DIAGHASH_NUM_BUCKETS, eDiagHash, Blast_ExtendWord::hash_table, BLAST_DiagTable::hit_len_array, BLAST_DiagTable::hit_level_array, BLAST_DiagHash::num_buckets, BLAST_DiagHash::occupancy, BLAST_DiagHash::offset, BlastInitialWordParameters::options, s_BlastDiagTableNew(), sfree, BLAST_DiagHash::window, and BlastInitialWordOptions::window_size.

Referenced by BOOST_AUTO_TEST_CASE(), s_BlastSetUpAuxStructures(), s_RPSPreliminarySearchEngine(), NuclWordFinderTextFixture::setupExtendWord(), and TestFixture::SkipMaskedRangesCore().

◆ BlastInitHitListMove()

void BlastInitHitListMove	(	BlastInitHitList *	dst,
		BlastInitHitList *	src
	)

Move the contents of a BlastInitHitList structure.

Parameters

dst	Destination hitlist [in][out]
src	Source hitlist (gets emptied of hits) [in][out]

Definition at line 248 of file blast_extend.c.

References BlastInitHitList::allocated, ASSERT, BlastInitHitList::do_not_reallocate, BlastInitHitList::init_hsp_array, memmove, s_BlastInitHitListClean(), and BlastInitHitList::total.

Referenced by CIndexedDb_Old::GetResults(), and CIndexedDb_New::GetResults().

◆ BlastInitHitListReset()

void BlastInitHitListReset ( BlastInitHitList * init_hitlist )

Free the ungapped data substructures and reset initial HSP count to 0.

Definition at line 229 of file blast_extend.c.

References BlastInitHitList::init_hsp_array, sfree, BlastInitHitList::total, and BlastInitHSP::ungapped_data.

Referenced by CIndexedDb_Old::GetResults(), CIndexedDb_New::GetResults(), s_BlastInitHitListClean(), and s_BlastSearchEngineOneContext().

◆ BlastSaveInitHsp()

void BlastSaveInitHsp	(	BlastInitHitList *	ungapped_hsps,
		Int4	q_start,
		Int4	s_start,
		Int4	q_off,
		Int4	s_off,
		Int4	len,
		Int4	score
	)

Add a new initial (ungapped) HSP to an initial hit list.

Parameters

ungapped_hsps	Hit list where to save a new HSP [in] [out]
q_start	Starting offset in query [in]
s_start	Starting offset in subject [in]
q_off	Offset in query, where lookup table hit was found. [in]
s_off	Offset in subject, where lookup table hit was found. [in]
len	Length of the ungapped match [in]
score	Score of the ungapped match [in]

Definition at line 360 of file blast_extend.c.

References BLAST_SaveInitialHit(), len, BlastUngappedData::length, malloc(), NULL, BlastUngappedData::q_start, BlastUngappedData::s_start, and BlastUngappedData::score.

Referenced by s_BlastAaWordFinder_OneHit(), s_BlastAaWordFinder_TwoHit(), s_BlastRPSWordFinder_OneHit(), and s_BlastRPSWordFinder_TwoHit().

Classes

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ DIAGHASH_CHAIN_LENGTH

◆ DIAGHASH_NUM_BUCKETS

◆ MIN_INIT_HITLIST_SIZE

Typedef Documentation

◆ BLAST_DiagHash

◆ BLAST_DiagTable

◆ Blast_ExtendWord

◆ BlastInitHitList

◆ BlastInitHSP

◆ BlastUngappedData

◆ DiagHashCell

◆ DiagStruct

Function Documentation

◆ Blast_ExtendWordExit()

◆ BLAST_InitHitListFree()

◆ Blast_InitHitListIsSortedByScore()

◆ BLAST_InitHitListNew()

◆ Blast_InitHitListSortByScore()

◆ BLAST_SaveInitialHit()

◆ BlastExtendWordFree()

◆ BlastExtendWordNew()

◆ BlastInitHitListMove()

◆ BlastInitHitListReset()

◆ BlastSaveInitHsp()