NCBI C++ ToolKit
Classes | Macros | Typedefs | Functions
jumper.h File Reference
#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/blast_util.h>
#include <algo/blast/core/blast_def.h>
#include <algo/blast/core/blast_gapalign.h>
#include <algo/blast/core/blast_parameters.h>
#include <algo/blast/core/blast_extend.h>
#include <algo/blast/core/gapinfo.h>
#include <algo/blast/core/blast_nalookup.h>
#include <algo/blast/core/blast_hspstream.h>
#include <algo/blast/core/spliced_hits.h>
+ Include dependency graph for jumper.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  JUMP
 
struct  JumperPrelimEditBlock
 Internal alignment edit script. More...
 
struct  JumperGapAlign
 Gapped alignment data needed for jumper. More...
 
struct  JumperEdit
 Single alignment error. More...
 
struct  JumperEditsBlock
 Alignment edit script for gapped alignment. More...
 
struct  SubjectIndex
 Index for a chunk of a subject sequence. More...
 
struct  SubjectIndexIterator
 Iterator over word locations in subject index. More...
 
struct  SequenceOverhangs
 Structure to save short unaligned subsequences outside an HSP. More...
 

Macros

#define JUMPER_MISMATCH   (0)
 
#define JUMPER_INSERTION   (-1)
 
#define JUMPER_DELETION   (-2)
 
#define SUBJECT_INDEX_WORD_LENGTH   (4)
 
#define MAPPER_SPLICE_SIGNAL   (0x80)
 
#define MAPPER_EXON   (0x40)
 
#define MAPPER_POLY_A   (0x20)
 
#define MAPPER_ADAPTER   (0x10)
 
#define MAPPER_FLAGS_PAIR_CONVERGENT   (1)
 
#define MAPPER_FLAGS_PAIR_DIVERGENT   (1 << 1)
 
#define MAPPER_FLAGS_PAIR_REARRANGED   (1 << 2)
 
#define MAPPER_FLAGS_PAIR   (MAPPER_FLAGS_PAIR_CONVERGENT | MAPPER_FLAGS_PAIR_DIVERGENT | MAPPER_FLAGS_PAIR_REARRANGED)
 

Typedefs

typedef Int2 JumperOpType
 Jumper edit script operation. More...
 
typedef struct JumperPrelimEditBlock JumperPrelimEditBlock
 Internal alignment edit script. More...
 
typedef struct JumperGapAlign JumperGapAlign
 Gapped alignment data needed for jumper. More...
 
typedef struct JumperEdit JumperEdit
 Single alignment error. More...
 
typedef struct JumperEditsBlock JumperEditsBlock
 Alignment edit script for gapped alignment. More...
 
typedef struct SubjectIndex SubjectIndex
 Index for a chunk of a subject sequence. More...
 
typedef struct SubjectIndexIterator SubjectIndexIterator
 Iterator over word locations in subject index. More...
 
typedef struct SequenceOverhangs SequenceOverhangs
 Structure to save short unaligned subsequences outside an HSP. More...
 

Functions

JumperGapAlignJumperGapAlignFree (JumperGapAlign *jumper_align)
 
JumperGapAlignJumperGapAlignNew (Int4 size)
 
Int4 JumperPrelimEditBlockAdd (JumperPrelimEditBlock *block, JumperOpType op)
 
JumperEditsBlockJumperEditsBlockFree (JumperEditsBlock *block)
 
JumperEditsBlockJumperEditsBlockDup (const JumperEditsBlock *block)
 
JumperEditsBlockJumperFindEdits (const Uint1 *query, const Uint1 *subject, BlastGapAlignStruct *gap_align)
 
GapEditScriptJumperPrelimEditBlockToGapEditScript (JumperPrelimEditBlock *rev_prelim_block, JumperPrelimEditBlock *fwd_prelim_block)
 Convert Jumper's preliminary edit script to GapEditScript. More...
 
Boolean JumperGoodAlign (const BlastGapAlignStruct *gap_align, const BlastHitSavingParameters *hit_params, Int4 num_identical, BlastContextInfo *range_info)
 Test whether an HSP should be saved. More...
 
Int4 JumperExtendRightWithTraceback (const Uint1 *query, const Uint1 *subject, int query_length, int subject_length, Int4 match_score, Int4 mismatch_score, Int4 gap_open, Int4 gap_extend, int max_mismatches, int window, Int4 *query_ext_len, Int4 *subject_ext_len, JumperPrelimEditBlock *edit_script, Int4 *num_identical, Boolean left_extension, Int4 *ungapped_ext_len, JUMP *jumper)
 Right extension with traceback. More...
 
int JumperGappedAlignmentCompressedWithTraceback (const Uint1 *query, const Uint1 *subject, Int4 query_length, Int4 subject_length, Int4 query_start, Int4 subject_start, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, Int4 *num_identical, Int4 *right_ungapped_ext_len)
 Jumper gapped alignment with traceback; 1 base per byte in query, 4 bases per byte in subject. More...
 
SubjectIndexSubjectIndexFree (SubjectIndex *sindex)
 Free subject index structure. More...
 
SubjectIndexSubjectIndexNew (BLAST_SequenceBlk *subject, Int4 width, Int4 word_size)
 Index a sequence, used for indexing compressed nucleotide subject sequence. More...
 
SubjectIndexIteratorSubjectIndexIteratorFree (SubjectIndexIterator *it)
 Free memory reserved for subject index word iterator. More...
 
SubjectIndexIteratorSubjectIndexIteratorNew (SubjectIndex *s_index, Int4 word, Int4 from, Int4 to)
 Create an iterator for locations of a given word. More...
 
Int4 SubjectIndexIteratorNext (SubjectIndexIterator *it)
 Return the next location of a word in an indexed sequence. More...
 
Int4 SubjectIndexIteratorPrev (SubjectIndexIterator *it)
 Return the previous location of a word in an indexed sequence. More...
 
Int4 BlastNaExtendJumper (BlastOffsetPair *offset_pairs, Int4 num_hits, const BlastInitialWordParameters *word_params, const BlastScoringParameters *score_params, const BlastHitSavingParameters *hit_params, LookupTableWrap *lookup_wrap, BLAST_SequenceBlk *query, BLAST_SequenceBlk *subject, BlastQueryInfo *query_info, BlastGapAlignStruct *gap_align, BlastHSPList *hsp_list, Uint4 s_range, SubjectIndex *s_index)
 Extend a list of word hits. More...
 
int JumperFindSpliceSignals (BlastHSP *hsp, Int4 query_len, const Uint1 *subject, Int4 subject_len)
 Find splice signals at the edges of an HSP and save them in the HSP. More...
 
GapEditScriptGapEditScriptCombine (GapEditScript **edit_script, GapEditScript **append)
 
JumperEditsBlockJumperEditsBlockCombine (JumperEditsBlock **block, JumperEditsBlock **append)
 
SequenceOverhangsSequenceOverhangsFree (SequenceOverhangs *overhangs)
 
Int2 DoAnchoredSearch (BLAST_SequenceBlk *query, BLAST_SequenceBlk *subject, Int4 word_size, BlastQueryInfo *query_info, BlastGapAlignStruct *gap_align, const BlastScoringParameters *score_params, const BlastHitSavingParameters *hit_params, BlastHSPStream *hsp_stream)
 Do a search against a single subject with smaller word size and with no database word frequency filtering, for queries that have partial hits. More...
 
Int2 FilterQueriesForMapping (Uint1 *sequence, Int4 length, Int4 offset, const SReadQualityOptions *options, BlastSeqLoc **seq_loc)
 
Int4 GetCutoffScore (Int4 query_length)
 Get alignment cutoff score for a given query length. More...
 

Macro Definition Documentation

◆ JUMPER_DELETION

#define JUMPER_DELETION   (-2)

Definition at line 56 of file jumper.h.

◆ JUMPER_INSERTION

#define JUMPER_INSERTION   (-1)

Definition at line 55 of file jumper.h.

◆ JUMPER_MISMATCH

#define JUMPER_MISMATCH   (0)

Definition at line 54 of file jumper.h.

◆ MAPPER_ADAPTER

#define MAPPER_ADAPTER   (0x10)

Definition at line 236 of file jumper.h.

◆ MAPPER_EXON

#define MAPPER_EXON   (0x40)

Definition at line 234 of file jumper.h.

◆ MAPPER_FLAGS_PAIR

Definition at line 253 of file jumper.h.

◆ MAPPER_FLAGS_PAIR_CONVERGENT

#define MAPPER_FLAGS_PAIR_CONVERGENT   (1)

Definition at line 249 of file jumper.h.

◆ MAPPER_FLAGS_PAIR_DIVERGENT

#define MAPPER_FLAGS_PAIR_DIVERGENT   (1 << 1)

Definition at line 250 of file jumper.h.

◆ MAPPER_FLAGS_PAIR_REARRANGED

#define MAPPER_FLAGS_PAIR_REARRANGED   (1 << 2)

Definition at line 251 of file jumper.h.

◆ MAPPER_POLY_A

#define MAPPER_POLY_A   (0x20)

Definition at line 235 of file jumper.h.

◆ MAPPER_SPLICE_SIGNAL

#define MAPPER_SPLICE_SIGNAL   (0x80)

Definition at line 233 of file jumper.h.

◆ SUBJECT_INDEX_WORD_LENGTH

#define SUBJECT_INDEX_WORD_LENGTH   (4)

Definition at line 148 of file jumper.h.

Typedef Documentation

◆ JumperEdit

typedef struct JumperEdit JumperEdit

Single alignment error.

◆ JumperEditsBlock

Alignment edit script for gapped alignment.

◆ JumperGapAlign

Gapped alignment data needed for jumper.

◆ JumperOpType

typedef Int2 JumperOpType

Jumper edit script operation.

Definition at line 59 of file jumper.h.

◆ JumperPrelimEditBlock

Internal alignment edit script.

◆ SequenceOverhangs

Structure to save short unaligned subsequences outside an HSP.

◆ SubjectIndex

typedef struct SubjectIndex SubjectIndex

Index for a chunk of a subject sequence.

◆ SubjectIndexIterator

Iterator over word locations in subject index.

Function Documentation

◆ BlastNaExtendJumper()

Int4 BlastNaExtendJumper ( BlastOffsetPair offset_pairs,
Int4  num_hits,
const BlastInitialWordParameters word_params,
const BlastScoringParameters score_params,
const BlastHitSavingParameters hit_params,
LookupTableWrap lookup_wrap,
BLAST_SequenceBlk query,
BLAST_SequenceBlk subject,
BlastQueryInfo query_info,
BlastGapAlignStruct gap_align,
BlastHSPList hsp_list,
Uint4  s_range,
SubjectIndex s_index 
)

Extend a list of word hits.

Definition at line 3253 of file jumper.c.

References ASSERT, Blast_HSPInit(), Blast_HSPListSaveHSP(), BlastHSPMappingInfoNew(), BSearchContextInfo(), COMPRESSION_RATIO, context, BlastQueryInfo::contexts, BlastGapAlignStruct::edit_script, BlastHSPMappingInfo::edits, eMBLookupTable, BlastSeg::end, BlastHSP::evalue, FALSE, BlastContextInfo::frame, i, BlastGapAlignStruct::jumper, JumperFindEdits(), JumperFindSpliceSignals(), JumperGappedAlignmentCompressedWithTraceback(), JumperGoodAlign(), JumperPrelimEditBlockToGapEditScript(), JumperGapAlign::left_prelim_block, BlastHitSavingOptions::longest_intron, LookupTableWrap::lut, LookupTableWrap::lut_type, BlastNaLookupTable::lut_word_length, BlastMBLookupTable::lut_word_length, BlastHSP::map_info, MAX, MIN, NULL, BlastHSP::num_ident, BlastSeg::offset, BlastHitSavingParameters::options, BlastScoringParameters::penalty, BlastOffsetPair::q_off, BlastOffsetPair::qs_offsets, BlastHSP::query, query, BlastContextInfo::query_length, BlastContextInfo::query_offset, BlastGapAlignStruct::query_start, BlastGapAlignStruct::query_stop, JumperGapAlign::right_prelim_block, round(), s_CompareOffsetPairsByDiagQuery(), s_CreateHSPForWordHit(), BlastOffsetPair::s_off, s_SaveSubjectOverhangs(), s_ShiftGaps(), BlastGapAlignStruct::score, BlastHitSavingOptions::splice, BlastHSP::subject, subject, SUBJECT_INDEX_WORD_LENGTH, BlastGapAlignStruct::subject_start, BlastGapAlignStruct::subject_stop, SubjectIndexIteratorFree(), SubjectIndexIteratorNew(), SubjectIndexIteratorNext(), SubjectIndexIteratorPrev(), UNPACK_BASE, BlastNaLookupTable::word_length, and BlastMBLookupTable::word_length.

Referenced by JumperNaWordFinder().

◆ DoAnchoredSearch()

Int2 DoAnchoredSearch ( BLAST_SequenceBlk query,
BLAST_SequenceBlk subject,
Int4  word_size,
BlastQueryInfo query_info,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
const BlastHitSavingParameters hit_params,
BlastHSPStream hsp_stream 
)

Do a search against a single subject with smaller word size and with no database word frequency filtering, for queries that have partial hits.

The subject is scanned only where one expects to find an exon. This is to find smaller and low complexity exons.

Parameters
queryConcatenated query [in]
subjectSubject sequence [in]
word_sizeMinimum word size to use in scanning [in]
query_infoQuery information structure [in]
gap_alignData for gapped alignment [in|out]
score_paramsAlignment scoring parameters [in]
hit_paramsHit saving parameters [in]
hsp_streamQueries will be selected based on hits in hsp_stream and new hits will be written to it [in|out]
Returns
Status

Definition at line 4394 of file jumper.c.

References Blast_HSPListFree(), Blast_HSPListNew(), Blast_HSPListSaveHSP(), BLASTERR_MEMORY, BlastHSPStreamWrite(), BlastHSP::context, context, BlastQueryInfo::contexts, BlastHSPWriter::data, DoAnchoredScan(), eMT_Lock, eMT_Unlock, BlastSeg::end, FindPartialyCoveredQueries(), HSPContainer::hsp, HSPChainFree(), HSPChain::hsps, BlastHitSavingOptions::longest_intron, MAX, MT_LOCK_Do, HSPContainer::next, HSPChain::next, NULL, BlastQueryInfo::num_queries, BlastSeg::offset, BlastHSPList::oid, BlastHitSavingParameters::options, BlastHSP::query, query, BlastContextInfo::query_length, BlastContextInfo::query_offset, BlastHSP::subject, subject, BlastHSPStream::writer, and BlastHSPStream::x_lock.

Referenced by BLAST_PreliminarySearchEngine().

◆ FilterQueriesForMapping()

Int2 FilterQueriesForMapping ( Uint1 sequence,
Int4  length,
Int4  offset,
const SReadQualityOptions options,
BlastSeqLoc **  seq_loc 
)

Definition at line 4531 of file jumper.c.

References SReadQualityOptions::frac_ambig, i, offset, s_FindDimerEntropy(), and s_MaskSequence().

Referenced by BlastSetUp_Filter().

◆ GapEditScriptCombine()

GapEditScript* GapEditScriptCombine ( GapEditScript **  edit_script,
GapEditScript **  append 
)

◆ GetCutoffScore()

Int4 GetCutoffScore ( Int4  query_length)

Get alignment cutoff score for a given query length.

The function assumes that score for match is 1

Definition at line 4563 of file jumper.c.

Referenced by JumperGoodAlign(), and s_BlastHSPMapperSplicedPairedRun().

◆ JumperEditsBlockCombine()

JumperEditsBlock* JumperEditsBlockCombine ( JumperEditsBlock **  block,
JumperEditsBlock **  append 
)

◆ JumperEditsBlockDup()

JumperEditsBlock* JumperEditsBlockDup ( const JumperEditsBlock block)

Definition at line 2737 of file jumper.c.

References JumperEditsBlock::edits, JumperEditsBlockNew(), NULL, and JumperEditsBlock::num_edits.

Referenced by Blast_HSPClone().

◆ JumperEditsBlockFree()

JumperEditsBlock* JumperEditsBlockFree ( JumperEditsBlock block)

◆ JumperExtendRightWithTraceback()

Int4 JumperExtendRightWithTraceback ( const Uint1 query,
const Uint1 subject,
int  query_length,
int  subject_length,
Int4  match_score,
Int4  mismatch_score,
Int4  gap_open,
Int4  gap_extend,
int  max_mismatches,
int  window,
Int4 query_ext_len,
Int4 subject_ext_len,
JumperPrelimEditBlock edit_script,
Int4 num_identical,
Boolean  left_extension,
Int4 ungapped_ext_len,
JUMP jumper 
)

◆ JumperFindEdits()

JumperEditsBlock* JumperFindEdits ( const Uint1 query,
const Uint1 subject,
BlastGapAlignStruct gap_align 
)

◆ JumperFindSpliceSignals()

int JumperFindSpliceSignals ( BlastHSP hsp,
Int4  query_len,
const Uint1 subject,
Int4  subject_len 
)

Find splice signals at the edges of an HSP and save them in the HSP.

Parameters
hspHSP [in|out]
query_lenLength of the query/read [in]
subjectSubject sequence [in]
subject_lenSubject length [in]
Returns
Zero on success

Definition at line 2947 of file jumper.c.

References BlastSeg::end, BlastHSPMappingInfo::left_edge, BlastHSP::map_info, MAPPER_EXON, BlastSeg::offset, BlastHSP::query, BlastHSPMappingInfo::right_edge, BlastHSP::subject, subject, and UNPACK_BASE.

Referenced by BlastNaExtendJumper(), s_CreateHSP(), s_CreateHSPForWordHit(), and ShortRead_IndexedWordFinder().

◆ JumperGapAlignFree()

JumperGapAlign* JumperGapAlignFree ( JumperGapAlign jumper_align)

◆ JumperGapAlignNew()

JumperGapAlign* JumperGapAlignNew ( Int4  size)

◆ JumperGappedAlignmentCompressedWithTraceback()

int JumperGappedAlignmentCompressedWithTraceback ( const Uint1 query,
const Uint1 subject,
Int4  query_length,
Int4  subject_length,
Int4  query_start,
Int4  subject_start,
BlastGapAlignStruct gap_align,
const BlastScoringParameters score_params,
Int4 num_identical,
Int4 right_ungapped_ext_len 
)

◆ JumperGoodAlign()

Boolean JumperGoodAlign ( const BlastGapAlignStruct gap_align,
const BlastHitSavingParameters hit_params,
Int4  num_identical,
BlastContextInfo range_info 
)

◆ JumperPrelimEditBlockAdd()

Int4 JumperPrelimEditBlockAdd ( JumperPrelimEditBlock block,
JumperOpType  op 
)

◆ JumperPrelimEditBlockToGapEditScript()

GapEditScript* JumperPrelimEditBlockToGapEditScript ( JumperPrelimEditBlock rev_prelim_block,
JumperPrelimEditBlock fwd_prelim_block 
)

◆ SequenceOverhangsFree()

SequenceOverhangs* SequenceOverhangsFree ( SequenceOverhangs overhangs)

◆ SubjectIndexFree()

SubjectIndex* SubjectIndexFree ( SubjectIndex sindex)

Free subject index structure.

Definition at line 3822 of file jumper.c.

References BlastNaLookupTableDestruct(), free(), i, SubjectIndex::lookups, NULL, and SubjectIndex::num_lookups.

Referenced by JumperNaWordFinder(), and s_SubjectIndexNewCleanup().

◆ SubjectIndexIteratorFree()

SubjectIndexIterator* SubjectIndexIteratorFree ( SubjectIndexIterator it)

Free memory reserved for subject index word iterator.

Definition at line 3972 of file jumper.c.

References free(), and NULL.

Referenced by BlastNaExtendJumper(), and SubjectIndexIteratorNew().

◆ SubjectIndexIteratorNew()

SubjectIndexIterator* SubjectIndexIteratorNew ( SubjectIndex s_index,
Int4  word,
Int4  from,
Int4  to 
)

Create an iterator for locations of a given word.

Parameters
s_indexSequence index [in]
wordNucleotide word to be searched [in]
fromSequence location to begin search [in]
toSequence location to end search [in]
Returns
Word location iterator

Definition at line 3983 of file jumper.c.

References ASSERT, calloc(), lookup(), SubjectIndexIterator::lookup_index, SubjectIndexIterator::lookup_pos, SubjectIndex::lookups, NA_HITS_PER_CELL, NULL, SubjectIndex::num_lookups, SubjectIndexIterator::num_words, SubjectIndexIterator::subject_index, SubjectIndexIteratorFree(), SubjectIndexIterator::to, SubjectIndex::width, SubjectIndexIterator::word, and SubjectIndexIterator::word_index.

Referenced by BlastNaExtendJumper().

◆ SubjectIndexIteratorNext()

Int4 SubjectIndexIteratorNext ( SubjectIndexIterator it)

Return the next location of a word in an indexed sequence.

Parameters
itIterator [in|out]
Returns
Word location or value less than zero if no more words are found

Definition at line 4045 of file jumper.c.

References ASSERT, lookup(), SubjectIndexIterator::lookup_index, SubjectIndexIterator::lookup_pos, SubjectIndex::lookups, NA_HITS_PER_CELL, NULL, SubjectIndex::num_lookups, SubjectIndexIterator::num_words, SubjectIndexIterator::subject_index, SubjectIndexIterator::to, SubjectIndexIterator::word, and SubjectIndexIterator::word_index.

Referenced by BlastNaExtendJumper().

◆ SubjectIndexIteratorPrev()

Int4 SubjectIndexIteratorPrev ( SubjectIndexIterator it)

Return the previous location of a word in an indexed sequence.

Parameters
itIterator [in|out]
Returns
Word location or value less than zero if no more words are found

Definition at line 4094 of file jumper.c.

References ASSERT, lookup(), SubjectIndexIterator::lookup_index, SubjectIndexIterator::lookup_pos, SubjectIndex::lookups, NA_HITS_PER_CELL, NULL, SubjectIndexIterator::num_words, SubjectIndexIterator::subject_index, SubjectIndexIterator::word, and SubjectIndexIterator::word_index.

Referenced by BlastNaExtendJumper().

◆ SubjectIndexNew()

SubjectIndex* SubjectIndexNew ( BLAST_SequenceBlk subject,
Int4  width,
Int4  word_size 
)

Index a sequence, used for indexing compressed nucleotide subject sequence.

The index consists of a list of lookup tables, each covering width number of bases.

Parameters
subjectSequence to be indexed [in]
widthNumber of bases covered by a single lookup table [in]
word_sizeWord size to be used in the lookup table [in]
Returns
Pointer to the created index

Definition at line 3874 of file jumper.c.

References ASSERT, BlastNaLookupTableNew(), calloc(), free(), i, SSeqRange::left, SubjectIndex::lookups, malloc(), MIN, NULL, SubjectIndex::num_lookups, SSeqRange::right, s_SubjectIndexNewCleanup(), BLAST_SequenceBlk::sequence, BlastSeqLoc::ssr, subject, SubjectIndex::width, and LookupTableOptions::word_size.

Referenced by JumperNaWordFinder().

Modified on Sun Apr 21 03:39:05 2024 by modify_doxy.py rev. 669887