blast_nalookup.h File Reference

Routines for creating nucleotide BLAST lookup tables. More...

#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/blast_def.h>
#include <algo/blast/core/blast_lookup.h>
#include <algo/blast/core/blast_options.h>
#include <algo/blast/core/blast_seqsrc.h>

Include dependency graph for blast_nalookup.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	BlastSmallNaLookupTable
	Lookup table structure for blastn searches with small queries. More...
struct	NaLookupBackboneCell
	structure defining one cell of the compacted lookup table More...
struct	BlastNaLookupTable
	The basic lookup table structure for blastn searches. More...
struct	BlastMBLookupTable
	The lookup table structure used for Mega BLAST. More...
struct	NaHashLookupBackboneCell
	Structure defining one cell of the compacted lookup table. More...
struct	BlastNaHashLookupTable

Macros
#define	NA_HITS_PER_CELL   3
	maximum number of hits in one lookup table cell More...
#define	NA_WORDS_PER_HASH   3
#define	NA_OFFSETS_PER_HASH   9

Typedefs
typedef struct BlastSmallNaLookupTable	BlastSmallNaLookupTable
	Lookup table structure for blastn searches with small queries. More...
typedef struct NaLookupBackboneCell	NaLookupBackboneCell
	structure defining one cell of the compacted lookup table More...
typedef struct BlastNaLookupTable	BlastNaLookupTable
	The basic lookup table structure for blastn searches. More...
typedef struct BlastMBLookupTable	BlastMBLookupTable
	The lookup table structure used for Mega BLAST. More...
typedef struct NaHashLookupBackboneCell	NaHashLookupBackboneCell
	Structure defining one cell of the compacted lookup table. More...
typedef struct BlastNaHashLookupTable	BlastNaHashLookupTable

Enumerations
enum	EDiscWordType { eMBWordCoding = 0 , eMBWordOptimal = 1 , eMBWordTwoTemplates = 2 }
	General types of discontiguous word templates. More...
enum	EDiscTemplateType {   eDiscTemplateContiguous = 0 , eDiscTemplate_11_16_Coding = 1 , eDiscTemplate_11_16_Optimal = 2 , eDiscTemplate_12_16_Coding = 3 ,   eDiscTemplate_12_16_Optimal = 4 , eDiscTemplate_11_18_Coding = 5 , eDiscTemplate_11_18_Optimal = 6 , eDiscTemplate_12_18_Coding = 7 ,   eDiscTemplate_12_18_Optimal = 8 , eDiscTemplate_11_21_Coding = 9 , eDiscTemplate_11_21_Optimal = 10 , eDiscTemplate_12_21_Coding = 11 ,   eDiscTemplate_12_21_Optimal = 12 }
	Enumeration of all discontiguous word templates; the enumerated values encode the weight, template length and type information. More...

Functions
ELookupTableType	BlastChooseNaLookupTable (const LookupTableOptions *lookup_options, Int4 approx_table_entries, Int4 query_length, Int4 *lut_width)
	choose the type of nucleotide lookup table to be used for a blast search More...
Int4	BlastSmallNaLookupTableNew (BLAST_SequenceBlk *query, BlastSeqLoc *locations, BlastSmallNaLookupTable **lut, const LookupTableOptions *opt, const QuerySetUpOptions *query_options, Int4 lut_width)
	Create a new small nucleotide lookup table. More...
BlastSmallNaLookupTable *	BlastSmallNaLookupTableDestruct (BlastSmallNaLookupTable *lookup)
	Free a small nucleotide lookup table. More...
Int4	BlastNaLookupTableNew (BLAST_SequenceBlk *query, BlastSeqLoc *locations, BlastNaLookupTable **lut, const LookupTableOptions *opt, const QuerySetUpOptions *query_options, Int4 lut_width)
	Create a new nucleotide lookup table. More...
BlastNaLookupTable *	BlastNaLookupTableDestruct (BlastNaLookupTable *lookup)
	Free a nucleotide lookup table. More...
Int2	BlastMBLookupTableNew (BLAST_SequenceBlk *query, BlastSeqLoc *location, BlastMBLookupTable **mb_lt_ptr, const LookupTableOptions *lookup_options, const QuerySetUpOptions *query_options, Int4 approx_table_entries, Int4 lut_width, BlastSeqSrc *seqsrc)
	Create the lookup table for Mega BLAST. More...
BlastMBLookupTable *	BlastMBLookupTableDestruct (BlastMBLookupTable *mb_lt)
	Deallocate memory used by the Mega BLAST lookup table. More...
static NCBI_INLINE Int4	DiscontigIndex_11_16_Coding (Uint8 accum)
	Forms a lookup table index for the 11-of-16 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_11_16_Optimal (Uint8 accum)
	Forms a lookup table index for the 11-of-16 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_11_18_Coding (Uint8 accum)
	Forms a lookup table index for the 11-of-18 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_11_18_Optimal (Uint8 accum)
	Forms a lookup table index for the 11-of-18 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_11_21_Coding (Uint8 accum)
	Forms a lookup table index for the 11-of-21 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_11_21_Optimal (Uint8 accum)
	Forms a lookup table index for the 11-of-21 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_16_Coding (Uint8 accum)
	Forms a lookup table index for the 12-of-16 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_16_Optimal (Uint8 accum)
	Forms a lookup table index for the 12-of-16 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_18_Coding (Uint8 accum)
	Forms a lookup table index for the 12-of-18 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_18_Optimal (Uint8 accum)
	Forms a lookup table index for the 12-of-18 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_21_Coding (Uint8 accum)
	Forms a lookup table index for the 12-of-21 coding template in discontiguous megablast. More...
static NCBI_INLINE Int4	DiscontigIndex_12_21_Optimal (Uint8 accum)
	Forms a lookup table index for the 12-of-21 optimal template in discontiguous megablast. More...
static NCBI_INLINE Int4	ComputeDiscontiguousIndex (Uint8 accum, EDiscTemplateType template_type)
	Given an accumulator containing packed bases, compute the discontiguous word index specified by template_type. More...
Int8	FindSparseIndex (Int8 index, PV_ARRAY_TYPE *pv_array, Int4 pv_array_bts, Int4 *pv_counts, Int4 words_per_bit)
	Find an index into a sparse array using pv_array as a bit field. More...
Int2	FindSparseIndices (Int8 *in_array, Int8 *out_array, Int4 length, PV_ARRAY_TYPE *pv_array, Int4 pv_array_bts, Int4 *counts, Int4 elems_per_bit)
	Find an index into a sparse array using pv_array as a bit field, for a batch of indices. More...
Int4	BlastNaHashLookupTableNew (BLAST_SequenceBlk *query, BlastSeqLoc *locations, BlastNaHashLookupTable **lut, const LookupTableOptions *opt, const QuerySetUpOptions *query_options, BlastSeqSrc *seqsrc, Uint4 num_threads)
BlastNaHashLookupTable *	BlastNaHashLookupTableDestruct (BlastNaHashLookupTable *lookup)
	Free a nucleotide lookup table. More...

Detailed Description

Routines for creating nucleotide BLAST lookup tables.

Definition in file blast_nalookup.h.

Macro Definition Documentation

NA_HITS_PER_CELL

#define NA_HITS_PER_CELL   3

maximum number of hits in one lookup table cell

Definition at line 110 of file blast_nalookup.h.

NA_OFFSETS_PER_HASH

#define NA_OFFSETS_PER_HASH   9

Definition at line 669 of file blast_nalookup.h.

NA_WORDS_PER_HASH

#define NA_WORDS_PER_HASH   3

Definition at line 668 of file blast_nalookup.h.

Typedef Documentation

BlastMBLookupTable

typedef struct BlastMBLookupTable BlastMBLookupTable

The lookup table structure used for Mega BLAST.

BlastNaHashLookupTable

typedef struct BlastNaHashLookupTable BlastNaHashLookupTable

BlastNaLookupTable

typedef struct BlastNaLookupTable BlastNaLookupTable

The basic lookup table structure for blastn searches.

BlastSmallNaLookupTable

typedef struct BlastSmallNaLookupTable BlastSmallNaLookupTable

Lookup table structure for blastn searches with small queries.

NaHashLookupBackboneCell

typedef struct NaHashLookupBackboneCell NaHashLookupBackboneCell

Structure defining one cell of the compacted lookup table.

NaLookupBackboneCell

typedef struct NaLookupBackboneCell NaLookupBackboneCell

structure defining one cell of the compacted lookup table

Enumeration Type Documentation

EDiscTemplateType

enum EDiscTemplateType

Enumeration of all discontiguous word templates; the enumerated values encode the weight, template length and type information.

 Optimal word templates:
Number of 1's in a template is word size (weight); 
total number of 1's and 0's - template length.
  1,110,110,110,110,111      - 12 of 16
  1,110,010,110,110,111      - 11 of 16 
111,010,110,010,110,111      - 12 of 18
111,010,010,110,010,111      - 11 of 18
111,010,010,110,010,010,111  - 12 of 21
111,010,010,100,010,010,111  - 11 of 21
 Coding word templates:
   111,110,110,110,110,1     - 12 of 16
   110,110,110,110,110,1     - 11 of 16
10,110,110,110,110,110,1     - 12 of 18
10,110,110,010,110,110,1     - 11 of 18
10,010,110,110,110,010,110,1 - 12 of 21
10,010,110,010,110,010,110,1 - 11 of 21

Sequence data processed by these templates is assumed to be arranged from left to right

Index values are calculated by masking the respective pieces of sequence so only bits corresponding to a contiguous string of 1's in a template are left, then shifting the masked value to a correct position in the final 22- or 24-bit lookup table index, which is the sum of such shifts.

Enumerator
eDiscTemplateContiguous
eDiscTemplate_11_16_Coding
eDiscTemplate_11_16_Optimal
eDiscTemplate_12_16_Coding
eDiscTemplate_12_16_Optimal
eDiscTemplate_11_18_Coding
eDiscTemplate_11_18_Optimal
eDiscTemplate_12_18_Coding
eDiscTemplate_12_18_Optimal
eDiscTemplate_11_21_Coding
eDiscTemplate_11_21_Optimal
eDiscTemplate_12_21_Coding
eDiscTemplate_12_21_Optimal

Definition at line 221 of file blast_nalookup.h.

EDiscWordType

enum EDiscWordType

General types of discontiguous word templates.

Enumerator
eMBWordCoding
eMBWordOptimal
eMBWordTwoTemplates

Definition at line 185 of file blast_nalookup.h.

Function Documentation

BlastChooseNaLookupTable()

ELookupTableType BlastChooseNaLookupTable	(	const LookupTableOptions *	lookup_options,
		Int4	approx_table_entries,
		Int4	query_length,
		Int4 *	lut_width
	)

choose the type of nucleotide lookup table to be used for a blast search

Parameters

lookup_options	Options for lookup table creation [in]
approx_table_entries	An upper bound on the number of words that must be added to the lookup table [in]
lut_width	The number of nucleotides in one lookup table word [out]
query_length	Number of letters in the query [in]

Returns

the lookup table type chosen

Definition at line 46 of file blast_nalookup.c.

References ASSERT, Blast_ProgramIsMapping(), LookupTableOptions::db_filter, eMBLookupTable, eNaHashLookupTable, eNaLookupTable, eSmallNaLookupTable, LookupTableOptions::mb_template_length, LookupTableOptions::program_number, and LookupTableOptions::word_size.

Referenced by LookupTableWrapInit_MT().

BlastMBLookupTableDestruct()

BlastMBLookupTable* BlastMBLookupTableDestruct

(

BlastMBLookupTable *

mb_lt

)

Deallocate memory used by the Mega BLAST lookup table.

Definition at line 1359 of file blast_nalookup.c.

References BlastSeqLocFree(), BlastMBLookupTable::hashtable, BlastMBLookupTable::hashtable2, BlastMBLookupTable::masked_locations, BlastMBLookupTable::next_pos, BlastMBLookupTable::next_pos2, NULL, BlastMBLookupTable::pv_array, and sfree.

Referenced by BlastMBLookupTableNew(), and LookupTableWrapFree().

BlastMBLookupTableNew()

Int2 BlastMBLookupTableNew	(	BLAST_SequenceBlk *	query,
		BlastSeqLoc *	location,
		BlastMBLookupTable **	mb_lt_ptr,
		const LookupTableOptions *	lookup_options,
		const QuerySetUpOptions *	query_options,
		Int4	approx_table_entries,
		Int4	lut_width,
		BlastSeqSrc *	seqsrc
	)

Create the lookup table for Mega BLAST.

Parameters

query	The query sequence block (if concatenated sequence, the individual strands/sequences must be separated by a 0x0f byte)[in]
location	The locations to be included in the lookup table, e.g. [0,length-1] for full sequence. NULL means no sequence. [in]
mb_lt_ptr	Pointer to the lookup table to be created [out]
lookup_options	Options for lookup table creation [in]
query_options	query options used to get filtering options [in]
approx_table_entries	An upper bound on the number of words that must be added to the lookup table [in]
lut_width	The number of nucleotides in one lookup table word [in]
seqsrc	Database sequences [in]

Definition at line 1215 of file blast_nalookup.c.

References ASSERT, BITS_PER_NUC, BlastMBLookupTableDestruct(), calloc(), LookupTableOptions::db_filter, free(), BlastMBLookupTable::hashsize, BlastMBLookupTable::hashtable, ilog2(), location, BlastMBLookupTable::longest_chain, BlastMBLookupTable::lut_word_length, BlastMBLookupTable::masked_locations, LookupTableOptions::max_db_word_count, LookupTableOptions::mb_template_length, NULL, BlastMBLookupTable::num_unique_pos_added, BlastMBLookupTable::num_words_added, BlastMBLookupTable::pv_array, PV_ARRAY_BTS, BlastMBLookupTable::pv_array_bts, PV_ARRAY_BYTES, query, s_FillContigMBTable(), s_FillDiscMBTable(), s_FillPV(), s_HasMaskAtHashEnabled(), s_ScanSubjectForWordCounts(), s_SeqLocListInvert(), BlastMBLookupTable::scan_step, BlastMBLookupTable::stride, LookupTableOptions::stride, BlastMBLookupTable::word_length, and LookupTableOptions::word_size.

Referenced by LookupTableWrapInit_MT().

BlastNaHashLookupTableDestruct()

BlastNaHashLookupTable* BlastNaHashLookupTableDestruct

(

BlastNaHashLookupTable *

lookup

)

Free a nucleotide lookup table.

Parameters

lookup

The lookup table structure to be freed

Returns

NULL

Definition at line 2196 of file blast_nalookup.c.

References BlastSeqLocFree(), lookup(), NULL, and sfree.

Referenced by BOOST_AUTO_TEST_CASE(), and LookupTableWrapFree().

BlastNaHashLookupTableNew()

Int4 BlastNaHashLookupTableNew	(	BLAST_SequenceBlk *	query,
		BlastSeqLoc *	locations,
		BlastNaHashLookupTable **	lut,
		const LookupTableOptions *	opt,
		const QuerySetUpOptions *	query_options,
		BlastSeqSrc *	seqsrc,
		Uint4	num_threads
	)

Definition at line 2210 of file blast_nalookup.c.

References ASSERT, BITS_PER_NUC, BLASTERR_MEMORY, BlastHashLookupIndexQueryExactMatches(), calloc(), LookupTableOptions::db_filter, FNV_hash(), i, lookup(), LookupTableOptions::max_db_word_count, NULL, offsets, PV_ARRAY_BTS, PV_ARRAY_TYPE, query, s_BlastNaHashLookupFinalize(), s_HasMaskAtHashEnabled(), s_NaHashLookupFillPV(), s_NaHashLookupRemovePolyAWords(), s_NaHashLookupScanSubjectForWordCounts(), s_Popcount(), s_SeqLocListInvert(), sfree, and LookupTableOptions::word_size.

Referenced by BOOST_AUTO_TEST_CASE(), and LookupTableWrapInit_MT().

BlastNaLookupTableDestruct()

BlastNaLookupTable* BlastNaLookupTableDestruct

(

BlastNaLookupTable *

lookup

)

Free a nucleotide lookup table.

Parameters

lookup

The lookup table structure to be freed

Returns

NULL

Definition at line 586 of file blast_nalookup.c.

References BlastSeqLocFree(), lookup(), NULL, and sfree.

Referenced by LookupTableWrapFree(), and SubjectIndexFree().

BlastNaLookupTableNew()

Int4 BlastNaLookupTableNew	(	BLAST_SequenceBlk *	query,
		BlastSeqLoc *	locations,
		BlastNaLookupTable **	lut,
		const LookupTableOptions *	opt,
		const QuerySetUpOptions *	query_options,
		Int4	lut_width
	)

Create a new nucleotide lookup table.

Parameters

query	The query sequence block (if concatenated sequence, the individual strands/sequences must be separated by a 0x0f byte)[in]
locations	The locations to be included in the lookup table, e.g. [0,length-1] for full sequence. NULL means no sequence. [in]
lut	Pointer to the lookup table to be created [out]
opt	Options for lookup table creation [in]
query_options	query options used to get filtering options [in]
lut_width	The number of nucleotides in one lookup table word [in]

Returns

0 if successful, nonzero on failure

Definition at line 548 of file blast_nalookup.c.

References ASSERT, BITS_PER_NUC, BlastLookupIndexQueryExactMatches(), calloc(), lookup(), NULL, query, s_BlastNaLookupFinalize(), s_HasMaskAtHashEnabled(), s_SeqLocListInvert(), sfree, and LookupTableOptions::word_size.

Referenced by LookupTableWrapInit_MT(), and SubjectIndexNew().

BlastSmallNaLookupTableDestruct()

BlastSmallNaLookupTable* BlastSmallNaLookupTableDestruct

(

BlastSmallNaLookupTable *

lookup

)

Free a small nucleotide lookup table.

Parameters

lookup

The lookup table structure to be freed

Returns

NULL

Definition at line 423 of file blast_nalookup.c.

References BlastSeqLocFree(), lookup(), NULL, and sfree.

Referenced by BlastSmallNaLookupTableNew(), and LookupTableWrapFree().

BlastSmallNaLookupTableNew()

Int4 BlastSmallNaLookupTableNew	(	BLAST_SequenceBlk *	query,
		BlastSeqLoc *	locations,
		BlastSmallNaLookupTable **	lut,
		const LookupTableOptions *	opt,
		const QuerySetUpOptions *	query_options,
		Int4	lut_width
	)

Create a new small nucleotide lookup table.

Parameters

query	The query sequence block (if concatenated sequence, the individual strands/sequences must be separated by a 0x0f byte)[in]
locations	The locations to be included in the lookup table, e.g. [0,length-1] for full sequence. NULL means no sequence. [in]
lut	Pointer to the lookup table to be created [out]
opt	Options for lookup table creation [in]
query_options	query options used to get filtering options [in]
lut_width	The number of nucleotides in one lookup table word [in]

Returns

0 if successful, nonzero on failure

Definition at line 378 of file blast_nalookup.c.

References ASSERT, BITS_PER_NUC, BlastLookupIndexQueryExactMatches(), BlastSmallNaLookupTableDestruct(), calloc(), lookup(), NULL, query, s_BlastSmallNaLookupFinalize(), s_SeqLocListInvert(), sfree, and LookupTableOptions::word_size.

Referenced by LookupTableWrapInit_MT().

ComputeDiscontiguousIndex()

static NCBI_INLINE Int4 ComputeDiscontiguousIndex ( Uint8  accum, EDiscTemplateType  template_type  )

static

Given an accumulator containing packed bases, compute the discontiguous word index specified by template_type.

Only the low-order (2 * template_length) bits of the accumulator are used; the base most recently added to the accumulator is in the two lowest bits.

Parameters

accum	The accumulator [in]
template_type	What type of discontiguous word template to use [in]

Returns

The lookup table index of the discontiguous word

Definition at line 540 of file blast_nalookup.h.

References DiscontigIndex_11_16_Coding(), DiscontigIndex_11_16_Optimal(), DiscontigIndex_11_18_Coding(), DiscontigIndex_11_18_Optimal(), DiscontigIndex_11_21_Coding(), DiscontigIndex_11_21_Optimal(), DiscontigIndex_12_16_Coding(), DiscontigIndex_12_16_Optimal(), DiscontigIndex_12_18_Coding(), DiscontigIndex_12_18_Optimal(), DiscontigIndex_12_21_Coding(), DiscontigIndex_12_21_Optimal(), eDiscTemplate_11_16_Coding, eDiscTemplate_11_16_Optimal, eDiscTemplate_11_18_Coding, eDiscTemplate_11_18_Optimal, eDiscTemplate_11_21_Coding, eDiscTemplate_11_21_Optimal, eDiscTemplate_12_16_Coding, eDiscTemplate_12_16_Optimal, eDiscTemplate_12_18_Coding, eDiscTemplate_12_18_Optimal, eDiscTemplate_12_21_Coding, and eDiscTemplate_12_21_Optimal.

Referenced by s_FillDiscMBTable(), s_MB_DiscWordScanSubject_1(), and s_MB_DiscWordScanSubject_TwoTemplates_1().

DiscontigIndex_11_16_Coding()

static NCBI_INLINE Int4 DiscontigIndex_11_16_Coding ( Uint8  accum )

static

Forms a lookup table index for the 11-of-16 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 22-bit lookup table index

Definition at line 307 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_11_16_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_11_16_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 11-of-16 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 22-bit lookup table index

Definition at line 325 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_11_18_Coding()

static NCBI_INLINE Int4 DiscontigIndex_11_18_Coding ( Uint8  accum )

static

Forms a lookup table index for the 11-of-18 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 22-bit lookup table index

Definition at line 342 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_11_18_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_11_18_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 11-of-18 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 22-bit lookup table index

Definition at line 362 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_11_21_Coding()

static NCBI_INLINE Int4 DiscontigIndex_11_21_Coding ( Uint8  accum )

static

Forms a lookup table index for the 11-of-21 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 22-bit lookup table index

Definition at line 382 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_11_21_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_11_21_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 11-of-21 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 403 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_16_Coding()

static NCBI_INLINE Int4 DiscontigIndex_12_16_Coding ( Uint8  accum )

static

Forms a lookup table index for the 12-of-16 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 423 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_16_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_12_16_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 12-of-16 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 440 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_18_Coding()

static NCBI_INLINE Int4 DiscontigIndex_12_18_Coding ( Uint8  accum )

static

Forms a lookup table index for the 12-of-18 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 457 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_18_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_12_18_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 12-of-18 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 477 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_21_Coding()

static NCBI_INLINE Int4 DiscontigIndex_12_21_Coding ( Uint8  accum )

static

Forms a lookup table index for the 12-of-21 coding template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 497 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

DiscontigIndex_12_21_Optimal()

static NCBI_INLINE Int4 DiscontigIndex_12_21_Optimal ( Uint8  accum )

static

Forms a lookup table index for the 12-of-21 optimal template in discontiguous megablast.

Parameters

accum

accumulator containing the 2-bit bases that will be used to create the index. Bases most recently added to the accumulator are in the low-order bits

Returns

The 24-bit lookup table index

Definition at line 518 of file blast_nalookup.h.

Referenced by ComputeDiscontiguousIndex().

FindSparseIndex()

Int8 FindSparseIndex	(	Int8	index,
		PV_ARRAY_TYPE *	pv_array,
		Int4	pv_array_bts,
		Int4 *	pv_counts,
		Int4	words_per_bit
	)

Find an index into a sparse array using pv_array as a bit field.

Parameters

index	Index to translate [in]
pv_array	Bit field (lookup table pv_array) [in]
pv_array_bts	Log2 of pv_array size [in]
pv_counts	Array of set bit counts, where pv_counts[i] is the number of bits set in pv_array[0..i-1] [in]
words_per_bit	Number of words represented by one bit in the pv_array [in]

Returns

Index into the sparse array

FindSparseIndices()

Int2 FindSparseIndices	(	Int8 *	in_array,
		Int8 *	out_array,
		Int4	length,
		PV_ARRAY_TYPE *	pv_array,
		Int4	pv_array_bts,
		Int4 *	counts,
		Int4	elems_per_bit
	)

Find an index into a sparse array using pv_array as a bit field, for a batch of indices.

Parameters

in_array	Input array of indices to translate [in]
out_array	Output array of indices to translate [out]
length	Number of indices to translate [in]
pv_array	Bit field (lookup table pv_array) [in]
pv_array_bts	Log2 of pv_array size [in]
pv_counts	Array of set bit counts, where pv_counts[i] is the number of bits set in pv_array[0..i-1] [in]
words_per_bit	Number of words represented by one bit in the pv_array [in]

Returns

Index into the sparse array