NCBI C++ ToolKit
Classes | Typedefs | Enumerations | Functions
link_hsps.c File Reference

Functions to link with use of sum statistics. More...

#include <algo/blast/core/link_hsps.h>
#include <algo/blast/core/blast_util.h>
#include "blast_hits_priv.h"
+ Include dependency graph for link_hsps.c:

Go to the source code of this file.

Go to the SVN repository for this file.

Classes

struct  BlastHSPLink
 The following structure is used in "link_hsps" to decide between two different "gapping" models. More...
 
struct  LinkHSPStruct
 Structure containing all information internal to the process of linking HSPs. More...
 
struct  LinkHelpStruct
 The helper array contains the info used frequently in the inner for loops of the HSP linking algorithm. More...
 
struct  BlastLinkedHSPSet
 Simple doubly linked list of HSPs, used for calculating sum statistics. More...
 

Typedefs

typedef enum ELinkOrderingMethod ELinkOrderingMethod
 Describes the method for ordering HSPs. More...
 
typedef struct BlastHSPLink BlastHSPLink
 The following structure is used in "link_hsps" to decide between two different "gapping" models. More...
 
typedef struct LinkHSPStruct LinkHSPStruct
 Structure containing all information internal to the process of linking HSPs. More...
 
typedef struct LinkHelpStruct LinkHelpStruct
 The helper array contains the info used frequently in the inner for loops of the HSP linking algorithm. More...
 
typedef struct BlastLinkedHSPSet BlastLinkedHSPSet
 Simple doubly linked list of HSPs, used for calculating sum statistics. More...
 

Enumerations

enum  ELinkOrderingMethod { eLinkSmallGaps = 0 , eLinkLargeGaps = 1 , eOrderingMethods = 2 }
 Describes the method for ordering HSPs. More...
 

Functions

static int s_FwdCompareHSPs (const void *v1, const void *v2)
 Callback used by qsort to sort a list of HSPs, encapsulated in LinkHSPStruct structures, in order of increasing query start offset. More...
 
static int s_FwdCompareHSPsTransl (const void *v1, const void *v2)
 Like s_FwdCompareHSPs, except with additional logic to distinguish HSPs that lie within different strands of a single translated query sequence. More...
 
static int s_RevCompareHSPs (const void *v1, const void *v2)
 Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset. More...
 
static int s_RevCompareHSPsTransl (const void *v1, const void *v2)
 Like s_RevCompareHSPs, except with additional logic to distinguish HSPs that lie within different strands of a single translated query sequence. More...
 
static int s_RevCompareHSPsTbn (const void *v1, const void *v2)
 Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset (suitable for use with tblastn). More...
 
static int s_RevCompareHSPsTbx (const void *v1, const void *v2)
 Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset (suitable for use with tblastx). More...
 
static LinkHSPStructs_LinkHSPStructReset (LinkHSPStruct *lhsp)
 Initialize a LinkHSPStruct. More...
 
static Int2 s_BlastEvenGapLinkHSPs (EBlastProgramType program_number, BlastHSPList *hsp_list, const BlastQueryInfo *query_info, Int4 subject_length, const BlastScoreBlk *sbp, const BlastLinkHSPParameters *link_hsp_params, Boolean gapped_calculation)
 Perform even gap linking on a list of HSPs. More...
 
static double s_SumHSPEvalue (EBlastProgramType program_number, const BlastQueryInfo *query_info, Int4 subject_length, const BlastLinkHSPParameters *link_hsp_params, BlastLinkedHSPSet *head_hsp, BlastLinkedHSPSet *new_hsp, double *sum_score)
 Calculates e-value of a set of HSPs with sum statistics. More...
 
static int s_FwdCompareLinkedHSPSets (const void *v1, const void *v2)
 Callback for sorting an array of HSPs, encapsulated in BlastLinkedHSPSet structures, in order of increasing query starting offset. More...
 
static int s_SumScoreCompareLinkedHSPSets (const void *v1, const void *v2)
 Callback used by qsort to sort a list of BlastLinkedHSPSet structures in order of decreasing sum score. More...
 
static Int4 s_HSPOffsetBinarySearch (BlastLinkedHSPSet **hsp_array, Int4 size, Uint4 queryId, Int4 offset)
 Find an HSP on the same queryId as the one given, with closest start offset that is greater than a specified value. More...
 
static Int4 s_HSPOffsetEndBinarySearch (BlastLinkedHSPSet **hsp_array, Int4 size, Int4 *qend_index_array, Uint4 queryId, Int4 offset)
 Find an HSP in an array sorted in increasing order of query offsets and increasing order of queryId, with the smallest index such that its query end is >= to a given offset. More...
 
static BlastLinkedHSPSet ** s_MergeLinkedHSPSets (BlastLinkedHSPSet *hsp_set1, BlastLinkedHSPSet *hsp_set2, Int4 *merged_size)
 Merges HSPs from two linked HSP sets into an array of HSPs, sorted in increasing order of contexts and increasing order of query offsets. More...
 
static BlastLinkedHSPSets_CombineLinkedHSPSets (BlastLinkedHSPSet *hsp_set1, BlastLinkedHSPSet *hsp_set2, double sum_score, double evalue)
 Combines two linked sets of HSPs into a single set. More...
 
static Boolean s_LinkedHSPSetsAdmissible (BlastLinkedHSPSet *hsp_set1, BlastLinkedHSPSet *hsp_set2, const BlastLinkHSPParameters *link_hsp_params, EBlastProgramType program)
 Checks if new candidate HSP is admissible to be linked to a set of HSPs on the left. More...
 
static BlastLinkedHSPSet ** s_LinkedHSPSetArraySetUp (BlastHSP **hsp_array, Int4 hspcnt, Blast_KarlinBlk **kbp_array, EBlastProgramType program)
 Sets up an array of wrapper structures for an array of BlastHSP's. More...
 
static BlastLinkedHSPSet ** s_LinkedHSPSetArrayCleanUp (BlastLinkedHSPSet **link_hsp_array, Int4 hspcnt)
 Frees the array of special structures, used for linking HSPs and restores the original contexts and subject/query order in BlastHSP structures, when necessary. More...
 
static Int2 s_LinkedHSPSetArrayIndexQueryEnds (BlastLinkedHSPSet **hsp_array, Int4 hspcnt, Int4 **qend_index_ptr)
 Given an array of HSPs (H), sorted in increasing order of query offsets, fills an array of indices into array H such that for each i, the index is the smallest HSP index, for which query ending offset is >= than query ending offset of H[i]. More...
 
static Int2 s_BlastUnevenGapLinkHSPs (EBlastProgramType program, BlastHSPList *hsp_list, const BlastQueryInfo *query_info, Int4 subject_length, const BlastScoreBlk *sbp, const BlastLinkHSPParameters *link_hsp_params, Boolean gapped_calculation)
 Greedy algorithm to link HSPs with uneven gaps. More...
 
Int2 BLAST_LinkHsps (EBlastProgramType program_number, BlastHSPList *hsp_list, const BlastQueryInfo *query_info, Int4 subject_length, const BlastScoreBlk *sbp, const BlastLinkHSPParameters *link_hsp_params, Boolean gapped_calculation)
 Link HSPs using sum statistics. More...
 

Detailed Description

Functions to link with use of sum statistics.

Definition in file link_hsps.c.

Typedef Documentation

◆ BlastHSPLink

typedef struct BlastHSPLink BlastHSPLink

The following structure is used in "link_hsps" to decide between two different "gapping" models.

Here link is used to hook up a chain of HSP's, num is the number of links, and sum is the sum score. Once the best gapping model has been found, this information is transferred up to the LinkHSPStruct. This structure should not be used outside of the function Blast_EvenGapLinkHSPs.

◆ BlastLinkedHSPSet

Simple doubly linked list of HSPs, used for calculating sum statistics.

◆ ELinkOrderingMethod

Describes the method for ordering HSPs.

Note that these values are used to index an array, so their values must linearly increase

◆ LinkHelpStruct

The helper array contains the info used frequently in the inner for loops of the HSP linking algorithm.

One array of helpers will be allocated for each thread.

◆ LinkHSPStruct

typedef struct LinkHSPStruct LinkHSPStruct

Structure containing all information internal to the process of linking HSPs.

Enumeration Type Documentation

◆ ELinkOrderingMethod

Describes the method for ordering HSPs.

Note that these values are used to index an array, so their values must linearly increase

Enumerator
eLinkSmallGaps 

favor small gaps when linking an HSP

eLinkLargeGaps 

favor large gaps when linking an HSP

eOrderingMethods 

number of methods (last in list)

Definition at line 47 of file link_hsps.c.

Function Documentation

◆ BLAST_LinkHsps()

Int2 BLAST_LinkHsps ( EBlastProgramType  program_number,
BlastHSPList hsp_list,
const BlastQueryInfo query_info,
Int4  subject_length,
const BlastScoreBlk sbp,
const BlastLinkHSPParameters link_hsp_params,
Boolean  gapped_calculation 
)

Link HSPs using sum statistics.

Parameters
program_numberBLAST program [in]
hsp_listList of HSPs [in]
query_infoQuery information block [in]
subject_lengthSubject sequence length [in]
sbpScoring and statistical data [in]
link_hsp_paramsParameters for linking of HSPs [in]
gapped_calculationIs this a gapped search? [in]

Definition at line 1761 of file link_hsps.c.

References ASSERT, BlastHSPList::best_evalue, Blast_HSPListAdjustOddBlastnScores(), Blast_HSPListGetEvalues(), Blast_HSPListSortByScore(), Blast_SubjectIsTranslated(), CODON_LENGTH, BlastHSP::evalue, FALSE, BlastLinkHSPParameters::gap_decay_rate, BlastHSPList::hsp_array, BlastHSPList::hspcnt, if(), BlastLinkHSPParameters::longest_intron, BlastHSP::num, s_BlastEvenGapLinkHSPs(), and s_BlastUnevenGapLinkHSPs().

Referenced by BLAST_PreliminarySearchEngine(), BOOST_AUTO_TEST_CASE(), s_BlastSearchEngineCore(), s_HitlistEvaluateAndPurge(), s_HSPListPostTracebackUpdate(), and LinkHspTestFixture::testUnevenGapLinkHsps().

◆ s_BlastEvenGapLinkHSPs()

static Int2 s_BlastEvenGapLinkHSPs ( EBlastProgramType  program_number,
BlastHSPList hsp_list,
const BlastQueryInfo query_info,
Int4  subject_length,
const BlastScoreBlk sbp,
const BlastLinkHSPParameters link_hsp_params,
Boolean  gapped_calculation 
)
static

Perform even gap linking on a list of HSPs.

Parameters
program_numberThe blast program that generated the HSPs [in]
hsp_listList of HSPs to link [in/modified]
query_infoList of structures describing all query sequences [in]
subject_lengthNumber of letters in the subject sequence [in]
sbpScore block [in]
link_hsp_paramsConfiguration information for the linking process [in]
gapped_calculationTRUE if the HSPs are from a gapped search [in]
Returns
0 if linking succeeded, nonzero otherwise

Definition at line 415 of file link_hsps.c.

References BLAST_GapDecayDivisor(), BLAST_LargeGapSumE(), Blast_QueryIsNucleotide(), Blast_QueryIsTranslated(), BLAST_SmallGapSumE(), Blast_SubjectIsTranslated(), calloc(), BlastHSPLink::changed, CODON_LENGTH, BlastHSP::context, BlastQueryInfo::contexts, BlastLinkHSPParameters::cutoff_big_gap, BlastLinkHSPParameters::cutoff_small_gap, BlastContextInfo::eff_searchsp, eLinkLargeGaps, eLinkSmallGaps, BlastSeg::end, eOrderingMethods, BlastHSP::evalue, FALSE, BlastLinkHSPParameters::gap_decay_rate, BlastLinkHSPParameters::gap_prob, BlastLinkHSPParameters::gap_size, H, LinkHSPStruct::hsp, BlastHSPList::hsp_array, LinkHSPStruct::hsp_link, BlastHSPList::hspcnt, i, if(), INT4_MAX, BlastScoreBlk::kbp, BlastScoreBlk::kbp_gap, Blast_KarlinBlk::Lambda, BlastContextInfo::length_adjustment, LinkHSPStruct::linked_set, LinkHSPStruct::linked_to, Blast_KarlinBlk::logK, malloc(), MAX, max(), LinkHelpStruct::maxsum1, MIN, next(), LinkHSPStruct::next, LinkHelpStruct::next_larger, NULL, BlastHSPLink::num, BlastQueryInfo::num_queries, NUM_STRANDS, BlastSeg::offset, BlastLinkHSPParameters::overlap_size, prev(), LinkHSPStruct::prev, prob(), LinkHelpStruct::ptr, LinkHelpStruct::q_off_trim, BlastHSP::query, BlastContextInfo::query_length, s_FwdCompareHSPs(), s_FwdCompareHSPsTransl(), s_LinkHSPStructReset(), LinkHelpStruct::s_off_trim, s_RevCompareHSPs(), s_RevCompareHSPsTbn(), s_RevCompareHSPsTbx(), s_RevCompareHSPsTransl(), sfree, SIGN, LinkHSPStruct::start_of_chain, BlastHSP::subject, BlastHSPLink::sum, LinkHelpStruct::sum, TRUE, window_size, and BlastHSPLink::xsum.

Referenced by BLAST_LinkHsps().

◆ s_BlastUnevenGapLinkHSPs()

static Int2 s_BlastUnevenGapLinkHSPs ( EBlastProgramType  program,
BlastHSPList hsp_list,
const BlastQueryInfo query_info,
Int4  subject_length,
const BlastScoreBlk sbp,
const BlastLinkHSPParameters link_hsp_params,
Boolean  gapped_calculation 
)
static

Greedy algorithm to link HSPs with uneven gaps.

Sorts HSPs by score. Starting with the highest scoring HSP, finds an HSP that produces the best sum e-value when added to the HSP set under consideration. The neighboring HSPs in a set must have endpoints within a window of each other on the protein axis, and within the longest allowed intron length on the nucleotide axis. When no more HSPs can be added to the highest scoring set, the next highest scoring HSP is considered that is not yet part of any set.

Parameters
programType of BLAST program (blastx or tblastn) [in]
hsp_listStructure containing all HSPs for a given subject [in] [out]
query_infoQuery information, including effective lengths [in]
subject_lengthSubject sequence length [in]
sbpScoring and statistical parameters [in]
link_hsp_paramsParameters for linking HSPs [in]
gapped_calculationTRUE if input HSPs are from a gapped search [in]

Definition at line 1613 of file link_hsps.c.

References eBlastTypeBlastx, BlastSeg::end, BlastHSP::evalue, BlastLinkHSPParameters::gap_size, BlastLinkedHSPSet::hsp, BlastHSPList::hsp_array, BlastHSPList::hspcnt, BlastScoreBlk::kbp, BlastScoreBlk::kbp_gap, BlastLinkHSPParameters::longest_intron, malloc(), MIN, next(), BlastLinkedHSPSet::next, NULL, BlastSeg::offset, prev(), BlastLinkedHSPSet::prev, BlastHSP::query, BlastLinkedHSPSet::queryId, s_CombineLinkedHSPSets(), s_FwdCompareLinkedHSPSets(), s_HSPOffsetBinarySearch(), s_HSPOffsetEndBinarySearch(), s_LinkedHSPSetArrayCleanUp(), s_LinkedHSPSetArrayIndexQueryEnds(), s_LinkedHSPSetArraySetUp(), s_LinkedHSPSetsAdmissible(), s_SumHSPEvalue(), s_SumScoreCompareLinkedHSPSets(), sfree, and BlastLinkedHSPSet::sum_score.

Referenced by BLAST_LinkHsps().

◆ s_CombineLinkedHSPSets()

static BlastLinkedHSPSet* s_CombineLinkedHSPSets ( BlastLinkedHSPSet hsp_set1,
BlastLinkedHSPSet hsp_set2,
double  sum_score,
double  evalue 
)
static

Combines two linked sets of HSPs into a single set.

Parameters
hsp_set1First set of HSPs [in]
hsp_set2Second set of HSPs [in]
sum_scoreThe sum score of the combined linked set
evalueThe E-value of the combined linked set
Returns
Combined linked set.

Definition at line 1359 of file link_hsps.c.

References BlastHSP::evalue, BlastLinkedHSPSet::hsp, BlastLinkedHSPSet::next, NULL, BlastHSP::num, BlastLinkedHSPSet::prev, s_MergeLinkedHSPSets(), sfree, and BlastLinkedHSPSet::sum_score.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_FwdCompareHSPs()

static int s_FwdCompareHSPs ( const void *  v1,
const void *  v2 
)
static

Callback used by qsort to sort a list of HSPs, encapsulated in LinkHSPStruct structures, in order of increasing query start offset.

The subject start offset of HSPs is used as a tiebreaker, and no HSPs may be NULL.

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 120 of file link_hsps.c.

References BlastHSP::context, BlastSeg::offset, BlastHSP::query, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_FwdCompareHSPsTransl()

static int s_FwdCompareHSPsTransl ( const void *  v1,
const void *  v2 
)
static

Like s_FwdCompareHSPs, except with additional logic to distinguish HSPs that lie within different strands of a single translated query sequence.

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 157 of file link_hsps.c.

References BlastHSP::context, NUM_FRAMES, BlastSeg::offset, BlastHSP::query, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_FwdCompareLinkedHSPSets()

static int s_FwdCompareLinkedHSPSets ( const void *  v1,
const void *  v2 
)
static

Callback for sorting an array of HSPs, encapsulated in BlastLinkedHSPSet structures, in order of increasing query starting offset.

The subject end offset of HSPs is used as a tiebreaker, and no HSPs may be NULL. The comparison is applied only to HSPs from the same context. Otherwise, the sorting is in increasing order of contexts.

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 1170 of file link_hsps.c.

References if(), BlastSeg::offset, BlastHSP::query, BlastHSP::subject, and v2.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_HSPOffsetBinarySearch()

static Int4 s_HSPOffsetBinarySearch ( BlastLinkedHSPSet **  hsp_array,
Int4  size,
Uint4  queryId,
Int4  offset 
)
static

Find an HSP on the same queryId as the one given, with closest start offset that is greater than a specified value.

The list of HSPs to search must be sorted by query offset and in increasing order of queryId.

Parameters
hsp_arrayList of pointers to HSPs, encapsulated within BlastLinkedHSPSet structures [in]
sizeNumber of elements in the array [in]
queryIdContext of the target HSP [in]
offsetThe target offset to search for [in]
Returns
The index in the array of the HSP whose start/end offset is closest to but >= the value 'offset'

Definition at line 1242 of file link_hsps.c.

References BlastLinkedHSPSet::hsp, BlastSeg::offset, offset, BlastHSP::query, BlastLinkedHSPSet::queryId, and ncbi::grid::netcache::search::fields::size.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_HSPOffsetEndBinarySearch()

static Int4 s_HSPOffsetEndBinarySearch ( BlastLinkedHSPSet **  hsp_array,
Int4  size,
Int4 qend_index_array,
Uint4  queryId,
Int4  offset 
)
static

Find an HSP in an array sorted in increasing order of query offsets and increasing order of queryId, with the smallest index such that its query end is >= to a given offset.

Parameters
hsp_arrayArray of pointers to HSPs, encapsulated within BlastLinkedHSPSet structures. Must be sorted by queryId and query offsets. [in]
sizeNumber of elements in the array [in]
qend_index_arrayArray indexing query ends in the hsp_array [in]
queryIdContext of the target HSP [in]
offsetThe target offset to search for [in]
Returns
The found index in the hsp_array.

Definition at line 1280 of file link_hsps.c.

References BlastSeg::end, BlastLinkedHSPSet::hsp, offset, BlastHSP::query, BlastLinkedHSPSet::queryId, and ncbi::grid::netcache::search::fields::size.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_LinkedHSPSetArrayCleanUp()

static BlastLinkedHSPSet** s_LinkedHSPSetArrayCleanUp ( BlastLinkedHSPSet **  link_hsp_array,
Int4  hspcnt 
)
static

Frees the array of special structures, used for linking HSPs and restores the original contexts and subject/query order in BlastHSP structures, when necessary.

Parameters
link_hsp_arrayArray of wrapper HSP structures, used for linking. [in]
hspcntSize of the array. [in]
Returns
NULL.

Definition at line 1543 of file link_hsps.c.

References NULL, and sfree.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_LinkedHSPSetArrayIndexQueryEnds()

static Int2 s_LinkedHSPSetArrayIndexQueryEnds ( BlastLinkedHSPSet **  hsp_array,
Int4  hspcnt,
Int4 **  qend_index_ptr 
)
static

Given an array of HSPs (H), sorted in increasing order of query offsets, fills an array of indices into array H such that for each i, the index is the smallest HSP index, for which query ending offset is >= than query ending offset of H[i].

This indexing is performed before any of the HSPs in H are linked.

Parameters
hsp_arrayArray of wrapper HSP structures. [in]
hspcntSize of the hsp_array. [in]
qend_index_ptrPointer to an array of special structures indexing the largest query ends in an HSP array sorting by query offset.

Definition at line 1567 of file link_hsps.c.

References calloc(), BlastSeg::end, BlastLinkedHSPSet::hsp, NULL, BlastHSP::query, and BlastLinkedHSPSet::queryId.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_LinkedHSPSetArraySetUp()

static BlastLinkedHSPSet** s_LinkedHSPSetArraySetUp ( BlastHSP **  hsp_array,
Int4  hspcnt,
Blast_KarlinBlk **  kbp_array,
EBlastProgramType  program 
)
static

Sets up an array of wrapper structures for an array of BlastHSP's.

Parameters
hsp_arrayOriginal array of HSP structures. [in]
hspcntSize of hsp_array. [in]
kbp_arrayArray of Karlin blocks - structures containing Karlin-Altschul parameters. [in]
programBLAST program (tblastn or blastx) [in]
Returns
Array of wrapper structures, used for linking HSPs.

Definition at line 1508 of file link_hsps.c.

References calloc(), BlastHSP::context, eBlastTypeBlastx, BlastLinkedHSPSet::hsp, Blast_KarlinBlk::Lambda, Blast_KarlinBlk::logK, malloc(), BlastHSP::num, BlastLinkedHSPSet::queryId, BlastHSP::score, and BlastLinkedHSPSet::sum_score.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_LinkedHSPSetsAdmissible()

static Boolean s_LinkedHSPSetsAdmissible ( BlastLinkedHSPSet hsp_set1,
BlastLinkedHSPSet hsp_set2,
const BlastLinkHSPParameters link_hsp_params,
EBlastProgramType  program 
)
static

Checks if new candidate HSP is admissible to be linked to a set of HSPs on the left.

The new HSP must start strictly before the parent HSP in both query and subject, and its end must lie within an interval from the parent HSP's start, determined by the allowed gap and overlap sizes in query and subject. This function also indicates whether parent is already too far to the right of the candidate HSP, via a boolean pointer.

Parameters
hsp_set1First linked set of HSPs. [in]
hsp_set2Second linked set of HSPs. [in]
link_hsp_paramsParameters for linking HSPs. [in]
programType of BLAST program (blastx or tblastn) [in]
Returns
Do the two sets satisfy the admissibility criteria to form a combined set?

Definition at line 1407 of file link_hsps.c.

References eBlastTypeBlastx, BlastSeg::end, FALSE, BlastSeg::frame, BlastLinkHSPParameters::gap_size, BlastLinkedHSPSet::hsp, BlastLinkHSPParameters::longest_intron, BlastSeg::offset, BlastLinkHSPParameters::overlap_size, BlastLinkedHSPSet::prev, BlastHSP::query, BlastLinkedHSPSet::queryId, s_MergeLinkedHSPSets(), sfree, SIGN, BlastHSP::subject, and TRUE.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_LinkHSPStructReset()

static LinkHSPStruct* s_LinkHSPStructReset ( LinkHSPStruct lhsp)
static

Initialize a LinkHSPStruct.

Parameters
lhspPointer to struct to initialize. If NULL, struct gets allocated and then initialized [in/modified]
Returns
Pointer to initialized struct

Definition at line 384 of file link_hsps.c.

References calloc(), and LinkHSPStruct::hsp.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_MergeLinkedHSPSets()

static BlastLinkedHSPSet** s_MergeLinkedHSPSets ( BlastLinkedHSPSet hsp_set1,
BlastLinkedHSPSet hsp_set2,
Int4 merged_size 
)
static

Merges HSPs from two linked HSP sets into an array of HSPs, sorted in increasing order of contexts and increasing order of query offsets.

Parameters
hsp_set1First linked set. [in]
hsp_set2Second linked set. [in]
merged_sizeThe total number of HSPs in two sets. [out]
Returns
The array of pointers to HSPs representing a merged set.

Definition at line 1314 of file link_hsps.c.

References BlastLinkedHSPSet::hsp, malloc(), BlastLinkedHSPSet::next, BlastHSP::num, BlastSeg::offset, BlastLinkedHSPSet::prev, and BlastHSP::query.

Referenced by s_CombineLinkedHSPSets(), and s_LinkedHSPSetsAdmissible().

◆ s_RevCompareHSPs()

static int s_RevCompareHSPs ( const void *  v1,
const void *  v2 
)
static

Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset.

The subject start offset of HSPs is used as a tiebreaker, and no HSPs may be NULL

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 198 of file link_hsps.c.

References BlastHSP::context, BlastSeg::offset, BlastHSP::query, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_RevCompareHSPsTbn()

static int s_RevCompareHSPsTbn ( const void *  v1,
const void *  v2 
)
static

Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset (suitable for use with tblastn).

HSPs are first separated by frame of a translated subject sequence, and tiebreaking is by decreasing query end offset, then subject start offset, then subject end offset. HSPs may not be NULL

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 277 of file link_hsps.c.

References BlastHSP::context, BlastSeg::end, BlastSeg::frame, BlastSeg::offset, BlastHSP::query, SIGN, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_RevCompareHSPsTbx()

static int s_RevCompareHSPsTbx ( const void *  v1,
const void *  v2 
)
static

Callback used by qsort to sort a list of HSPs (encapsulated in LinkHSPStruct structures) in order of decreasing query start offset (suitable for use with tblastx).

HSPs are first separated by frame of a translated query sequence and then by frame of a translated subject sequence. Tiebreaking is by decreasing query end offset, then subject start offset, then subject end offset. HSPs may not be NULL

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 331 of file link_hsps.c.

References BlastHSP::context, BlastSeg::end, BlastSeg::frame, NUM_FRAMES, BlastSeg::offset, BlastHSP::query, SIGN, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_RevCompareHSPsTransl()

static int s_RevCompareHSPsTransl ( const void *  v1,
const void *  v2 
)
static

Like s_RevCompareHSPs, except with additional logic to distinguish HSPs that lie within different strands of a single translated query sequence.

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 234 of file link_hsps.c.

References BlastHSP::context, NUM_FRAMES, BlastSeg::offset, BlastHSP::query, BlastHSP::subject, and v2.

Referenced by s_BlastEvenGapLinkHSPs().

◆ s_SumHSPEvalue()

static double s_SumHSPEvalue ( EBlastProgramType  program_number,
const BlastQueryInfo query_info,
Int4  subject_length,
const BlastLinkHSPParameters link_hsp_params,
BlastLinkedHSPSet head_hsp,
BlastLinkedHSPSet new_hsp,
double *  sum_score 
)
static

Calculates e-value of a set of HSPs with sum statistics.

Parameters
program_numberType of BLAST program [in]
query_infoQuery information structure [in]
subject_lengthSubject sequence length [in]
link_hsp_paramsParameters for linking HSPs [in]
head_hspSet of HSPs with previously calculated sum score/evalue [in]
new_hspNew HSP candidate to join the set [in]
sum_scoreNormalized score for the collection if HSPs[out]
Returns
E-value of all the HSPs together

Definition at line 1117 of file link_hsps.c.

References ASSERT, BLAST_GapDecayDivisor(), Blast_SubjectIsTranslated(), BLAST_UnevenGapSumE(), BlastHSP::context, context, BlastQueryInfo::contexts, eBlastTypeTblastx, BlastContextInfo::eff_searchsp, BlastLinkHSPParameters::gap_decay_rate, BlastLinkHSPParameters::gap_size, BlastLinkedHSPSet::hsp, BlastContextInfo::length_adjustment, BlastLinkHSPParameters::longest_intron, MAX, BlastHSP::num, BlastLinkHSPParameters::overlap_size, BlastContextInfo::query_length, and BlastLinkedHSPSet::sum_score.

Referenced by s_BlastUnevenGapLinkHSPs().

◆ s_SumScoreCompareLinkedHSPSets()

static int s_SumScoreCompareLinkedHSPSets ( const void *  v1,
const void *  v2 
)
static

Callback used by qsort to sort a list of BlastLinkedHSPSet structures in order of decreasing sum score.

Entries in the list may be NULL

Parameters
v1first HSP in list [in]
v2second HSP in list [in]
Returns
-1, 0, or 1 depending on HSPs

Definition at line 1205 of file link_hsps.c.

References BlastLinkedHSPSet::hsp, ScoreCompareHSPs(), BlastLinkedHSPSet::sum_score, and v2.

Referenced by s_BlastUnevenGapLinkHSPs().

Modified on Fri Sep 20 14:57:01 2024 by modify_doxy.py rev. 669887