Prototypes and structures for greedy gapped alignment. More...

#include <algo/blast/core/ncbi_std.h>
#include <algo/blast/core/gapinfo.h>

Include dependency graph for greedy_align.h:

This graph shows which files directly or indirectly include 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 high-scoring 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 high-scoring 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 non-affine 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...

Detailed Description

Prototypes and structures for greedy gapped alignment.

Definition in file greedy_align.h.

Macro Definition Documentation

◆ GREEDY_MAX_COST

#define GREEDY_MAX_COST 1000

The largest distance to be examined for an optimal alignment.

Definition at line 50 of file greedy_align.h.

◆ GREEDY_MAX_COST_FRACTION

#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 Documentation

◆ SGreedyAlignMem

typedef struct SGreedyAlignMem SGreedyAlignMem

All auxiliary memory needed for the greedy extension algorithm.

◆ SGreedyOffset

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 high-scoring alignment for a given start point

◆ SGreedySeed

typedef struct SGreedySeed SGreedySeed

Structure for locating high-scoring seeds for greedy alignment.

◆ SMBSpace

typedef struct SMBSpace SMBSpace

Space structure for greedy alignment algorithm.

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
	)

Perform the greedy extension algorithm with affine gap penalties.

Parameters

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	X-dropoff 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]

Returns: The score of the alignment

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

◆ 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
	)

Perform the greedy extension algorithm with non-affine gap penalties.

Parameters

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	X-dropoff 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]

Returns: The minimum distance between the two sequences, i.e. the number of mismatches plus gaps in the resulting alignment

Perform the greedy extension algorithm with non-affine 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().

◆ MBSpaceFree()

void MBSpaceFree ( SMBSpace * space )

Free the space structure.

Parameters

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

◆ MBSpaceNew()

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.

Parameters

num_space_arrays number of array elements to allocated [in]

Returns: Pointer to allocated structure, or NULL upon failure

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

Classes

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ GREEDY_MAX_COST

◆ GREEDY_MAX_COST_FRACTION

Typedef Documentation

◆ SGreedyAlignMem

◆ SGreedyOffset

◆ SGreedySeed

◆ SMBSpace

Function Documentation

◆ BLAST_AffineGreedyAlign()

◆ BLAST_GreedyAlign()

◆ MBSpaceFree()

◆ MBSpaceNew()