NCBI C++ ToolKit

Prototypes and structures for greedy gapped alignment. More...
Go to the source code of this file.
Go to the SVN repository for this file.
Classes  
struct  SGreedyOffset 
Bookkeeping structure for greedy alignment. More...  
struct  SMBSpace 
Space structure for greedy alignment algorithm. More...  
struct  SGreedyAlignMem 
All auxiliary memory needed for the greedy extension algorithm. More...  
struct  SGreedySeed 
Structure for locating highscoring seeds for greedy alignment. More...  
Macros  
#define  GREEDY_MAX_COST_FRACTION 2 
sequence_length / (this number) is a measure of how hard the alignment code will work to find the optimal alignment; in fact this gives a worst case bound on the number of loop iterations More...  
#define  GREEDY_MAX_COST 1000 
The largest distance to be examined for an optimal alignment. More...  
Typedefs  
typedef struct SGreedyOffset  SGreedyOffset 
Bookkeeping structure for greedy alignment. More...  
typedef struct SMBSpace  SMBSpace 
Space structure for greedy alignment algorithm. More...  
typedef struct SGreedyAlignMem  SGreedyAlignMem 
All auxiliary memory needed for the greedy extension algorithm. More...  
typedef struct SGreedySeed  SGreedySeed 
Structure for locating highscoring seeds for greedy alignment. More...  
Functions  
SMBSpace *  MBSpaceNew (int num_space_arrays) 
Allocate a space structure for greedy alignment At least num_space_arrays will be allocated, possibly more if the number is low. More...  
void  MBSpaceFree (SMBSpace *sp) 
Free the space structure. More...  
Int4  BLAST_GreedyAlign (const Uint1 *seq1, Int4 len1, const Uint1 *seq2, Int4 len2, Boolean reverse, Int4 xdrop_threshold, Int4 match_cost, Int4 mismatch_cost, Int4 *seq1_align_len, Int4 *seq2_align_len, SGreedyAlignMem *aux_data, GapPrelimEditBlock *edit_block, Uint1 rem, Boolean *fence_hit, SGreedySeed *seed) 
Perform the greedy extension algorithm with nonaffine gap penalties. More...  
Int4  BLAST_AffineGreedyAlign (const Uint1 *seq1, Int4 len1, const Uint1 *seq2, Int4 len2, Boolean reverse, Int4 xdrop_threshold, Int4 match_cost, Int4 mismatch_cost, Int4 in_gap_open, Int4 in_gap_extend, Int4 *seq1_align_len, Int4 *seq2_align_len, SGreedyAlignMem *aux_data, GapPrelimEditBlock *edit_block, Uint1 rem, Boolean *fence_hit, SGreedySeed *seed) 
Perform the greedy extension algorithm with affine gap penalties. More...  
Prototypes and structures for greedy gapped alignment.
Definition in file greedy_align.h.
#define GREEDY_MAX_COST 1000 
The largest distance to be examined for an optimal alignment.
Definition at line 50 of file greedy_align.h.
#define GREEDY_MAX_COST_FRACTION 2 
sequence_length / (this number) is a measure of how hard the alignment code will work to find the optimal alignment; in fact this gives a worst case bound on the number of loop iterations
Definition at line 47 of file greedy_align.h.
typedef struct SGreedyAlignMem SGreedyAlignMem 
All auxiliary memory needed for the greedy extension algorithm.
typedef struct SGreedyOffset SGreedyOffset 
Bookkeeping structure for greedy alignment.
When aligning two sequences, the members of this structure store the largest offset into the second sequence that leads to a highscoring alignment for a given start point
typedef struct SGreedySeed SGreedySeed 
Structure for locating highscoring seeds for greedy alignment.
Int4 BLAST_AffineGreedyAlign  (  const Uint1 *  seq1, 
Int4  len1,  
const Uint1 *  seq2,  
Int4  len2,  
Boolean  reverse,  
Int4  xdrop_threshold,  
Int4  match_score,  
Int4  mismatch_score,  
Int4  in_gap_open,  
Int4  in_gap_extend,  
Int4 *  seq1_align_len,  
Int4 *  seq2_align_len,  
SGreedyAlignMem *  aux_data,  
GapPrelimEditBlock *  edit_block,  
Uint1  rem,  
Boolean *  fence_hit,  
SGreedySeed *  seed  
) 
Perform the greedy extension algorithm with affine gap penalties.
seq1  First sequence (always uncompressed) [in] 
len1  Maximal extension length in first sequence [in] 
seq2  Second sequence (may be compressed) [in] 
len2  Maximal extension length in second sequence [in] 
reverse  Is extension performed in backwards direction? [in] 
xdrop_threshold  Xdropoff value to use in extension [in] 
match_cost  Match score to use in extension [in] 
mismatch_cost  Mismatch score to use in extension [in] 
in_gap_open  Gap opening penalty [in] 
in_gap_extend  Gap extension penalty [in] 
seq1_align_len  Length of extension on sequence 1 [out] 
seq2_align_len  Length of extension on sequence 2 [out] 
aux_data  Structure containing all preallocated memory [in] 
edit_block  Edit script structure for saving traceback. Traceback is not saved if NULL is passed. [in] [out] 
rem  Offset within a byte of the compressed second sequence. Set to 4 if sequence is uncompressed. [in] 
fence_hit  True is returned here if overrun is detected. [in] 
seed  Structure to remember longest run of exact matches [out] 
Perform the greedy extension algorithm with affine gap penalties.
Definition at line 755 of file greedy_align.c.
References ASSERT, BLAST_Gdb3(), BLAST_GreedyAlign(), SGreedyOffset::delete_off, SGreedyAlignMem::diag_bounds, eGapAlignDel, eGapAlignIns, eGapAlignSub, FALSE, for(), GapPrelimEditBlockAdd(), SGreedyOffset::insert_off, kInvalidOffset, SGreedyAlignMem::last_seq2_off_affine, SGreedyOffset::match_off, MAX, SGreedyAlignMem::max_dist, SGreedyAlignMem::max_score, MBSpaceNew(), MIN, NULL, s_FindFirstMismatch(), s_GetMBSpace(), s_GetNextAffineTbackFromIndel(), s_GetNextAffineTbackFromMatch(), s_RefreshMBSpace(), seed, SGreedyAlignMem::space, and TRUE.
Referenced by BLAST_GreedyGappedAlignment().
Int4 BLAST_GreedyAlign  (  const Uint1 *  seq1, 
Int4  len1,  
const Uint1 *  seq2,  
Int4  len2,  
Boolean  reverse,  
Int4  xdrop_threshold,  
Int4  match_cost,  
Int4  mismatch_cost,  
Int4 *  seq1_align_len,  
Int4 *  seq2_align_len,  
SGreedyAlignMem *  aux_data,  
GapPrelimEditBlock *  edit_block,  
Uint1  rem,  
Boolean *  fence_hit,  
SGreedySeed *  seed  
) 
Perform the greedy extension algorithm with nonaffine gap penalties.
seq1  First sequence (always uncompressed) [in] 
len1  Maximal extension length in first sequence [in] 
seq2  Second sequence (may be compressed) [in] 
len2  Maximal extension length in second sequence [in] 
reverse  Is extension performed in backwards direction? [in] 
xdrop_threshold  Xdropoff value to use in extension [in] 
match_cost  Match score to use in extension [in] 
mismatch_cost  Mismatch score to use in extension [in] 
seq1_align_len  Length of extension on sequence 1 [out] 
seq2_align_len  Length of extension on sequence 2 [out] 
aux_data  Structure containing all preallocated memory [in] 
edit_block  Edit script structure for saving traceback. Traceback is not saved if NULL is passed. [in] [out] 
rem  Offset within a byte of the compressed second sequence. Set to 4 if sequence is uncompressed. [in] 
fence_hit  True is returned here if overrun is detected. [in] 
seed  Structure to remember longest run of exact matches [out] 
Perform the greedy extension algorithm with nonaffine gap penalties.
Definition at line 380 of file greedy_align.c.
References done, eGapAlignDel, eGapAlignIns, eGapAlignSub, FALSE, for(), GapPrelimEditBlockAdd(), kInvalidOffset, SGreedyAlignMem::last_seq2_off, MAX, SGreedyAlignMem::max_dist, SGreedyAlignMem::max_score, MBSpaceNew(), NULL, s_FindFirstMismatch(), s_GetMBSpace(), s_GetNextNonAffineTback(), s_RefreshMBSpace(), seed, SGreedyAlignMem::space, and TRUE.
Referenced by BLAST_AffineGreedyAlign().
void MBSpaceFree  (  SMBSpace *  space  ) 
Free the space structure.
sp  Linked list of structures to free 
Free the space structure.
Definition at line 80 of file greedy_align.c.
References SMBSpace::next, NULL, sfree, and SMBSpace::space_array.
Referenced by BOOST_AUTO_TEST_CASE(), and s_BlastGreedyAlignsFree().
Allocate a space structure for greedy alignment At least num_space_arrays will be allocated, possibly more if the number is low.
num_space_arrays  number of array elements to allocated [in] 
Allocate a space structure for greedy alignment At least num_space_arrays will be allocated, possibly more if the number is low.
Definition at line 43 of file greedy_align.c.
References malloc(), MAX, SMBSpace::next, NULL, sfree, SMBSpace::space_allocated, SMBSpace::space_array, and SMBSpace::space_used.
Referenced by BLAST_AffineGreedyAlign(), BLAST_GreedyAlign(), BOOST_AUTO_TEST_CASE(), s_BlastGreedyAlignMemAlloc(), and s_GetMBSpace().