blast_hits.h
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:19k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: blast_hits.h,v $
  4.  * PRODUCTION Revision 1000.4  2004/06/01 18:03:32  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.41
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /* $Id: blast_hits.h,v 1000.4 2004/06/01 18:03:32 gouriano Exp $
  10.  * ===========================================================================
  11.  *
  12.  *                            PUBLIC DOMAIN NOTICE
  13.  *               National Center for Biotechnology Information
  14.  *
  15.  *  This software/database is a "United States Government Work" under the
  16.  *  terms of the United States Copyright Act.  It was written as part of
  17.  *  the author's official duties as a United States Government employee and
  18.  *  thus cannot be copyrighted.  This software/database is freely available
  19.  *  to the public for use. The National Library of Medicine and the U.S.
  20.  *  Government have not placed any restriction on its use or reproduction.
  21.  *
  22.  *  Although all reasonable efforts have been taken to ensure the accuracy
  23.  *  and reliability of the software and data, the NLM and the U.S.
  24.  *  Government do not and cannot warrant the performance or results that
  25.  *  may be obtained by using this software or data. The NLM and the U.S.
  26.  *  Government disclaim all warranties, express or implied, including
  27.  *  warranties of performance, merchantability or fitness for any particular
  28.  *  purpose.
  29.  *
  30.  *  Please cite the author in any work or product based on this material.
  31.  *
  32.  * ===========================================================================
  33.  *
  34.  * Author:  Ilya Dondoshansky
  35.  *
  36.  */
  37. /** @file blast_hits.h
  38.  * Structures and API used for saving BLAST hits
  39.  */
  40. #ifndef __BLAST_HITS__
  41. #define __BLAST_HITS__
  42. #ifdef __cplusplus
  43. extern "C" {
  44. #endif
  45. #include <algo/blast/core/blast_options.h>
  46. #include <algo/blast/core/gapinfo.h>
  47. #include <algo/blast/core/blast_seqsrc.h>
  48. /** One sequence segment within an HSP */
  49. typedef struct BlastSeg {
  50.    Int2 frame;  /**< Translation frame */
  51.    Int4 offset; /**< Start of hsp */
  52.    Int4 length; /**< Length of hsp */
  53.    Int4 end;    /**< End of HSP */
  54.    Int4 gapped_start;/**< Where the gapped extension started. */
  55. } BlastSeg;
  56. /** Structure holding all information about an HSP */
  57. typedef struct BlastHSP {
  58.    Int4 score;         /**< This HSP's raw score */
  59.    Int4 num_ident;         /**< Number of identical base pairs in this HSP */
  60.    double evalue;        /**< This HSP's e-value */
  61.    BlastSeg query;            /**< Query sequence info. */
  62.    BlastSeg subject;          /**< Subject sequence info. */
  63.    Int4     context;          /**< Context number of query */
  64.    GapEditBlock* gap_info; /**< ALL gapped alignment is here */
  65.    Int2 splice_junction; /**< Splice junction count in a linked set of
  66.                             HSPs. Each present splice junction counts as +1, 
  67.                             absent as -1. */
  68.    Int4 num;            /**< How many HSP's make up this (sum) segment? */
  69.    Uint4 pattern_length; /**< Length of pattern occurrence in this HSP, in 
  70.                             PHI BLAST */
  71. } BlastHSP;
  72. /** The structure to hold all HSPs for a given sequence after the gapped 
  73.  *  alignment.
  74.  */
  75. typedef struct BlastHSPList {
  76.    Int4 oid;/**< The ordinal id of the subject sequence this HSP list is for */
  77.    BlastHSP** hsp_array; /**< Array of pointers to individual HSPs */
  78.    Int4 hspcnt; /**< Number of HSPs saved */
  79.    Int4 allocated; /**< The allocated size of the hsp_array */
  80.    Int4 hsp_max; /**< The maximal number of HSPs allowed to be saved */
  81.    Boolean do_not_reallocate; /**< Is reallocation of the hsp_array allowed? */
  82.    Boolean traceback_done; /**< Has the traceback already been done on HSPs in
  83.                               this list? */
  84. } BlastHSPList;
  85. /** The structure to contain all BLAST results for one query sequence */
  86. typedef struct BlastHitList {
  87.    Int4 hsplist_count; /**< Filled size of the HSP lists array */
  88.    Int4 hsplist_max; /**< Maximal allowed size of the HSP lists array */
  89.    double worst_evalue; /**< Highest of the best e-values among the HSP 
  90.                            lists */
  91.    Int4 low_score; /**< The lowest of the best scores among the HSP lists */
  92.    Boolean heapified; /**< Is this hit list already heapified? */
  93.    BlastHSPList** hsplist_array; /**< Array of HSP lists for individual
  94.                                           database hits */
  95. } BlastHitList;
  96. /** The structure to contain all BLAST results, for multiple queries */
  97. typedef struct BlastHSPResults {
  98.    Int4 num_queries; /**< Number of query sequences */
  99.    BlastHitList** hitlist_array; /**< Array of results for individual
  100.                                           query sequences */
  101. } BlastHSPResults;
  102. /* By how much should the chunks of a subject sequence overlap if it is 
  103.    too long and has to be split */
  104. #define DBSEQ_CHUNK_OVERLAP 100
  105. /********************************************************************************
  106. The following section has four sets of functions (or "APIs"), manipulating with
  107. the following structures:
  108. 1. BlastHSP, which is the basic unit to record one alignment.  
  109. 2. BlastHSPList, which is a list of BlastHSP's for one database sequence. 
  110. 3. BlastHitList, which contains all HSPList's for a given query. 
  111. 4. BlastHSPResults, which is a list of BlastHitList's for multiple queries.
  112.  The naming conventions for the functions are the following:
  113. 1.) All routines start with "Blast_"
  114. 2.) After "Blast_" comes the structure being manipulated, that should be either 
  115.     HSP (all capitals all the time!), HSPList (exactly this capitalization), 
  116.     HitList (capital H and L, all others lower-case), or HSPResults.
  117. 3.) finally the task being done, e.g., "Free", "New", "Init".
  118. ********************************************************************************/
  119. /********************************************************************************
  120.           HSP API
  121. ********************************************************************************/
  122. /** Deallocate memory for an HSP structure */
  123. BlastHSP* Blast_HSPFree(BlastHSP* hsp);
  124. /** Allocate and zeros out memory for an HSP structure */
  125. BlastHSP* Blast_HSPNew(void);
  126. /** Allocates BlastHSP and inits with information from input.
  127.  * structure
  128.  * @param query_start Start of query alignment [in]
  129.  * @param query_end End of query alignment [in]
  130.  * @param subject_start Start of subject alignment [in]
  131.  * @param subject_end End of subject alignment [in]
  132.  * @param query_gapped_start Where gapped alignment started on query [in]
  133.  * @param subject_gapped_start Where gapped alignment started on subject [in]
  134.  * @param query_context The index of the query containing this HSP [in]
  135.  * @param subject_frame Subject frame: -3..3 for translated sequence, 
  136.  *        1 for blastn, 0 for blastp [in]
  137.  * @param score score of alignment [in]
  138.  * @param gap_edit Will be transferred to HSP and nulled out 
  139.  *    if a traceback was not calculated may be NULL [in] [out]
  140.  * @param ret_hsp allocated and filled in BlastHSP [out]
  141.  */
  142. Int2
  143. Blast_HSPInit(Int4 query_start, Int4 query_end, Int4 subject_start, 
  144.               Int4 subject_end,
  145.               Int4 query_gapped_start, Int4 subject_gapped_start,
  146.               Int4 query_context, Int2 subject_frame, Int4 score,
  147.               GapEditBlock* *gap_edit, BlastHSP** ret_hsp);
  148. /** Modifies the HSP data after the final gapped alignment.
  149.  *   Input includes only data that likely needs modification.
  150.  * @param query_start start of alignment on query [in]
  151.  * @param query_end end of alignment on query [in]
  152.  * @param subject_start start of alignment on subject [in]
  153.  * @param subject_end end of alignment on subject [in]
  154.  * @param program_number Which BLAST program is this done for? [in]
  155.  * @param gap_edit traceback from final gapped alignment [in] [out]
  156.  * @param hsp Original HSP from the preliminary stage [in] [out]
  157.  */
  158. Int2
  159. Blast_HSPReset(Int4 query_start, Int4 query_end, Int4 subject_start, 
  160.                Int4 subject_end, Int4 score, GapEditBlock* *gap_edit, 
  161.                BlastHSP* hsp);
  162. /** Calculate e-value for an HSP found by PHI BLAST.
  163.  * @param hsp An HSP found by PHI BLAST [in]
  164.  * @param sbp Scoring block with statistical parameters [in]
  165.  */
  166. void Blast_HSPPHIGetEvalue(BlastHSP* hsp, BlastScoreBlk* sbp);
  167. /** Reevaluate the HSP's score, e-value and percent identity after taking
  168.  * into account the ambiguity information. Needed for blastn only, either
  169.  * after a greedy gapped extension, or for ungapped search.
  170.  * @param hsp The HSP structure [in] [out]
  171.  * @param query_start Pointer to the start of the query sequence [in]
  172.  * @param subject_start Pointer to the start of the subject sequence [in]
  173.  * @param hit_options Hit saving options with e-value cut-off [in]
  174.  * @param score_params Scoring parameters [in]
  175.  * @param query_info Query information structure, containing effective search
  176.  *                   space(s) [in]
  177.  * @param sbp Score block with Karlin-Altschul parameters [in]
  178.  * @return Should this HSP be deleted after the score reevaluation?
  179.  */
  180. Boolean Blast_HSPReevaluateWithAmbiguities(BlastHSP* hsp, 
  181.            Uint1* query_start, Uint1* subject_start, 
  182.            const BlastHitSavingOptions* hit_options, 
  183.            const BlastScoringParameters* score_params, 
  184.            BlastQueryInfo* query_info, BlastScoreBlk* sbp);
  185. /** Calculate number of identities in an HSP.
  186.  * @param query The query sequence [in]
  187.  * @param subject The uncompressed subject sequence [in]
  188.  * @param hsp All information about the HSP [in]
  189.  * @param is_gapped Is this a gapped search? [in]
  190.  * @param num_ident_ptr Number of identities [out]
  191.  * @param align_length_ptr The alignment length, including gaps [out]
  192.  */
  193. Int2
  194. Blast_HSPGetNumIdentities(Uint1* query, Uint1* subject, BlastHSP* hsp, 
  195.                           Boolean is_gapped, Int4* num_ident_ptr, 
  196.                           Int4* align_length_ptr);
  197. /** Calculate number of identities in an HSP for an out-of-frame alignment.
  198.  * @param query The query sequence [in]
  199.  * @param subject The uncompressed subject sequence [in]
  200.  * @param hsp All information about the HSP [in]
  201.  * @param program BLAST program (blastx or tblastn) [in]
  202.  * @param num_ident_ptr Number of identities [out]
  203.  * @param align_length_ptr The alignment length, including gaps [out]
  204.  */
  205. Int2
  206. Blast_HSPGetOOFNumIdentities(Uint1* query, Uint1* subject, BlastHSP* hsp, 
  207.                              Uint1 program, Int4* num_ident_ptr, 
  208.                              Int4* align_length_ptr);
  209. /********************************************************************************
  210.           HSPList API
  211. ********************************************************************************/
  212. /** Deallocate memory for an HSP list structure 
  213.  *  as well as all it's components.
  214.  * @param hsp_list the BlastHSPList to be freed [in]. 
  215. */
  216. BlastHSPList* Blast_HSPListFree(BlastHSPList* hsp_list);
  217. /** Creates HSP list structure with a default size HSP array 
  218.  * @param hsp_max the maximum number of HSP's that can ever be
  219.  *    saved at once [in].
  220. */
  221. BlastHSPList* Blast_HSPListNew(Int4 hsp_max);
  222. /** Saves HSP information into a BlastHSPList structure
  223.  * @param hsp_list Structure holding all HSPs with full gapped alignment 
  224.  *        information [in] [out]
  225.  * @param new_hsp The new HSP to be inserted into the HSPList [in]
  226. */
  227. Int2
  228. Blast_HSPListSaveHSP(BlastHSPList* hsp_list, BlastHSP* hsp);
  229. /** Assign frames in all HSPs in the HSP list.
  230.  * @param program_number Type of BLAST program [in]
  231.  * @param hsp_list List of HSPs for one subject sequence [in] [out]
  232.  * @param is_ooframe Is out-of-frame gapping used? [in]
  233. */
  234. void 
  235. Blast_HSPListSetFrames(Uint1 program_number, BlastHSPList* hsp_list, 
  236.                  Boolean is_ooframe);
  237. /** Calculate the expected values for all HSPs in a hit list, without using 
  238.  * the sum statistics. In case of multiple queries, the offsets are assumed 
  239.  * to be already adjusted to individual query coordinates, and the contexts 
  240.  * are set for each HSP.
  241.  * @param program The integer BLAST program index [in]
  242.  * @param query_info Auxiliary query information - needed only for effective
  243.  *                   search space calculation if it is not provided [in]
  244.  * @param hsp_list List of HSPs for one subject sequence [in] [out]
  245.  * @param gapped_calculation Is this for a gapped or ungapped search? [in]
  246.  * @param sbp Structure containing statistical information [in]
  247.  */
  248. Int2 Blast_HSPListGetEvalues(Uint1 program, BlastQueryInfo* query_info,
  249.         BlastHSPList* hsp_list, Boolean gapped_calculation, 
  250.         BlastScoreBlk* sbp);
  251. /** Calculate e-values for a PHI BLAST HSP list.
  252.  * @param hsp_list HSP list found by PHI BLAST [in] [out]
  253.  * @param sbp Scoring block with statistical parameters [in]
  254.  */
  255. void Blast_HSPListPHIGetEvalues(BlastHSPList* hsp_list, BlastScoreBlk* sbp);
  256. /** Discard the HSPs above the e-value threshold from the HSP list 
  257.  * @param hsp_list List of HSPs for one subject sequence [in] [out]
  258.  * @param hit_options Options block containing the e-value cut-off [in]
  259. */
  260. Int2 Blast_HSPListReapByEvalue(BlastHSPList* hsp_list, 
  261.                                BlastHitSavingOptions* hit_options);
  262. /** Cleans out the NULLed out HSP's from the HSP array that
  263.  * is part of the BlastHSPList.
  264.  * @param hsp_list Contains array of pointers to HSP structures [in]
  265.  * @return status of function call.
  266. */
  267. Int2
  268. Blast_HSPListPurgeNullHSPs(BlastHSPList* hsp_list);
  269. /** Reevaluate all HSPs in an HSP list, using ambiguity information. 
  270.  * This is/can only done either for an ungapped search, or if traceback is 
  271.  * already available.
  272.  * Subject sequence is uncompressed and saved here. Number of identities is
  273.  * calculated for each HSP along the way. 
  274.  * @param hsp_list The list of HSPs for one subject sequence [in] [out]
  275.  * @param query_blk The query sequence [in]
  276.  * @param subject_blk The subject sequence [in] [out]
  277.  * @param hit_options The options related to saving hits [in]
  278.  * @param query_info Auxiliary query information [in]
  279.  * @param sbp The statistical information [in]
  280.  * @param score_params Parameters related to scoring [in]
  281.  * @param seq_src The BLAST database structure (for retrieving uncompressed
  282.  *             sequence) [in]
  283.  */
  284. Int2 
  285. Blast_HSPListReevaluateWithAmbiguities(BlastHSPList* hsp_list,
  286.    BLAST_SequenceBlk* query_blk, BLAST_SequenceBlk* subject_blk, 
  287.    const BlastHitSavingOptions* hit_options, BlastQueryInfo* query_info, 
  288.    BlastScoreBlk* sbp, const BlastScoringParameters* score_params, 
  289.    const BlastSeqSrc* seq_src);
  290. /** Append one HSP list to the other. Discard lower scoring HSPs if there is
  291.  * not enough space to keep all.
  292.  * @param hsp_list New list of HSPs [in]
  293.  * @param combined_hsp_list_ptr Pointer to the combined list of HSPs, possibly
  294.  *                              containing previously saved HSPs [in] [out]
  295.  * @param hsp_num_max Maximal allowed number of HSPs to save (unlimited if 0) [in]
  296.  * @return Status: 0 on success, -1 on failure.
  297.  */ 
  298. Int2 Blast_HSPListAppend(BlastHSPList* hsp_list, 
  299.                          BlastHSPList** combined_hsp_list_ptr, 
  300.                          Int4 hsp_num_max);
  301. /** Merge an HSP list from a chunk of the subject sequence into a previously
  302.  * computed HSP list.
  303.  * @param hsp_list Contains HSPs from the new chunk [in]
  304.  * @param combined_hsp_list_ptr Contains HSPs from previous chunks [in] [out]
  305.  * @param hsp_num_max Maximal allowed number of HSPs to save (unlimited if 0) [in]
  306.  * @param start Offset where the current subject chunk starts [in]
  307.  * @param merge_hsps Should the overlapping HSPs be merged into one? [in]
  308.  * @return 0 if HSP lists have been merged successfully, -1 otherwise.
  309.  */
  310. Int2 Blast_HSPListsMerge(BlastHSPList* hsp_list, 
  311.                    BlastHSPList** combined_hsp_list_ptr, 
  312.                    Int4 hsp_num_max, Int4 start, Boolean merge_hsps);
  313. /** Adjust subject offsets in an HSP list if only part of the subject sequence
  314.  * was searched. Used when long subject sequence is split into more manageable
  315.  * chunks.
  316.  * @param hsp_list List of HSPs from a chunk of a subject sequence [in]
  317.  * @param offset Offset where the chunk starts [in]
  318.  */
  319. void Blast_HSPListAdjustOffsets(BlastHSPList* hsp_list, Int4 offset);
  320. /********************************************************************************
  321.           HitList API.
  322. ********************************************************************************/
  323. /** Allocate memory for a hit list of a given size.
  324.  * @param hitlist_size Size of the hit list (number of HSP lists) [in]
  325.  */
  326. BlastHitList* Blast_HitListNew(Int4 hitlist_size);
  327. /** Deallocate memory for the hit list */
  328. BlastHitList* Blast_HitListFree(BlastHitList* hitlist);
  329. /** Deallocate memory for every HSP list on BlastHitList,
  330.  *  as well as all their components.
  331.  * @param hitlist contains the BlastHSPList array to be freed [in/out]. 
  332. */
  333. Int2 Blast_HitListHSPListsFree(BlastHitList* hitlist);
  334. /** Insert a new HSP list into the hit list.
  335.  * Before capacity of the hit list is reached, just add to the end;
  336.  * After that, store in a heap, to ensure efficient insertion and deletion.
  337.  * The heap order is reverse, with worst e-value on top, for convenience
  338.  * of deletion.
  339.  * @param hit_list Contains all HSP lists saved so far [in] [out]
  340.  * @param hsp_list A new HSP list to be inserted into the hit list [in]
  341. */
  342. Int2 Blast_HitListUpdate(BlastHitList* hit_list, BlastHSPList* hsp_list);
  343. /********************************************************************************
  344.           HSPResults API.
  345. ********************************************************************************/
  346. /** Initialize the results structure.
  347.  * @param num_queries Number of query sequences to allocate results structure
  348.  *                    for [in]
  349.  * @param results_ptr The allocated structure [out]
  350.  */
  351. Int2 Blast_HSPResultsInit(Int4 num_queries, BlastHSPResults** results_ptr);
  352. /** Deallocate memory for BLAST results */
  353. BlastHSPResults* Blast_HSPResultsFree(BlastHSPResults* results);
  354. /** Sort each hit list in the BLAST results by best e-value */
  355. Int2 Blast_HSPResultsSortByEvalue(BlastHSPResults* results);
  356. /** Blast_HSPResultsSaveHitList
  357.  *  Save the current hit list to appropriate places in the results structure
  358.  * @param program The type of BLAST search [in]
  359.  * @param results The structure holding results for all queries [in] [out]
  360.  * @param hsp_list The results for the current subject sequence; in case of 
  361.  *                 multiple queries, offsets are still in the concatenated 
  362.  *                 sequence coordinates [in]
  363.  * @param hit_parameters The options/parameters related to saving hits [in]
  364.  */
  365. Int2 Blast_HSPResultsSaveHitList(Uint1 program, BlastHSPResults* results, 
  366.         BlastHSPList* hsp_list, BlastHitSavingParameters* hit_parameters);
  367. /** Convert a prelimiary list of HSPs, that are the result of
  368.  * an RPS blast search, to a format compatible with the rest
  369.  * of the blast engine. RPS blast takes a single query and the
  370.  * concatenation of all DB sequences; the DB sequences are the
  371.  * query input to the engine, and the single query is treated as
  372.  * a single subject sequence. This function should be invoked 
  373.  * after BLAST_SearchEngineCore() but before BLAST_RPSTraceback().
  374.  *
  375.  *   BEFORE THIS CALL      AFTER THIS CALL
  376.  *  - many HitLists        - one HitList
  377.  *  - each HitList has     - the HitList has
  378.  *    one HSPList            many HSPLists
  379.  *  - each HSPList has     - each HSPList has its
  380.  *    subject OID zero       own subject OID
  381.  *  - each HSPList has a   - all HSPlists have
  382.  *    different context      context zero
  383.  *
  384.  * @param init_results The input result list [in]
  385.  * @param results The modified results (in new format) [out]
  386.  */
  387. void Blast_HSPResultsRPSUpdate(BlastHSPResults *results,
  388.                                BlastHSPResults *init_results);
  389. #ifdef __cplusplus
  390. }
  391. #endif
  392. #endif /* !__BLAST_HITS__ */