NCBI C++ ToolKit
Functions | Variables
greedy_align.c File Reference

Functions to perform greedy affine and non-affine gapped alignment. More...

#include <algo/blast/core/greedy_align.h>
#include <algo/blast/core/ncbi_math.h>
#include <algo/blast/core/blast_util.h>
+ Include dependency graph for greedy_align.c:

Go to the source code of this file.

Go to the SVN repository for this file.

Functions

SMBSpaceMBSpaceNew (int num_space_arrays)
 see greedy_align.h for description More...
 
static void s_RefreshMBSpace (SMBSpace *space)
 Mark the input collection of space structures as unused. More...
 
void MBSpaceFree (SMBSpace *space)
 see greedy_align.h for description More...
 
static SGreedyOffsets_GetMBSpace (SMBSpace *pool, Int4 num_alloc)
 Allocate a specified number of SGreedyOffset structures from a memory pool. More...
 
static EGapAlignOpType s_GetNextAffineTbackFromMatch (SGreedyOffset **last_seq2_off, Int4 *diag_lower, Int4 *diag_upper, Int4 *d, Int4 diag, Int4 op_cost, Int4 *seq2_index)
 During the traceback for a greedy alignment with affine gap penalties, determine the next state of the traceback after moving upwards in the traceback array from a substitution. More...
 
static EGapAlignOpType s_GetNextAffineTbackFromIndel (SGreedyOffset **last_seq2_off, Int4 *diag_lower, Int4 *diag_upper, Int4 *d, Int4 diag, Int4 gap_open, Int4 gap_extend, EGapAlignOpType IorD)
 During the traceback for a greedy alignment with affine gap penalties, determine the next state of the traceback after moving upwards in the traceback array from an insertion or deletion. More...
 
static Int4 s_GetNextNonAffineTback (Int4 **last_seq2_off, Int4 d, Int4 diag, Int4 *seq2_index)
 During the traceback for a non-affine greedy alignment, compute the diagonal that will result from the next traceback operation. More...
 
static NCBI_INLINE Int4 s_FindFirstMismatch (const Uint1 *seq1, const Uint1 *seq2, Int4 len1, Int4 len2, Int4 seq1_index, Int4 seq2_index, Boolean *fence_hit, Boolean reverse, Uint1 rem)
 Find the first mismatch in a pair of sequences. 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)
 see greedy_align.h for description More...
 
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)
 See greedy_align.h for description. More...
 

Variables

static const Int4 kInvalidOffset = -2
 Signal that a diagonal is invalid. More...
 

Detailed Description

Functions to perform greedy affine and non-affine gapped alignment.

Reference: Zhang et. al., "A Greedy Algorithm for Aligning DNA Sequences" Journal of Computational Biology vol 7 pp 203-214

Definition in file greedy_align.c.

Function Documentation

◆ BLAST_AffineGreedyAlign()

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 
)

◆ BLAST_GreedyAlign()

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 
)

◆ MBSpaceFree()

void MBSpaceFree ( SMBSpace space)

see greedy_align.h for description

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().

◆ MBSpaceNew()

SMBSpace* MBSpaceNew ( int  num_space_arrays)

see greedy_align.h for description

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().

◆ s_FindFirstMismatch()

static NCBI_INLINE Int4 s_FindFirstMismatch ( const Uint1 seq1,
const Uint1 seq2,
Int4  len1,
Int4  len2,
Int4  seq1_index,
Int4  seq2_index,
Boolean fence_hit,
Boolean  reverse,
Uint1  rem 
)
static

Find the first mismatch in a pair of sequences.

Parameters
seq1First sequence (always uncompressed) [in]
seq2Second sequence (compressed or uncompressed) [in]
len1Length of seq1 [in]
len2Length of seq2 [in]
seq1_indexStarting offset in seq1 [in]
seq2_indexStarting offset in seq2 [in]
fence_hitSet to TRUE if an end-of-initialized-data sentinel is encountered in seq2 [out]
reverseIf TRUE, comparison proceeds backwards from the end of seq1 and seq2 [in]
remWhen seq2 is part of a larger compressed sequence, this is the offset within a byte of seq2[0]. Set to 4 if seq2 is uncompressed [in]
Returns
Number of exact matches found before a mismatch was encountered

Definition at line 313 of file greedy_align.c.

References ASSERT, FENCE_SENTRY, NCBI2NA_UNPACK_BASE, tmp, and TRUE.

Referenced by BLAST_AffineGreedyAlign(), and BLAST_GreedyAlign().

◆ s_GetMBSpace()

static SGreedyOffset* s_GetMBSpace ( SMBSpace pool,
Int4  num_alloc 
)
static

Allocate a specified number of SGreedyOffset structures from a memory pool.

Parameters
poolThe memory pool [in]
num_allocThe number of structures to allocate [in]
Returns
Pointer to the allocated memory, or NULL in case of error

Definition at line 100 of file greedy_align.c.

References ErrPostEx, MBSpaceNew(), SMBSpace::next, NULL, SEV_WARNING, SMBSpace::space_allocated, SMBSpace::space_array, and SMBSpace::space_used.

Referenced by BLAST_AffineGreedyAlign(), and BLAST_GreedyAlign().

◆ s_GetNextAffineTbackFromIndel()

static EGapAlignOpType s_GetNextAffineTbackFromIndel ( SGreedyOffset **  last_seq2_off,
Int4 diag_lower,
Int4 diag_upper,
Int4 d,
Int4  diag,
Int4  gap_open,
Int4  gap_extend,
EGapAlignOpType  IorD 
)
static

During the traceback for a greedy alignment with affine gap penalties, determine the next state of the traceback after moving upwards in the traceback array from an insertion or deletion.

Parameters
last_seq2_offArray of offsets into the second sequence; last_seq2_off[d][k] gives the largest offset into the second sequence that lies on diagonal k and has distance d [in]
diag_lowerArray of lower bounds on diagonal index [in]
diag_upperArray of upper bounds on diagonal index [in]
dStarting distance [in][out]
diagThe diagonal of the current traceback position [in]
gap_openopen a gap [in]
gap_extend(Modified) cost to extend a gap [in]
IorDThe state of the traceback at present [in]
Returns
The state for the next traceback operation

Definition at line 199 of file greedy_align.c.

References ASSERT, SGreedyOffset::delete_off, eGapAlignIns, eGapAlignSub, SGreedyOffset::insert_off, and kInvalidOffset.

Referenced by BLAST_AffineGreedyAlign().

◆ s_GetNextAffineTbackFromMatch()

static EGapAlignOpType s_GetNextAffineTbackFromMatch ( SGreedyOffset **  last_seq2_off,
Int4 diag_lower,
Int4 diag_upper,
Int4 d,
Int4  diag,
Int4  op_cost,
Int4 seq2_index 
)
static

During the traceback for a greedy alignment with affine gap penalties, determine the next state of the traceback after moving upwards in the traceback array from a substitution.

Parameters
last_seq2_offArray of offsets into the second sequence; last_seq2_off[d][k] gives the largest offset into the second sequence that lies on diagonal k and has distance d [in]
diag_lowerArray of lower bounds on diagonal index [in]
diag_upperArray of upper bounds on diagonal index [in]
dStarting distance [in][out]
diagThe diagonal of the current traceback position [in]
op_costThe sum of the match and mismatch scores [in]
seq2_indexThe offset into the second sequence after the traceback operation has completed [out]
Returns
The state for the next traceback operation

Definition at line 149 of file greedy_align.c.

References SGreedyOffset::delete_off, eGapAlignDel, eGapAlignIns, eGapAlignSub, SGreedyOffset::insert_off, SGreedyOffset::match_off, and MAX.

Referenced by BLAST_AffineGreedyAlign().

◆ s_GetNextNonAffineTback()

static Int4 s_GetNextNonAffineTback ( Int4 **  last_seq2_off,
Int4  d,
Int4  diag,
Int4 seq2_index 
)
static

During the traceback for a non-affine greedy alignment, compute the diagonal that will result from the next traceback operation.

Parameters
last_seq2_offArray of offsets into the second sequence; last_seq2_off[d][k] gives the largest offset into the second sequence that lies on diagonal k and has distance d [in]
dStarting distance [in]
diagIndex of diagonal that produced the starting distance [in]
seq2_indexThe offset into the second sequence after the traceback operation has completed [out]
Returns
The diagonal resulting from the next traceback operation being applied

Definition at line 276 of file greedy_align.c.

References MAX.

Referenced by BLAST_GreedyAlign().

◆ s_RefreshMBSpace()

static void s_RefreshMBSpace ( SMBSpace space)
static

Mark the input collection of space structures as unused.

Parameters
spaceThe space to mark

Definition at line 71 of file greedy_align.c.

References SMBSpace::next, NULL, and SMBSpace::space_used.

Referenced by BLAST_AffineGreedyAlign(), and BLAST_GreedyAlign().

Variable Documentation

◆ kInvalidOffset

const Int4 kInvalidOffset = -2
static

Signal that a diagonal is invalid.

Definition at line 129 of file greedy_align.c.

Referenced by BLAST_AffineGreedyAlign(), BLAST_GreedyAlign(), and s_GetNextAffineTbackFromIndel().

Modified on Fri May 24 14:58:15 2024 by modify_doxy.py rev. 669887