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

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: blast_extend.h,v $
  4.  * PRODUCTION Revision 1000.2  2004/06/01 18:03:26  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.26
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /* $Id: blast_extend.h,v 1000.2 2004/06/01 18:03:26 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_extend.h
  38.  * Structures used for BLAST extension @todo FIXME: elaborate description
  39.  * rename to nt_ungapped.h?
  40.  */
  41. #ifndef __BLAST_EXTEND__
  42. #define __BLAST_EXTEND__
  43. #include <algo/blast/core/blast_def.h>
  44. #include <algo/blast/core/blast_options.h>
  45. #include <algo/blast/core/lookup_wrap.h>
  46. #include <algo/blast/core/blast_diagnostics.h>
  47. #ifdef __cplusplus
  48. extern "C" {
  49. #endif
  50. /** Structure to hold ungapped alignment information */
  51. typedef struct BlastUngappedData {
  52.    Int4 q_start; /**< Start of the ungapped alignment in query */
  53.    Int4 s_start; /**< Start of the ungapped alignment in subject */ 
  54.    Int4 length;  /**< Length of the ungapped alignment */
  55.    Int4 score;   /**< Score of the ungapped alignment */
  56.    Int2 frame;   /**< Needed for translated searches */
  57. } BlastUngappedData;
  58. /** Structure to hold the initial HSP information */
  59. typedef struct BlastInitHSP {
  60.    Int4 q_off; /**< Offset in query */
  61.    Int4 s_off; /**< Offset in subject */
  62.    BlastUngappedData* ungapped_data; /**< Pointer to a structure holding
  63.                                           ungapped alignment information */
  64. } BlastInitHSP;
  65. /** Structure to hold all initial HSPs for a given subject sequence */
  66. typedef struct BlastInitHitList {
  67.    Int4 total; /**< Total number of hits currently saved */
  68.    Int4 allocated; /**< Available size of the offsets array */
  69.    BlastInitHSP* init_hsp_array; /**< Array of offset pairs, possibly with
  70.                                       scores */
  71.    Boolean do_not_reallocate; /**< Can the init_hsp_array be reallocated? */
  72. } BlastInitHitList;
  73. /** Structure for keeping last hit information for a diagonal */
  74. typedef struct DiagStruct {
  75.    Int4 last_hit; /**< Offset of the last hit */
  76.    Int4 diag_level; /**< To what length has this hit been extended so far? */
  77. } DiagStruct;
  78. /** Structure for keeping last hit information for a diagonal on a stack */
  79. typedef struct MB_Stack {
  80.    Int4 diag; /**< This hit's actual diagonal */
  81.    Int4 level; /**< This hit's offset in the subject sequence */
  82.    Int4 length; /**< To what length has this hit been extended so far? */
  83. } MB_Stack;
  84. /** Structure containing parameters needed for initial word extension.
  85.  * Only one copy of this structure is needed, regardless of how many
  86.  * contexts there are.
  87. */
  88. typedef struct BLAST_DiagTable {
  89.    DiagStruct* diag_array;/**< Array to hold latest hits for all diagonals */
  90.    Int4 diag_array_length; /**< Smallest power of 2 longer than query length */
  91.    Int4 diag_mask; /**< Used to mask off everything above
  92.                           min_diag_length (mask = min_diag_length-1). */
  93.    Int4 offset; /**< "offset" added to query and subject position
  94.                    so that "diag_level" and "last_hit" don't have
  95.                    to be zeroed out every time. */
  96.    Int4 window; /**< The "window" size, within which two (or more)
  97.                    hits must be found in order to be extended. */
  98.    Boolean multiple_hits;/**< Used by BlastExtendWordNew to decide whether
  99.                             or not to prepare the structure for multiple-hit
  100.                             type searches. If TRUE, multiple hits are not
  101.                             neccessary, but possible. */
  102.    Int4 actual_window; /**< The actual window used if the multiple
  103.                           hits method was used and a hit was found. */
  104. } BLAST_DiagTable;
  105. typedef struct MB_StackTable {
  106.    Int4 num_stacks; /**< Number of stacks to be used for storing hit offsets
  107.                        by MegaBLAST */
  108.    Int4* stack_index; /**< Current number of elements in each stack */
  109.    Int4* stack_size;  /**< Available memory for each stack */
  110.    MB_Stack** estack; /**< Array of stacks for most recent hits */
  111. } MB_StackTable;
  112.    
  113. /** Structure for keeping initial word extension information */
  114. typedef struct Blast_ExtendWord {
  115.    BLAST_DiagTable* diag_table; /**< Diagonal array and related parameters */
  116.    MB_StackTable* stack_table; /**< Stacks and related parameters */ 
  117. } Blast_ExtendWord;
  118. /** Initializes the word extension structure
  119.  * @param query_length Length of the query sequence [in]
  120.  * @param word_options Options for initial word extension [in]
  121.  * @param subject_length Average length of a subject sequence, used to 
  122.  *                       calculate average search space. [in]
  123.  * @param ewp_ptr Pointer to the word extension structure [out]
  124.  */
  125. Int2 BlastExtendWordNew(Uint4 query_length,
  126.    const BlastInitialWordOptions* word_options,
  127.    Uint4 subject_length, Blast_ExtendWord** ewp_ptr);
  128. /** Allocate memory for the BlastInitHitList structure */
  129. BlastInitHitList* BLAST_InitHitListNew(void);
  130. /** Free the ungapped data substructures and reset initial HSP count to 0 */
  131. void BlastInitHitListReset(BlastInitHitList* init_hitlist);
  132. /** Free memory for the BlastInitList structure */
  133. BlastInitHitList* BLAST_InitHitListFree(BlastInitHitList* init_hitlist);
  134. /** Finds all words for a given subject sequence, satisfying the wordsize and 
  135.  *  discontiguous template conditions, and performs initial (exact match) 
  136.  *  extension.
  137.  * @param subject The subject sequence [in]
  138.  * @param query The query sequence (needed only for the discontiguous word 
  139.  *        case) [in]
  140.  * @param lookup Pointer to the (wrapper) lookup table structure. Only
  141.  *        traditional MegaBlast lookup table supported. [in]
  142.  * @param matrix The scoring matrix [in]
  143.  * @param word_params Parameters for the initial word extension [in]
  144.  * @param ewp Structure needed for initial word information maintenance [in]
  145.  * @param q_offsets pointer to previously-allocated query offset array [in]
  146.  * @param s_offsets pointer to previously-allocated query offset array [in]
  147.  * @param max_hits size of offset arrays [in]
  148.  * @param init_hitlist Structure to hold all hits information. Has to be 
  149.  *        allocated up front [out]
  150.  * @param ungapped_stats Various hit counts. Not filled if NULL [out]
  151.  */
  152. Int2 MB_WordFinder(BLAST_SequenceBlk* subject,
  153.    BLAST_SequenceBlk* query, 
  154.    LookupTableWrap* lookup,
  155.    Int4** matrix, 
  156.    const BlastInitialWordParameters* word_params,
  157.    Blast_ExtendWord* ewp,
  158.    Uint4* q_offsets,
  159.    Uint4* s_offsets,
  160.    Int4 max_hits,
  161.    BlastInitHitList* init_hitlist, 
  162.          BlastUngappedStats* ungapped_stats);
  163. /** Perform ungapped extension of a word hit
  164.  * @param query The query sequence [in]
  165.  * @param subject The subject sequence [in]
  166.  * @param matrix The scoring matrix [in]
  167.  * @param q_off The offset of a word in query [in]
  168.  * @param s_off The offset of a word in subject [in]
  169.  * @param cutoff The minimal score the ungapped alignment must reach [in]
  170.  * @param X The drop-off parameter for the ungapped extension [in]
  171.  * @param ungapped_data The ungapped extension information [out]
  172.  * @return TRUE if ungapped alignment score is below cutoff, indicating that 
  173.  *         this HSP should be deleted.
  174.  */
  175. Boolean
  176. BlastnWordUngappedExtend(BLAST_SequenceBlk* query, 
  177.    BLAST_SequenceBlk* subject, Int4** matrix, 
  178.    Int4 q_off, Int4 s_off, Int4 cutoff, Int4 X, 
  179.    BlastUngappedData** ungapped_data);
  180. /** Finds all initial hits for a given subject sequence, that satisfy the 
  181.  *  wordsize condition, and pass the ungapped extension test.
  182.  * @param subject The subject sequence [in]
  183.  * @param query The query sequence (needed only for the discontiguous word 
  184.  *        case) [in]
  185.  * @param lookup_wrap Pointer to the (wrapper) lookup table structure. Only
  186.  *        traditional BLASTn lookup table supported. [in]
  187.  * @param matrix The scoring matrix [in]
  188.  * @param word_params Parameters for the initial word extension [in]
  189.  * @param ewp Structure needed for initial word information maintenance [in]
  190.  * @param q_offsets pointer to previously-allocated query offset array [in]
  191.  * @param s_offsets pointer to previously-allocated subject offset array [in]
  192.  * @param max_hits size of offset arrays [in]
  193.  * @param init_hitlist Structure to hold all hits information. Has to be 
  194.  *        allocated up front [out]
  195.  * @param ungapped_stats Various hit counts. Not filled if NULL [out]
  196.  */
  197. Int2 BlastNaWordFinder(BLAST_SequenceBlk* subject, 
  198.        BLAST_SequenceBlk* query,
  199.        LookupTableWrap* lookup_wrap,
  200.        Int4** matrix,
  201.        const BlastInitialWordParameters* word_params, 
  202.        Blast_ExtendWord* ewp,
  203.        Uint4* q_offsets,
  204.        Uint4* s_offsets,
  205.        Int4 max_hits,
  206.        BlastInitHitList* init_hitlist, 
  207.              BlastUngappedStats* ungapped_stats);
  208. /** Finds all words for a given subject sequence, satisfying the wordsize and 
  209.  *  discontiguous template conditions, and performs initial (exact match) 
  210.  *  extension.
  211.  * @param subject The subject sequence [in]
  212.  * @param query The query sequence (needed only for the discontiguous word 
  213.  *        case) [in]
  214.  * @param lookup_wrap Pointer to the (wrapper) lookup table structure. Only
  215.  *        traditional BLASTn lookup table supported.[in]
  216.  * @param matrix The scoring matrix [in]
  217.  * @param word_params Parameters for the initial word extension [in]
  218.  * @param ewp Structure needed for initial word information maintenance [in]
  219.  * @param q_offsets pointer to previously-allocated query offset array [in]
  220.  * @param s_offsets pointer to previously-allocated subject offset array [in]
  221.  * @param max_hits size of offset arrays [in]
  222.  * @param init_hitlist Structure to hold all hits information. Has to be 
  223.  *        allocated up front [out]
  224.  * @param ungapped_stats Various hit counts. Not filled if NULL [out]
  225.  */
  226. Int2 BlastNaWordFinder_AG(BLAST_SequenceBlk* subject, 
  227.   BLAST_SequenceBlk* query,
  228.   LookupTableWrap* lookup_wrap,
  229.   Int4** matrix,
  230.   const BlastInitialWordParameters* word_params, 
  231.   Blast_ExtendWord* ewp,
  232.   Uint4* q_offsets,
  233.   Uint4* s_offsets,
  234.   Int4 max_hits,
  235.   BlastInitHitList* init_hitlist, 
  236.            BlastUngappedStats* ungapped_stats);
  237. /** Save the initial hit data into the initial hit list structure.
  238.  * @param init_hitlist the structure holding all the initial hits 
  239.  *        information [in] [out]
  240.  * @param q_off The query sequence offset [in]
  241.  * @param s_off The subject sequence offset [in]
  242.  * @param ungapped_data The information about the ungapped extension of this 
  243.  *        hit [in]
  244.  */
  245. Boolean BLAST_SaveInitialHit(BlastInitHitList* init_hitlist, 
  246.            Int4 q_off, Int4 s_off, BlastUngappedData* ungapped_data); 
  247. /** Deallocate memory for the word extension structure */
  248. Blast_ExtendWord* BlastExtendWordFree(Blast_ExtendWord* ewp);
  249. void 
  250. BlastSaveInitHsp(BlastInitHitList* ungapped_hsps, Int4 q_start, Int4 s_start, 
  251.                  Int4 q_off, Int4 s_off, Int4 len, Int4 score);
  252. #ifdef __cplusplus
  253. }
  254. #endif
  255. #endif /* !__BLAST_EXTEND__ */