/* =========================================================================== * * PUBLIC DOMAIN NOTICE * National Center for Biotechnology Information * * This software/database is a "United States Government Work" under the * terms of the United States Copyright Act. It was written as part of * the author's official duties as a United States Government employee and * thus cannot be copyrighted. This software/database is freely available * to the public for use. The National Library of Medicine and the U.S. * Government have not placed any restriction on its use or reproduction. * * Although all reasonable efforts have been taken to ensure the accuracy * and reliability of the software and data, the NLM and the U.S. * Government do not and cannot warrant the performance or results that * may be obtained by using this software or data. The NLM and the U.S. * Government disclaim all warranties, express or implied, including * warranties of performance, merchantability or fitness for any particular * purpose. * * Please cite the author in any work or product based on this material. * * ===========================================================================*/ /***************************************************************************** File name: blastdef.h Author: Tom Madden Contents: #defines and definitions for structures used by BLAST. ******************************************************************************/ /* $Revision: 6.129 $ * $Log: blastdef.h,v $ * Revision 6.129 2001/12/28 20:38:39 dondosha * Moved Mega BLAST related parameters into a separate structure * * Revision 6.128 2001/12/28 18:01:26 dondosha * Added field scoreThisAlign to SWResults to allow more tie-breaking options * * Revision 6.127 2001/12/14 22:05:40 madden * Changed version and release date * * Revision 6.126 2001/09/11 14:28:31 madden * Added timed_out Boolean to SearchBlk * * Revision 6.125 2001/09/07 14:46:44 dondosha * Roll back removal of threshold_first from functions and structures * * Revision 6.124 2001/09/06 20:24:34 dondosha * Removed threshold_first * * Revision 6.123 2001/08/06 12:50:51 madden * Change release date * * Revision 6.122 2001/07/12 19:50:24 madden * Changed release date * * Revision 6.121 2001/06/28 13:42:09 madden * Fixes to prevent overflow on number of hits reporting * * Revision 6.120 2001/06/12 19:48:56 madden * Introduce total_hsp_limit, check before making SeqAlign * * Revision 6.119 2001/04/13 20:56:08 madden * Updated version to 2.2.1, changed date * * Revision 6.118 2001/04/11 20:56:21 madden * Added scalingFactor for rpsblast, changed release date * * Revision 6.117 2001/03/30 21:58:18 madden * Change release date and version * * Revision 6.116 2001/03/27 21:27:01 madden * Minor efficiency in how lookup table is made * * Revision 6.115 2001/03/19 18:52:57 madden * Add base_offset element to structure for BlastHitRange * * Revision 6.114 2001/02/07 21:05:33 dondosha * Added an output stream to BlastOptionsBlk * * Revision 6.113 2000/12/21 22:28:17 dondosha * Added option and parameter for percent identity cutoff * * Revision 6.112 2000/11/29 16:17:56 dondosha * Added a definition of small structure BLASTHSPSegment * * Revision 6.111 2000/11/14 18:14:00 madden * release date to Nov-13-2000 * * Revision 6.110 2000/11/08 22:18:05 dondosha * Added longest_intron integer option and parameter * * Revision 6.109 2000/11/07 16:30:25 madden * Introduce intermediate score (before linking of HSPs) for blastx and tblastn * * Revision 6.108 2000/11/03 20:16:24 dondosha * Changed one_line_results option and parameter to more meaningful no_traceback * * Revision 6.107 2000/11/01 16:25:56 madden * Changes from Futamura for psitblastn * * Revision 6.106 2000/10/18 19:53:19 shavirin * Empty log message. * * Revision 6.105 2000/10/18 19:17:56 shavirin * Changed BLAST_ENGINE_VERSION and BLAST_RELEASE_DATE * * Revision 6.104 2000/10/05 19:50:49 dondosha * Added mb_result_struct to the BlastSearchBlk to be used instead of result_struct in Mega BLAST * * Revision 6.103 2000/09/28 14:48:20 dondosha * Added exact_match_array to hitlist structure for megablast initial hits * * Revision 6.102 2000/09/21 19:16:30 madden * increase AWAKE_THR_MIN_SIZE by 100 * * Revision 6.101 2000/08/29 19:35:49 madden * Add gilist_not_owned to blast_gi_list * * Revision 6.100 2000/08/08 20:37:21 madden * increase version number to 2.1.1 and release date * * Revision 6.99 2000/07/17 14:05:22 shavirin * Added parameter Out-Of-Frame shift penalty and query DNAP sequence * * Revision 6.98 2000/07/11 18:38:02 madden * decreased size of helper array, added prefetch to BlastGappedScoreInternal * * Revision 6.97 2000/07/11 17:16:20 shavirin * Added new parameter is_ooframe for Out-Of-Frame gapping algorithm. * * Revision 6.96 2000/07/10 15:41:28 madden * Add typedef for BLAST_HSP_helper * * Revision 6.95 2000/07/07 21:20:07 vakatov * Get all "#include" out of the 'extern "C" { }' scope! * * Revision 6.94 2000/07/06 17:24:55 dondosha * Added option and parameter megablast_full_deflines * * Revision 6.93 2000/06/30 17:52:45 madden * Move AWAKE_THR_MIN_SIZE to blastdef.h * * Revision 6.92 2000/06/29 20:30:03 madden * Update version and date * * Revision 6.91 2000/06/08 20:34:18 madden * add explode_seqids option to show all ids in a defline * * Revision 6.90 2000/05/26 20:04:57 madden * Raise version and date * * Revision 6.89 2000/05/12 19:40:59 dondosha * Added qid_array element to BlastSearchBlk * * Revision 6.88 2000/05/01 19:04:31 shavirin * Changed parameter level in BlastErrorMsg structure from Uint1 to Uint2. * * Revision 6.87 2000/04/21 20:48:05 madden * Change version and date * * Revision 6.86 2000/04/06 14:47:10 madden * Added original_expect_value * * Revision 6.85 2000/04/03 21:20:03 dondosha * Added option and parameter is_neighboring * * Revision 6.84 2000/03/31 19:10:44 dondosha * Changed some names related to MegaBlast * * Revision 6.83 2000/03/13 21:01:24 dondosha * Added boolean option sort_gi_list to options block structure * * Revision 6.82 2000/02/29 18:17:23 shavirin * Variable query_dna_mask changed to query_lcase_mask. * * Revision 6.81 2000/02/18 15:30:36 shavirin * Added parameter query_dna_mask into options and parameters. * * Revision 6.80 2000/02/17 21:23:09 shavirin * Added parameter is_rps_blast. * * Revision 6.79 2000/02/17 19:00:44 shavirin * Removed theCacheSize parameter from everywhere. * * Revision 6.78 2000/02/15 19:06:09 shavirin * Added parameter filter_string into BLAST_ParameterBlk structure. * * Revision 6.77 2000/02/02 18:21:51 madden * Add LinkHelpStruct definition * * Revision 6.76 2000/02/02 16:52:43 dondosha * Added option one_line_results to BLAST_OptionsBlk and BLAST_ParameterBlk * * Revision 6.75 2000/02/01 18:02:22 dondosha * Added greedy alignment option to BLAST_OptionsBlk and query context offsets array to BlastSearchBlk * * Revision 6.74 2000/01/26 22:00:52 madden * Added subject_index field to SWResults * * Revision 6.73 2000/01/20 19:12:00 madden * Change BLAST version and date * * Revision 6.72 2000/01/13 18:10:43 madden * Fix problem with incorrect stat values for blastn and missing hits * * Revision 6.71 2000/01/11 17:02:48 shavirin * Added element theCacheSize into BLAST_OptionsBlk and BLAST_ParameterBlk. * * Revision 6.70 1999/12/31 14:23:19 egorov * Add support for using mixture of real and maks database with gi-list files: * 1. Change logic of creating rdfp list. * 2. BlastGetDbChunk gets real databases first, then masks. * 3. Propoper calculation of database sizes using alias files. * 4. Change to CommonIndex to support using of mask databases. * 5. Use correct gis in formated output (BlastGetAllowedGis()). * 6. Other small changes * * Revision 6.69 1999/12/21 20:04:15 egorov * gi_list now contains start position for corresponding database * * Revision 6.68 1999/11/30 18:23:08 shavirin * Added parameter max_num_patterns to the BLAST_OptionsBlkPtr structure * * Revision 6.67 1999/11/15 22:03:31 madden * added Boolean isFirstAlignment to SWResults * * Revision 6.66 1999/11/12 20:57:39 shavirin * Added parameter use_best_align into BLAST_ParameterBlkPtr * * Revision 6.65 1999/11/12 16:37:30 shavirin * Added new option use_best_align into Blast options. * * Revision 6.64 1999/10/26 20:45:19 madden * Add use_real_db_size option * * Revision 6.63 1999/10/05 17:42:54 shavirin * Removed global variables from blast.c * * Revision 6.62 1999/09/28 20:14:31 madden * Joerg changes to mimize cache misses * * Revision 6.61 1999/08/31 13:42:23 madden * Moved SWResults to blastdef.h from profiles.h * * Revision 6.60 1999/08/27 18:07:33 shavirin * Passed parameter decline_align from top to the engine. * * Revision 6.59 1999/08/26 14:56:49 madden * Raise version and date * * Revision 6.58 1999/08/26 14:55:16 madden * Fixed Int8 problem * * Revision 6.57 1999/08/20 19:47:41 madden * removed version element * * Revision 6.56 1999/08/17 18:37:12 shavirin * Added phi_pattern element into options block. * * Revision 6.55 1999/08/17 14:02:34 madden * add smith_waterman and tweak_parameters fields to Options * * Revision 6.54 1999/05/10 18:47:52 madden * Changed version to 2.0.9 * * Revision 6.53 1999/05/08 15:04:24 madden * Changed version and release date * * Revision 6.52 1999/04/23 19:25:01 madden * Fixes a prototype complaint * * Revision 6.51 1999/04/23 16:45:54 madden * call BQ_IncSemaphore as callback * * Revision 6.50 1999/04/22 16:46:13 shavirin * Added semaphore ID to the search_blk structure. * * Revision 6.49 1999/04/01 21:42:47 madden * Fix memory leaks when gi list is used * * Revision 6.48 1999/03/18 21:13:32 egorov * The "output" filed added to search block. This is VoidPtr and an application can * use it as stream, ASNIO, etc to output blast results. * * Revision 6.47 1999/03/17 16:49:11 madden * Removed comment within comment * * Revision 6.46 1999/02/17 13:23:01 madden * Added hsp_num_max * * Revision 6.45 1999/01/28 16:04:56 madden * do_not_reallocate Boolean for HSPs * * Revision 6.44 1999/01/26 17:56:37 madden * query_id added to HitRange * * Revision 6.43 1999/01/05 13:57:19 madden * Changed version and release date * * Revision 6.42 1998/12/31 18:17:03 madden * Added strand option * * Revision 6.41 1998/12/29 17:45:06 madden * Add do_sum_stats flag * * Revision 6.40 1998/12/21 13:09:53 madden * Changed version and release date * * Revision 6.39 1998/11/04 01:36:05 egorov * Add support for entrez-query and org-name to blast3 * * Revision 6.38 1998/09/16 18:58:57 madden * Changed release number and date * * Revision 6.37 1998/09/14 15:11:15 egorov * Add support for Int8 length databases; remove unused variables * * Revision 6.36 1998/07/30 19:00:32 madden * Change to allow search of subset of database * * Revision 6.35 1998/07/28 21:17:59 madden * Added do_not_reevaluate * * Revision 6.34 1998/07/25 14:26:38 madden * Added comments * * Revision 6.33 1998/07/22 12:16:25 madden * Added handle_results * * Revision 6.32 1998/07/21 20:58:04 madden * Changes to allow masking at hash only * * Revision 6.31 1998/07/17 15:39:56 madden * Changes for Effective search space. * * Revision 6.30 1998/07/14 20:17:05 egorov * Add two new parameters (gilist and gifile) to BLAST_OptionsBlk * * Revision 6.29 1998/06/17 18:10:07 madden * Added isPatternSearch to Options * * Revision 6.28 1998/06/12 16:08:49 madden * BlastHitRange stuff * * Revision 6.27 1998/05/28 19:59:16 madden * Added typedef for BLASTHeapStruct * * Revision 6.26 1998/05/17 16:28:43 madden * Allow changes to filter options and cc filtering. * * Revision 6.25 1998/05/05 13:56:38 madden * Raised version to 2.0.5 and changed date * * Revision 6.24 1998/04/24 19:27:05 madden * Added BlastMatrixRescalePtr * * Revision 6.23 1998/04/01 22:47:14 madden * Added query_invalid flag * * Revision 6.22 1998/03/24 15:38:22 madden * Use BlastDoubleInt4Ptr to keep track of gis and ordinal_ids * * Revision 6.21 1998/03/18 14:14:20 madden * Support random access by gi list * * Revision 6.20 1998/03/14 18:29:21 madden * Added BlastSeqIdListPtr * * Revision 6.19 1998/02/26 22:34:37 madden * Changes for 16 bit windows * * Revision 6.18 1998/02/26 19:10:37 madden * Removed elements with BLAST_COLLECT_SPECIAL_STATS defines * * Revision 6.17 1998/02/24 22:46:29 madden * Added perform_culling Boolean and changed release date * * Revision 6.16 1998/02/19 17:17:10 madden * Use of Int4 rather than Int2 when pruning SeqAlign * * Revision 6.15 1998/01/05 16:46:52 madden * One or both strands can be searched, as opposed to only both, changes to number of contexts * * Revision 6.14 1997/12/23 19:14:14 madden * release version to 2.0.4 * * Revision 6.13 1997/12/23 18:12:32 madden * Changes for range-dependent blast * * Revision 6.12 1997/12/12 20:38:02 madden * Fix to comments * * Revision 6.11 1997/12/11 22:20:16 madden * Corrected blast_type defines * * Revision 6.10 1997/12/10 22:41:40 madden * program number defines * * Revision 6.9 1997/11/14 21:30:16 madden * Changed version and date * * Revision 6.8 1997/10/26 17:26:59 madden * Changes for range dependent limits * * Revision 6.7 1997/10/01 13:35:28 madden * Changed BLAST_VERSION to BLAST_ENGINE_VERSION * * Revision 6.6 1997/09/22 17:36:24 madden * MACROS for position-specific matrices from Andy Neuwald * * Revision 6.5 1997/09/18 22:22:12 madden * Added prune functions * * Revision 6.4 1997/09/11 18:49:26 madden * Changes to enable searches against multiple databases. * * Revision 6.3 1997/09/10 21:27:57 madden * Changes to set CPU limits * * Revision 6.2 1997/09/03 19:06:35 madden * changed BLAST_VERSION and BLAST_RELEASE_DATE * * Revision 6.1 1997/08/27 14:46:48 madden * Changes to enable multiple DB searches * * Revision 6.0 1997/08/25 18:52:32 madden * Revision changed to 6.0 * * Revision 1.63 1997/08/20 21:43:10 madden * Updated release date * * Revision 1.62 1997/07/21 17:37:15 madden * Added define for BLAST_RELEASE_DATE * * Revision 1.61 1997/07/18 20:55:45 madden * Added BLAST_VERSION * * Revision 1.60 1997/07/15 20:36:43 madden * Added ValNodePtr mask * * Revision 1.59 1997/07/14 15:33:00 madden * typedef for BlastErrorMsg * * Revision 1.58 1997/05/22 21:24:52 madden * Added support for final gapX dropoff value * * Revision 1.57 1997/05/20 17:51:33 madden * Added element SeqLocPtr query_slp to BlastSearch * * Revision 1.56 1997/05/06 22:19:35 madden * Added use_large_gaps and subject_length * * Revision 1.55 1997/04/09 20:01:53 madden * Added seqid_list to SearchBlk * * Revision 1.54 1997/04/03 19:48:13 madden * Changes to use effective database length instead of the length of each * sequence in statistical calculations. * * Revision 1.53 1997/03/31 17:07:57 madden * Added BLAST_COLLECT_STATS define. * * Revision 1.52 1997/03/20 22:56:24 madden * Added gap_info to hsp. * * Revision 1.51 1997/03/14 22:06:11 madden * fixed MT bug in BlastReevaluateWithAmbiguities. * * Revision 1.50 1997/03/08 16:52:16 madden * y * Added discontinuous option to ParameterBlk. * * Revision 1.49 1997/02/25 19:17:05 madden * Added discontinuous flag to options. * * Revision 1.48 1997/02/23 16:44:47 madden * GapAlignBlkPtr added to search structure. * * Revision 1.47 1997/02/20 18:38:34 madden * Added Int4 db_length to Options block. * * Revision 1.46 1997/02/18 21:03:00 madden * Added #define FILTER_NONE 0. * * Revision 1.45 1997/02/17 17:40:18 madden * Added seqalign to ResultHitlistptr * * Revision 1.44 1997/02/11 19:30:54 madden * Added program_name to Options. * * Revision 1.43 1997/02/10 20:27:01 madden * Changed some CharPtr's into Uint1Ptr's. * * Revision 1.42 1997/02/10 20:14:23 madden * replaced doubles by Nlm_FloatHi's. * * Revision 1.41 1997/02/10 20:03:58 madden * Added specific to BlastAllWordsPtr. * * Revision 1.40 1997/02/10 15:36:40 madden * added posConverged to the BlastSearchBlk. * * Revision 1.39 1997/02/06 14:27:15 madden * Addition of BlastAllWord structure. * * Revision 1.38 1997/02/03 13:02:12 madden * Added length to BLASTSubjectInfo. * * Revision 1.37 1997/01/17 17:41:44 madden * Added flags for position based BLAST. * * Revision 1.36 1997/01/13 15:37:05 madden * Changed prototypes for star_callback and tick_callback. * * Revision 1.35 1997/01/11 18:22:10 madden * Changes to allow S2 to be set. * * Revision 1.34 1997/01/09 17:44:35 madden * Added "bit_score" to BLASTResultHsp. * * Revision 1.33 1996/12/27 20:44:10 madden * Chnages to require that part of the query be included. * * Revision 1.32 1996/12/23 14:04:44 madden * Added gap_trigger. * * Revision 1.31 1996/12/20 21:11:40 madden * Changes to allow multiple hits runs only. * * Revision 1.30 1996/12/18 14:33:13 madden * Added high_score element. * * Revision 1.29 1996/12/17 17:27:03 madden * Count number of attempted gappings. * * Revision 1.28 1996/12/17 13:47:57 madden * Added star_proc. * * Revision 1.27 1996/12/16 14:35:48 madden * Added gapped_calculation Boolean * * Revision 1.26 1996/12/13 22:00:23 madden * Corrected starting point for gapped extension with traceback. * * Revision 1.25 1996/12/13 18:13:56 madden * Added tick callback functions * * Revision 1.24 1996/12/13 15:09:31 madden * Changes to parameters used for gapped extensions. * * Revision 1.23 1996/12/09 23:24:05 madden * Added parameters to control which sequences get a gapped alignment. * * Revision 1.22 1996/12/08 15:19:59 madden * Added parameters for gapped alignments. * * Revision 1.21 1996/11/27 21:56:57 madden * Removed define for XNU. * * Revision 1.20 1996/11/18 18:07:57 madden * *** empty log message *** * * Revision 1.19 1996/11/18 17:28:13 madden * Added BLAST_SEARCH_ALLOC_TRANS_INFO define. * * Revision 1.18 1996/11/18 15:45:40 madden * Defines for filter type added (by S. Shavirin),. * * Revision 1.17 1996/11/15 17:54:54 madden * Added support for alternate genetic codes for blastx, tblast[nx]. * * Revision 1.16 1996/11/13 22:35:18 madden * Added genetic_code and db_genetic_code elements to blastdef.h * * Revision 1.15 1996/11/12 16:21:53 madden * Added context_factor * * Revision 1.14 1996/11/06 22:10:01 madden * translation_buffer changed from CharPtr to Uint1Ptr. * * Revision 1.13 1996/11/04 16:59:43 madden * Added translation_table and translation_table_rc elements * to BlastSearchBlk. * * Revision 1.12 1996/10/03 20:49:29 madden * Added xsum member to HSP_Link structure. * ,. * * Revision 1.11 1996/10/01 21:24:02 madden * Added e2. * * Revision 1.10 1996/09/26 13:02:32 madden * Removed ifdef for BLAST_COLLECT_STATS with counters. * * Revision 1.9 1996/09/12 21:13:46 madden * *** empty log message *** * * Revision 1.8 1996/09/11 22:21:51 madden * *** empty log message *** * * Revision 1.7 1996/09/11 19:14:09 madden * Added BLAST_OptionsBlkPtr structure and use thereof. * * Revision 1.6 1996/08/14 18:16:13 madden * removed frame from Context. * * Revision 1.5 1996/08/14 17:19:02 madden * Added frame to BlastSeqBlkPtr. * * Revision 1.4 1996/08/13 15:26:29 madden * Changes for tblastn. * * Revision 1.3 1996/08/09 22:11:12 madden * Added original_sequence to BlastSequenceBlk. * * Revision 1.2 1996/08/07 14:24:42 madden * Removed include for blast18p.h and objblst2.h * * Revision 1.1 1996/08/05 20:32:18 madden * Initial revision * * Revision 1.51 1996/08/02 14:20:06 madden * Removed multiproc strucutre. * * Revision 1.50 1996/07/31 13:09:17 madden * Changes for threaded blast. * * Revision 1.49 1996/07/24 12:01:28 madden * Changes for blastx * * Revision 1.48 1996/07/18 22:00:49 madden * Addition of BLAST_ExtendWordParams structure. * * Revision 1.47 1996/07/18 13:36:34 madden * Addition of the BLASTContextStructPtr. * * Revision 1.46 1996/07/16 14:37:42 madden * Removed _blast_link_structure . * * Revision 1.45 1996/07/11 16:03:58 madden * SaveCurrentHitlist keeps track of which set an HSP belongs to. * * Revision 1.44 1996/07/02 14:33:16 madden * Added hspcnt_max. * * Revision 1.43 1996/07/02 12:04:15 madden * HSP's saved on array, rather than linked list. * * Revision 1.42 1996/06/26 19:38:12 madden * Removed ifdef. * * Revision 1.41 1996/06/24 20:26:46 madden * Added dropoff_1st_pass and dropoff_2nd_pass to ParameterBlkPtr. * * Revision 1.40 1996/06/24 17:58:21 madden * Removed X_set parameter, added right and left dropoff's. * * Revision 1.39 1996/06/20 16:15:57 madden * Replaced int's with Int4's. * * Revision 1.38 1996/06/19 14:19:53 madden * Added define for BLASTSubjectInfoPtr. * * Revision 1.37 1996/06/17 19:03:07 madden * Rmoved unused structure. * * Revision 1.36 1996/06/14 17:58:13 madden * Changes to avoid nulling out arrays for every sequence. * * Revision 1.35 1996/06/13 21:03:06 madden * Added actual_window element to ExtendWord structure. * * Revision 1.34 1996/06/11 17:58:31 madden * Changes to allow shorter arrays for multiple hits type blast. * * Revision 1.33 1996/06/10 16:52:16 madden * Use bit-shifting and masking instead of dividing and remainder. * * Revision 1.32 1996/06/10 13:44:07 madden * Changes to reduce the size of the "already visited" array. * * Revision 1.31 1996/06/06 17:55:16 madden * Added number_of_bits to ParameterBlkPtr. * * Revision 1.30 1996/06/06 13:23:17 madden * Added elements cutoff_big_gap and ignore_small_gaps to ParameterBlkPt. * * Revision 1.29 1996/05/29 12:44:04 madden * Added structure BlastTimeKeeper. * * Revision 1.28 1996/05/28 14:16:32 madden * Added Int4's to collect statistics info. * * Revision 1.27 1996/05/23 21:55:04 madden * Removed unused variable initlen * * Revision 1.26 1996/05/23 21:48:23 madden * Removed unused defines. * * Revision 1.25 1996/05/16 19:51:09 madden * Added documentation block. * * Revision 1.24 1996/05/16 13:29:38 madden * Added defines for contiguous or discontiguous calls. * * Revision 1.23 1996/05/01 15:00:00 madden * Added BlastResults sturcture defs. * * Revision 1.22 1996/04/24 16:17:26 madden * Added new structure, BLAST_Link. * * Revision 1.21 1996/04/24 12:52:48 madden * ID's for sequences simplified. * * Revision 1.20 1996/04/03 19:14:35 madden * Removed defunct HSP ptr's. * * Revision 1.19 1996/03/29 21:27:43 madden * "hitlist" now kept on SeqAlign rather than HitList. * * Revision 1.17 1996/03/27 19:51:53 madden * "current_hitlist" added to Search Structure. * * Revision 1.16 1996/03/26 19:36:59 madden * Added ReadDBFILEPtr to Search structure. * * Revision 1.15 1996/03/25 16:35:18 madden * Added old_stats. * * Revision 1.14 1996/02/28 21:37:43 madden * Added "trim" variables to segments for HSP. * * Revision 1.13 1996/02/06 22:51:13 madden * Added "prelim" to BlastSearch * * Revision 1.12 1996/02/02 19:25:32 madden * Added wfp_first and wfp_second to BlastParameterBlk for first and second pass. * * Revision 1.11 1996/01/29 21:12:07 madden * *** empty log message *** * * Revision 1.10 1996/01/23 16:31:47 madden * e_cutoff changed from BLAST_Score to double in ParameterBlk. * * Revision 1.9 1996/01/17 17:00:40 madden * Added gap parameters to ParameterBlk, dblen to SearchBlk. * * Revision 1.8 1996/01/17 13:45:58 madden * Added gap_prob and gap_decay_rate to ParameterBlk. * * Revision 1.7 1996/01/11 15:17:36 madden * Added process_num to ParameterBlk. * * Revision 1.6 1996/01/08 23:23:55 madden * removed "len" from HSP. * * Revision 1.5 1996/01/06 18:57:47 madden * Added BLAST_HSP_LINK structure. * * Revision 1.4 1995/12/28 21:26:05 madden * *** empty log message *** * * Revision 1.3 1995/12/26 23:04:14 madden * Added parameters to BlastParameterBlk. * * Revision 1.2 1995/12/21 23:10:41 madden * BLAST_Score prototypes moved to blastkar.h. * * Revision 1.1 1995/12/19 22:33:06 madden * Initial revision * * Revision 1.1 1995/12/08 15:48:23 madden * Initial revision * * */ #ifndef __BLASTSTR__ #define __BLASTSTR__ #include #include #include #include #include #include #include #include #ifdef __cplusplus extern "C" { #endif /* the version of BLAST. */ #define BLAST_ENGINE_VERSION "2.2.2" #define BLAST_RELEASE_DATE "Jan-08-2002" /* Defines for program numbers. (Translated in BlastGetProgramNumber). */ #define blast_type_undefined 0 #define blast_type_blastn 1 #define blast_type_blastp 2 #define blast_type_blastx 3 #define blast_type_tblastn 4 #define blast_type_tblastx 5 #define blast_type_psitblastn 6 /* defines for strand_option, determines which strand of query to compare. */ #define BLAST_TOP_STRAND 1 #define BLAST_BOTTOM_STRAND 2 #define BLAST_BOTH_STRAND 3 /* Defines that specify whether or not BLAST should delete some memory, or leave it up to the caller. */ #define BLAST_OWN 0 #define BLAST_NOT_OWN 1 /* Specifies minimum search space size for an awak thread. */ #define AWAKE_THR_MIN_SIZE 2000000000000.0 /******************************************************************** * * define for collecting BLAST stats. * ***********************************************************************/ #define BLAST_COLLECT_STATS /******************************************************************** * * Structure to save timing info. in. Right now this only * works for UNIX. * ********************************************************************/ typedef struct _blast_time_keeper { FloatLo user, /* CPU time in user space of the process. */ system, /* CPU time used by system. */ total; /* total CPU time (i.e., both of the above). */ } BlastTimeKeeper, PNTR BlastTimeKeeperPtr; /***************************************************************** * * Used for pruing SeqALigns that are too big. * ********************************************************************/ typedef struct _blast_prune_hits_from_sap { SeqAlignPtr sap; Int4 original_number, /* how may unique hits were there originally. */ number; /* How many hits on SeqALignPtr above. */ Boolean allocated; /* If FALSE, SeqAlignPtr above does NOT belong to this struc.*/ } BlastPruneSapStruct, PNTR BlastPruneSapStructPtr; /*************************************************************************** Macros added by Andy Neuwald in order to allow easy modification of matrices. ***************************************************************************/ #define MtrxScorePosSearch(S,x,y) ((S)->posMatrix[(x)][(y)]) #define PtrMtrxScorePosSearch(S,x) ((S)->posMatrix[(x)]) /***** #define MtrxScorePosSearchi2(S,x,y) \ ((S)->posMatrix[( (x) %(S)->query_length)][(y)]) #define PtrMtrxScorePosSearch2(S,x) \ ((S)->posMatrix[( (x) %(S)->query_length)]) *****/ /******************************************************************** Defines for discontiguous word hits on 1st and 2nd pass. ********************************************************************/ #define BLAST_NO_PASS_DISCONTIG 0 #define BLAST_1ST_PASS_DISCONTIG 1 #define BLAST_2ND_PASS_DISCONTIG 2 #define BLAST_BOTH_PASS_DISCONTIG 3 #define CODON_LENGTH 3 /* three is always the codon length. */ #define BLAST_SMALL_GAPS 0 #define BLAST_LARGE_GAPS 1 #define MAX_INTRON_LENGTH 4000 #define MAX_DBSEQ_LEN 5000000 /********************************************************************* Filter types definitions *********************************************************************/ #define FILTER_NONE 0 #define FILTER_DUST 1 #define FILTER_SEG 2 /********************************************************************** Structure for the blast options (available to user/programmer). This should be filled in by the "Main" program before blast is called. ***********************************************************************/ typedef struct _blast_optionsblk { Nlm_FloatHi gap_decay_rate, /* decay rate. */ gap_prob; /* Prob of decay. */ Int4 gap_size, /* Small gap size. */ window_size,/* Multiple Hits window size (zero for single hit algorithm) */ threshold_first, /* Threshold for extending hits (preliminary pass), zero if one-pass algorithm is used. */ threshold_second;/* Threshold for extending hits (second pass) */ Nlm_FloatHi expect_value, /* Expectation value (E) */ e2; /* Expect value for a single HSP */ /* These two scores are zero, unless they've been set, then they set the expect_value and e2 above. */ Int4 cutoff_s, /* score corresponds to expect_value above.*/ cutoff_s2; /* score corresponds to e2 above. */ Boolean two_pass_method; /* should two passes be used? */ Boolean multiple_hits_only; /* Only the multiple hits alg. used. */ Int4 hitlist_size; /* How many hits should be returned. */ Nlm_FloatHi number_of_bits; /* Number of bits to initiate 2nd pass (default is used if zero) */ Int4 dropoff_1st_pass, /* dropoff ("X") used for 1st pass. */ dropoff_2nd_pass; /* dropoff ("X") used for 2nd pass. */ Int2 number_of_cpus; /* How many CPU's. */ CharPtr matrix; /* name of matrix to use. */ Boolean old_stats; /* Use old stats (option may disappear later) */ Boolean do_sum_stats; /* Should sum statistics be used? */ Boolean use_large_gaps; /* Use only large gaps for linking HSP's with sum stats. */ Int2 wordsize; /* size of word used to find hits. */ Int2 penalty, reward; /* penalty and reward, only for blastn */ /* The ID numbers from gc.prt are used for the genetic codes. */ Int4 genetic_code, /* genetic code for query (blastx, tblastx) */ db_genetic_code; /* genetic code for db (tblast[nx]). */ Int4 filter; /* filter type 0 mean no filter non-zero value indicate filer type */ CharPtr filter_string; /* String specifying the type of filtering and filter options. */ Boolean gapped_calculation; /* Is a gapped calc. being done? */ /* The next three are used ONLY for gapped alignments. */ Int4 gap_open, /* Cost to open a gap (NO extension). */ gap_extend, /* Cost to extend a gap one letter. */ gap_x_dropoff, /* X-dropoff (in bits) used by Gapped align routine. */ gap_x_dropoff_final; /* X-dropoff (in bits) used by Gapped align routine for FINAL alignment. */ Int4 decline_align; /* Cost for declining alignment */ Nlm_FloatHi gap_trigger; /* Score (in bits) to gap, if an HSP gaps well. */ Boolean discontinuous; /* Should the SeqAlign be discontinuous.*/ /* What region of the query is required for the alignment. If start is zero and end is -1 (the entire query), then these are not checked. */ Int4 required_start, required_end; Int8 db_length; /* database size used for stat. calcul. */ Int4 dbseq_num; /* number of database sequences used for stat. calcul. */ Nlm_FloatHi searchsp_eff; /* Effective search space to be used. */ /* Options for postion based blast. */ Nlm_FloatHi ethresh; Int4 maxNumPasses, pseudoCountConst; CharPtr program_name; /* program name, for reference. */ Int4 cpu_limit; /* timeout total. */ /* Used for region-dependent limits when storing hits. */ Int4 hsp_range_max, /* maximum hits for a range */ block_width; /* width of a block */ Boolean perform_culling; /* Should results be culled at all? */ Boolean isPatternSearch; /* Is this a use of PHI-BLAST?*/ CharPtr gifile; /* name of file containing list of gis on server */ ValNodePtr gilist; /* list of gis specified by client */ Boolean do_not_reevaluate; /* Don't perform BlastReevaluateWithAmbiguities. */ /* These options allow a subset of the database to be examined. IF they are set to zero, then the entire database is examined. */ Int4 first_db_seq, /* 1st sequence in db to be compared. */ final_db_seq; /* Final sequence to be compared. */ CharPtr entrez_query; /* user specified Entrez query to make selection from databases */ CharPtr org_name; /* user specified name of organizm; corresponding .gil file will be used */ Uint1 strand_option; /* BLAST_TOP_STRAND, BLAST_BOTTOM_STRAND, or BLAST_BOTH_STRAND. used by blast[nx] and tblastx */ Int4 hsp_num_max; /* maximum number of HSP's allowed. Zero indicates no limit. */ Boolean tweak_parameters, /* For impala related stuff. */ smith_waterman; CharPtr phi_pattern; /* Pattern for PHI-Blast search */ Boolean use_real_db_size; /* Use real DB size. meant for use if a list of gis' is submitted, but statistics should be based upon the real database. */ Boolean use_best_align; /* option is to use alignments choosen by user in PSM computation API (used in WWW PSI-Blast); */ Int4 max_num_patterns; /* Maximum number of patterns to be used in PHI-Blast search */ Boolean no_check_score; Boolean is_megablast_search; /* Is this a MegaBlast search? */ Boolean no_traceback; /* No traceback in MegaBLAST extension */ Boolean is_rps_blast; /* If this RPS Blast ? */ SeqLocPtr query_lcase_mask; /* Masking of input DNA regions */ Boolean sort_gi_list; /* Should the gi list be sorted? */ Boolean is_neighboring; /* Is this a neighboring task? */ Nlm_FloatHi original_expect_value;/* Used to change the E-value threshold for part of a BLAST-KAPPA run and to restore it to the original threshold for the final output. */ Boolean explode_seqids; /* make one SeqAlign for every gi on a redundant sequence. */ Boolean megablast_full_deflines; /* Print full deflines in megablast one-line output */ Boolean is_ooframe; /* Use Out-Of-Frame gapping algorithm */ Int4 shift_pen; /* Out-Of-Frame shift penalty */ Boolean gilist_already_calculated; /* translation of gis to ordinalID's already done (used for neighboring). */ Boolean recoverCheckpoint; /* For psitblastn */ Boolean freqCheckpoint; /* For psitblastn */ CharPtr CheckpointFileName; /* For psitblastn */ Int4 longest_intron; /* the length of longest intron for linking HSPs */ FloatLo perc_identity; /* Identity percentage cut-off */ VoidPtr output; /* Output stream to put results to */ FloatHi scalingFactor; /* scaling factor used when constructing pssm for rpsblast. */ Int4 total_hsp_limit; /* total number of HSP's that will be processed to SeqAligns, zero means no limit. */ Boolean mb_one_base_step; /* Scan every base of the database */ Int2 mb_template_length; /* Length of the discontiguous word */ Boolean mb_use_dyn_prog; /* Use dynamic programming gapped extension in megablast with affine gap scores */ } BLAST_OptionsBlk, PNTR BLAST_OptionsBlkPtr; typedef struct _mb_parameter_blk_ { Boolean no_traceback; /* No traceback in greedy extension */ Boolean is_neighboring; /* Is this a neighboring task? */ Boolean full_seqids; /* Print full seqids in tabular output? */ FloatLo perc_identity; /* Identity percentage cut-off */ Int4 max_positions; /* Maximal number of positions in query of a given word */ Boolean disc_word; /* Use a discontiguous word template to find initial matches */ Boolean one_base_step; /* Form words for every position in the database sequence (default is every 4th position) */ Int2 word_weight; /* Number of identical nucleotides in a word match */ Int2 template_length; /* Length of a discontiguous word template */ Boolean use_dyn_prog; /* Use dynamic programming extension for affine gap scores */ } MegaBlastParameterBlk, PNTR MegaBlastParameterBlkPtr; /**************************************************************************** PARAMETER BLOCK: parameters for the BLAST search entered by on command line by user. *****************************************************************************/ typedef struct _blast_parameterblk { BLAST_Score threshold, /* threshold for extending a word hit*/ threshold_first, /* threshold for 1st pass. */ threshold_second, /* threshold for 2nd pass. */ X, /* drop-off score for extension. */ dropoff_1st_pass, /* dropoff ("X") used for 1st pass. */ dropoff_2nd_pass, /* dropoff ("X") used for 2nd pass. */ cutoff_s, /* Final Score to report a hit. */ cutoff_s1, /* Score to save an HSP after a gapped extension. */ cutoff_s2, /* Score to save an HSP after an ungapped extension. */ cutoff_s_first, /* Score (S2) to use on 1st pass */ cutoff_s_second, /* Score (S2) to use on 2nd pass and for "small" gaps in link_hsps (in blast.c) */ /* Max value of s2, used if s2 is set or s2 becomes larger than s. */ cutoff_s2_max, cutoff_big_gap; /* cutoff value for a "big" gap in link_hsps (in blast.c). */ Nlm_FloatHi cutoff_e, /* Expect value to report a hit. */ cutoff_e2, /* Expect value to report a hsp. */ number_of_bits; /* number of bits of significance, used to calculate cutoff_s_first (above). */ Boolean threshold_set, /*TRUE if threshold set on command-line*/ cutoff_s_set, /* TRUE if cutoff score set on c-l */ cutoff_s2_set, /* TRUE if cutoff score2 set on c-l */ cutoff_e_set, /* TRUE if cutoff expect set on c-l */ cutoff_e2_set, /* TRUE if cutoff expect2 set on c-l */ ignore_small_gaps, /* ignore small gaps if TRUE, set by CalculateSecondCutoffScore in blast.c if the search space is smalled than 8*gap_size*gap_size. */ window_size_set;/* TRUE if window size set for MHBLAST*/ Boolean sump_option; /* TRUE if sump is used. */ Int4 gap_size, /* max. gap allowed for small gaps.*/ window_size; /* used for multiple hits BLAST. */ Nlm_FloatHi gap_prob; /* prob. of gap of size "gap" (above).*/ Nlm_FloatHi gap_decay_rate; /* prob. of only one HSP */ Int2 process_num; /* max # processrs permitted (for MP).*/ Boolean old_stats; /* Use "old" stats if TRUE. */ Boolean do_sum_stats; /* Should sum statistics be used? */ Boolean use_large_gaps; /* Use only large gaps for linking HSP's with sum stats. */ Boolean two_pass_method; /* should two passes be used? */ Boolean multiple_hits_only; /* Only the multiple hits alg. used. */ Boolean discontinuous; /* Should discontinuous SeqAlign's be produced? */ Boolean gapped_calculation; /* Is a gapped calc. being done? */ Boolean do_not_reevaluate; /* Don't perform BlastReevaluateWithAmbiguities. */ /* The next three are used ONLY for gapped alignments. */ Int4 gap_open, /* Cost to open a gap (NO extension). */ gap_extend, /* Cost to extend a gap one letter. */ gap_x_dropoff, /* X-dropoff used by Gapped align routine. */ gap_x_dropoff_final; /* X-dropoff (in bits) used by Gapped align routine for FINAL alignment. */ Int4 decline_align; /* Cost for declining alignment */ Nlm_FloatHi gap_trigger; /* Score (in bits) to gap, if an HSP gaps well.*/ /* Options for postion based blast. */ Nlm_FloatHi ethresh; Int4 maxNumPasses, pseudoCountConst; Int4 cpu_limit; /* timeout total. */ Int4 hsp_range_max, /* maximum hits for a range */ max_pieces; /* Max number of pieces allowed (query_length/block_width) */ Boolean perform_culling; /* determines whether culling should be used or not. If not, then hsp_range_max, block_width, and max_pieces are ignored. */ /* These options allow a subset of the database to be examined. IF they are set to zero, then the entire database is examined. */ Int4 first_db_seq, /* 1st sequence in db to be compared. */ final_db_seq; /* Final sequence to be compared. */ Int4 hsp_num_max; /* maximum number of HSP's allowed. Zero indicates no limit. */ Boolean use_best_align; /* option is to use alignments choosen by user in PSM computation API (used in WWW PSI-Blast); */ Boolean no_check_score; MegaBlastParameterBlkPtr mb_params; /* Is this a MegaBlast search? */ CharPtr filter_string; /* String specifying the type of filtering and filter options. - used with Translated RPS Blast */ Boolean is_rps_blast; /* If this RPS Blast ? */ SeqLocPtr query_lcase_mask; /* Masking of input DNA regions */ Boolean explode_seqids; /* make one SeqAlign for every gi on a redundant sequence. */ Boolean is_ooframe; /* Use Out-Of-Frame gapping algorithm */ Int4 shift_pen; /* Out-Of-Frame shift penalty */ Int4 longest_intron; /* the length of longest intron for linking HSPs */ FloatHi scalingFactor; /* scaling factor used when constructing pssm for rpsblast. */ Int4 total_hsp_limit; /* total number of HSP's that will be processed to SeqAligns, zero means no limit. */ } BLAST_ParameterBlk, PNTR BLAST_ParameterBlkPtr; typedef Nlm_Int4 BLAST_Diag, PNTR BLAST_DiagPtr; /* Structure to keep track of the last hit and diag level. */ typedef struct cfj_mod_struct{ Int4 last_hit; Int4 diag_level; } CfjModStruct; /* BLAST_ExtendWord contains information about which diagonals have been extended over (i.e., which diagonals have been tested). This structure will be duplicated once for each context as every context is different. */ typedef struct _blast_extend_word { Int4Ptr _buffer; /* The "real" buffer for diag_level, version, and last_hit arrays. */ CfjModStruct *combo_array; Int4Ptr version; /* still needed?? */ Int4 actual_window; /* The actual window used if the multiple hits method was used and a hit was found. */ } BLAST_ExtendWord, PNTR BLAST_ExtendWordPtr; /* BLAST_ExtendWordParams contains parameters about the extensions. Only one copy of this structure is needed, regardless of how many contexts there are. */ typedef struct _blast_extend_word_params { Int4 bits_to_shift; /* how many bits should the diagonal be shifted to get the "version" */ Int4 min_diag_length, /* Min. length of diagonal, actuall 2**bits_to_shift. */ min_diag_mask; /* Used to mask off everything above min_diag_length (mask = min_diag_length-1). */ Int4 offset; /* "offset" added to query and subject position so that "diag_level" and "last_hit" don't have to be zeroed out every time. */ Int4 window; /* The "window" size, within which two (or more) hits must be found in order to be extended. */ /* Used by BLAST_ExtendWordNew to decide whether or not to prepare the structure for multiple-hit type searches. If TRUE, multiple hits are not neccessary, but possible. */ Boolean multiple_hits; } BLAST_ExtendWordParams, PNTR BLAST_ExtendWordParamsPtr; /* Data block to describe a single sequence. */ typedef struct blast_sequence_block { Uint1Ptr sequence, /* Actual (perhaps transl.) sequence. */ sequence_start; /* Start of sequence, used if the sequence is preceded by a NULLB. Sequences starting with a NULLB are used by BlastWordExtend_L1. */ Int4 length, /* length of sequence. */ original_length,/* length before translation. */ effective_length;/* effective length, used only by query. */ Int2 frame; /* frame of the sequence. */ } BlastSequenceBlk, PNTR BlastSequenceBlkPtr; typedef struct _blast_seg { Int2 frame; Int4 offset; /* start of hsp */ Int4 length; /* length of hsp */ Int4 end; /* end of HSP */ Int4 offset_trim; /* start of trimmed hsp */ Int4 end_trim; /* end of trimmed HSP */ /* Where the gapped extension (with X-dropoff) started. */ Int4 gapped_start; } BLAST_Seg, PNTR BLAST_SegPtr; #define BLAST_NUMBER_OF_ORDERING_METHODS 2 /* 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 (this is a VoidPtr as _blast_hsp is not yet defined), 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 BLAST_HSP. This structure should not be used outside of the function link_hsps. */ typedef struct _blast_hsp_link { /* Used to order the HSP's (i.e., hook-up w/o overlapping). */ VoidPtr link[BLAST_NUMBER_OF_ORDERING_METHODS]; /* number of HSP in the ordering. */ Int2 num[BLAST_NUMBER_OF_ORDERING_METHODS]; /* Sum-Score of HSP. */ Int4 sum[BLAST_NUMBER_OF_ORDERING_METHODS]; /* Sum-Score of HSP, multiplied by the appropriate Lambda. */ Nlm_FloatHi xsum[BLAST_NUMBER_OF_ORDERING_METHODS]; Int4 changed; } BLAST_HSP_LINK, PNTR BLAST_HSP_LINKPtr; /* BLAST_NUMBER_OF_ORDERING_METHODS tells how many methods are used to "order" the HSP's. */ typedef struct _blast_hsp { struct _blast_hsp PNTR next, /* the next HSP */ PNTR prev; /* the previous one. */ BLAST_HSP_LINK hsp_link; /* Is this HSp part of a linked set? */ Boolean linked_set; /* which method (max or no max for gaps) was used? */ Int2 ordering_method; /* how many HSP's make up this (sum) segment */ Int4 num; /* sumscore of a set of "linked" HSP's. */ BLAST_Score sumscore; /* If TRUE this HSP starts a chain along the "link" pointer. */ Boolean start_of_chain; BLAST_Score score; Nlm_FloatHi pvalue; Nlm_FloatHi evalue; BLAST_Seg query, /* query sequence info. */ subject; /* subject sequence info. */ Int2 context; /* Context number of query */ GapXEditBlockPtr gap_info; /* ALL gapped alignment is here */ Int4 num_ref; Int4 linked_to; } BLAST_HSP, PNTR BLAST_HSPPtr; /* The helper arrays contains the info used frequently in the inner for loops. -cfj * One array of helpers will be allocated for each thread. See comments preceding * link_hsps in blast.c for more info. */ typedef struct link_help_struct{ BLAST_HSPPtr ptr; Int4 q_off_trim; Int4 s_off_trim; Int4 sum[BLAST_NUMBER_OF_ORDERING_METHODS]; Int4 maxsum1; Int4 next_larger; } LinkHelpStruct; /* Orders information for HSP accesses. */ typedef struct hsp_helper{ Int4 qoffset, qend; } BLAST_HSP_helper, PNTR BLAST_HSP_helperPtr; typedef struct _exact_match { Int4 q_off; Int4 s_off; } MegaBlastExactMatch, PNTR MegaBlastExactMatchPtr; typedef struct _blast_hitlist { struct _blast_hitlist PNTR next; BLAST_HSPPtr PNTR hsp_array; /* head of linked list of HSPs */ Int4 hspmax, /* max no. of HSPs allowed per hit list */ hspcnt, /* no. of HSPs in hit list */ hspcnt_max; /* no. of HSPs in hitlist, before reaping */ Boolean further_process; /* This sequence has been found interesting, it should be further processed by a gapped alignment etc. */ Boolean do_not_reallocate; /* Don't reallocate the HSP's, probably because there is no more memory for this. */ /* added -cfj */ LinkHelpStruct *lh_helper; Int4 lh_helper_size; MegaBlastExactMatchPtr PNTR exact_match_array; /* Array to hold initial exact match hits */ Int4 exact_match_max; } BLAST_HitList, PNTR BLAST_HitListPtr; /* The next two structures are the final output produced by BLAST. Formatters should then convert the data into SeqAligns or the BLAST ASN.1 spec. */ typedef struct _blast_results_hsp { Int2 ordering_method;/* determines whether large or small gap was used. */ Int4 number; /* number of HSP's used to calculate the p-value. */ BLAST_Score score; /* score of this HSP. */ Nlm_FloatHi e_value,/* expect value of this set of HSP's. */ p_value,/* p-value of this set of HSP's. */ bit_score; /* above score * lambda/ln2 */ Int2 context; /* context number of query. */ Int2 query_frame, /* frame of query, non-zero if transl. */ subject_frame; /* frame of subject, non-zero if transl. */ Int4 query_offset, /* Start of the query HSP. */ query_length, /* Length of the query HSP. */ subject_offset, /* Start of the subject HSP. */ subject_length, /* Length of the subject HSP.*/ hspset_cnt; /* which set of HSP's? */ /* Starting points (on original HSP) for a gapped extension with X dropoff. */ Int4 query_gapped_start, subject_gapped_start; GapXEditBlockPtr gap_info; /* ALL gapped alignment is here */ struct _blast_result_hitlist PNTR point_back; struct _blast_heap_struct PNTR back_left, PNTR back_right; } BLASTResultHsp, PNTR BLASTResultHspPtr; /* The following structure contains the subject info, if the readdb facility is not being used. Then the subject information is kept here. Otherwise this structure is NULL. */ typedef struct _blast_subject_info { SeqIdPtr sip; /* ID of the subject. */ CharPtr defline; /* Defline of the subject. */ Int4 length; /* untranslated length of the database sequence. */ } BLASTSubjectInfo, PNTR BLASTSubjectInfoPtr; typedef struct _blast_result_hitlist { BLASTResultHspPtr hsp_array; /* An array holding the HSP's. */ Nlm_FloatHi best_evalue; /* best evalue in all the HSP's. */ Int4 high_score; /* HSP with highest score. */ Int4 hspcnt, /* Number of HSP's. */ subject_id; /* ID of the subject. */ Int2 db_id; /* ID (0,1,2...) of the db if multiple db's searched. */ Int4 subject_length; /* length of the database sequence. */ BLASTSubjectInfoPtr subject_info; /* Subject info if the readdb facility is not being used. */ SeqAlignPtr seqalign; /* alignment, if this a gapped calculation. */ Int4 num_ref; } BLASTResultHitlist, PNTR BLASTResultHitlistPtr; typedef struct _blast_heap_struct { Int4 cutvalue; /* start of a region? */ BLASTResultHspPtr PNTR heap; Int4 num_in_heap; /* Number in 'heap' */ Int4 num_of_ref; struct _blast_heap_struct PNTR next, PNTR prev; } BLASTHeapStruct, PNTR BLASTHeapPtr; /* Holds the results already saved. */ typedef struct _blast_results_struct { BLASTResultHitlistPtr PNTR results; Int4 hitlist_count, /* Number of hitlists saved on results array already. */ hitlist_max, /* Length of results array. */ max_pieces; /* For range-dependent limits. */ BLASTResultHspPtr **heap; Int4 *num_in_heap; BLASTHeapPtr heap_ptr; } BLASTResultsStruct, PNTR BLASTResultsStructPtr; /* Holds the data for all possible words that might be used by BLAST. */ typedef struct _blast_all_words { Uint1Ptr *array, /* All the possible words */ array_storage; /* Storage for the words in array. */ Int4 num_of_cols, wordsize; Boolean rows_allocated, /* are the rows (of length the wordsize) alloc.*/ specific; /* specific (limited) words are to be indexed. */ } BlastAllWord, *BlastAllWordPtr; typedef struct _blast_seqid_list { SeqIdPtr seqid_list; /* A list of SeqId's (may or may not be in the database) that should serve as subject sequences for BLAST'ing. */ Uint1 mode; /* Either BLAST_OWN, or BLAST_NOT_OWN. Specifies whether they should be deleted. */ SeqIdPtr seqid_ptr; } BlastSeqIdList, *BlastSeqIdListPtr; /* Contains gi and ordinal number for use by random access BLAST. */ typedef struct _double_int4 { Int4 gi, ordinal_id, start; } BlastDoubleInt4, *BlastDoubleInt4Ptr; typedef struct _blast_gi_list { BlastDoubleInt4Ptr gi_list; /* List of gi's. */ BlastDoubleInt4Ptr *gi_list_pointer; /* Pointer to above list. */ Int4 current; /* Current position in gi list. */ Int4 total; /* total number of gi's. */ Boolean gilist_not_owned; /* do not delete gilist at end. */ } BlastGiList, *BlastGiListPtr; /* used for keeping start and stop of hits to query, for ALU filtering. */ typedef struct _blast_hit_range { BlastDoubleInt4Ptr range_list; /* ranges. */ BlastDoubleInt4Ptr *range_list_pointer; /* Pointer to above list. */ Int4 current, /* current position in list. */ total; /* total number in list. */ SeqIdPtr query_id; /* ID to be put on SeqLoc's that are produced. */ Int4 base_offset; /* used if a SeqLoc is searched and it does not start at begining of sequence. */ } BlastHitRange, *BlastHitRangePtr; /* Contains BLAST error messages. */ typedef struct _blast_error_msg { Uint2 level;/* corresponds to levels of ErrPostEx [none(0), info(1), warn(2), error(3) and fatal(4)] */ CharPtr msg; } BlastErrorMsg, *BlastErrorMsgPtr; /* Holds data for each "context" (which is generally equal to one frame of the query). blastx would have six contexts, blastp would have one. */ typedef struct _blast_context_structure { Boolean query_allocated;/* The BlastSequenceBlkPtr IS allocated. */ BlastSequenceBlkPtr query; /* query sequence. */ BLAST_ExtendWordPtr ewp;/* keep track of diagonal etc. for each frame */ ValNodePtr location; /* Where to start/stop masking. */ } BLASTContextStruct, PNTR BLASTContextStructPtr; /* Structure used for full Smith-Waterman results. */ typedef struct SWResults { Uint1Ptr seq; Int4 seqStart; Int4 seqEnd; Int4 queryStart; Int4 queryEnd; Int4 *reverseAlignScript; BLAST_Score score; BLAST_Score scoreThisAlign; Nlm_FloatHi eValue; Nlm_FloatHi eValueThisAlign; Nlm_FloatHi Lambda; Nlm_FloatHi logK; SeqIdPtr subject_id; /*used to display the sequence in alignment*/ struct SWResults *next; Boolean isFirstAlignment; Int4 subject_index; /* needed to break ties on rare occasions */ } SWResults; /* Average sizes of protein and nucl. sequences. */ #define BLAST_AA_AVGLEN 300 #define BLAST_NT_AVGLEN 1000 /* How many ticks should be emitted total. */ #define BLAST_NTICKS 50 #define BLAST_DB_CHUNK_SIZE 500 /* period of sending out a star/message. */ #define STAR_MSG_PERIOD 60 typedef struct _BlastThrInfo { TNlmMutex db_mutex; /*lock for access to database*/ TNlmMutex results_mutex; /*lock for storing results */ TNlmMutex callback_mutex; /*lock for issuing update ticks on the screen*/ /* Mutex for recalculation of ambiguities, in BlastReevaluateWithAmbiguities */ TNlmMutex ambiguities_mutex; /* SeqId lists if only a certain number of the database sequences will be used for the search. */ BlastSeqIdListPtr blast_seqid_list; /* GI List to be used if database will be searched by GI. current is the current element in the array being worked on. global_gi_being_used specifies that it will be used. */ Int4 gi_current; BlastGiListPtr blast_gi_list; /* db_chunk_size is used, if the db is smaller than BLAST_DB_CHUNK_SIZE */ Int4 db_chunk_size; /* The last db sequence to be assigned. Used only in get_db_chunk after the acquisition of the "db_mutex" (above). */ Int4 db_chunk_last; /* the last sequence in the database to be compared against. */ Int4 final_db_seq; Int4 number_seqs_done; /*number of sequences already tested*/ Int4 db_incr; /*size of a database chunk to get*/ Int4 last_db_seq; /* How many positive hits were found (set by ReapHitlist, read by tick_proc and star_proc). */ Int4 number_of_pos_hits; /* Use by star_proc to determine whether to emit a star. */ time_t last_tick; /* tells star_proc to check that a star should be emitted. */ TNlmThread awake_thr; Boolean awake; /* tells index_proc to check that a message should be emitted. */ TNlmThread index_thr; Boolean awake_index; /* Callback functions to indicate progress, or lack thereof. */ int (LIBCALLBACK *tick_callback)PROTO((Int4 done, Int4 positives)); int (LIBCALLBACK *star_callback)PROTO((Int4 done, Int4 positives)); int (LIBCALLBACK *index_callback)PROTO((Int4 done, Int4 positives)); /* whether real databases are done */ Boolean realdb_done; } BlastThrInfo, PNTR BlastThrInfoPtr; /* Structure used for matrix rescaling. */ typedef struct _blast_matrix_rescale { Int4 alphabet_size, query_length; /* length of query. */ Uint1Ptr query; Nlm_FloatHi *standardProb; Int4Ptr *matrix; Int4Ptr *private_matrix; BLAST_KarlinBlkPtr *kbp_std, *kbp_psi, *kbp_gap_std, *kbp_gap_psi; Nlm_FloatHi lambda_ideal, K_ideal; } BlastMatrixRescale, *BlastMatrixRescalePtr; /* The central structure for the BLAST search. This structure should contain data (or pointers to data) for all the information in a BLAST search. */ #define BLAST_SEARCH_ALLOC_QUERY 1 #define BLAST_SEARCH_ALLOC_SUBJECT 2 #define BLAST_SEARCH_ALLOC_PBP 4 #define BLAST_SEARCH_ALLOC_SBP 8 #define BLAST_SEARCH_ALLOC_WFP_FIRST 16 #define BLAST_SEARCH_ALLOC_WFP_SECOND 32 #define BLAST_SEARCH_ALLOC_EWPPARAMS 64 #define BLAST_SEARCH_ALLOC_CONTEXT 128 #define BLAST_SEARCH_ALLOC_RESULTS 256 #define BLAST_SEARCH_ALLOC_READDB 512 #define BLAST_SEARCH_ALLOC_TRANS_INFO 1024 #define BLAST_SEARCH_ALLOC_ALL_WORDS 2048 #define BLAST_SEARCH_ALLOC_QUERY_SLP 4096 /* #define BLAST_SEARCH_ALLOC_GILIST 8192 */ #define BLAST_SEARCH_ALLOC_THRINFO 8192 /* 16384 */ typedef struct blast_search_block { Int4 allocated; /* bit fields specify which structures from below are allocated. If a field is allocated, then it's bit is non-zero. structure bit-field (define) ----------------------------------------- query BLAST_SEARCH_ALLOC_QUERY subject BLAST_SEARCH_ALLOC_SUBJECT pbp BLAST_SEARCH_ALLOC_PBP sbp BLAST_SEARCH_ALLOC_SBP wfp_first BLAST_SEARCH_ALLOC_WFP_FIRST wfp_second BLAST_SEARCH_ALLOC_WFP_SECOND ewp_params BLAST_SEARCH_ALLOC_EWPPARAMS context BLAST_SEARCH_ALLOC_CONTEXT result_struct BLAST_SEARCH_ALLOC_RESULTS rdfp BLAST_SEARCH_ALLOC_READDB translation_table BLAST_SEARCH_ALLOC_TRANS_INFO translation_table_rc all_words BLAST_SEARCH_ALLOC_ALL_WORDS query_slp BLAST_SEARCH_ALLOC_QUERY_SLP blast_gi_list BLAST_SEARCH_ALLOC_GILIST */ /* Specifies whether the search is position based or not. */ Boolean positionBased; Boolean posConverged; /* Specifies that the query sequence was invalid (e.g., XXXXXXXXXXXXXXXXXXXXXX). */ Boolean query_invalid; /* Specifies that the search timed out (i.e., cpu time limit was reached). */ Boolean timed_out; /* The BLASTContextStructPtr is an array and each element contains information about the query sequence and the frame number. If there are six frames (e.g., blastx) then the BLASTContextStructPtr is six elements long; if there's one frame (e.g., blastp) then BLASTContextStructPtr is one element long. number_of_contexts states how long the context array is. */ BLASTContextStructPtr context; Int2 first_context, last_context; /* The GapAlignBlkPtr used by ALIGN (in gapxdrop.c) for gapped alignments. */ GapAlignBlkPtr gap_align; /* All the possible words. */ BlastAllWordPtr all_words; /* Set the context_factor, which specifies how many different ways the query or db is examined (e.g., blastn looks at both stands of query, context_factor is 2). */ Int2 context_factor; /* What type of search (e.g., blastp, blastx, etc.)? */ CharPtr prog_name; Uint1 prog_number; /* translation_table and translation_table_rc holds the translation from ncbi2na to ncbistdaa for normal and reverse-complement translations. Only used and initialized with tblast[nx]. Initialized by GetPrivatTranslationTable */ Uint1Ptr translation_table, translation_table_rc; /* ValNodePtr containing error messages. */ ValNodePtr error_return; /* ValNodePtr containing masking SeqLocPtr's */ ValNodePtr mask; /* What genetic codes are we using to translate the query or database when needed. Based upon NCBI genetic codes. */ CharPtr genetic_code, /* genetic code used for query. */ db_genetic_code; /* genetic code used for database. */ /* The BlastSequenceBlk's subject hold info about the subject. Info about the original sequence is in original_seq. This will be NULL if the sequence was not translated. */ Uint1Ptr translation_buffer; /* Buffer for (tblast[nx]) db translations*/ Int4 translation_buffer_size; /* size of translation_buffer. */ CharPtr original_seq; /* Original (i.e., untransl.) sequence. */ BlastSequenceBlkPtr subject;/* subject sequence. */ /* SeqLocPtr for the query, owned by the called and not by BLAST. */ SeqLocPtr query_slp; /* Id's for the query and subject. */ SeqIdPtr query_id; /* ID for the query, any form. */ Int4 subject_id; /* the number of the subject, in the DB. */ BLAST_ParameterBlkPtr pbp; /* options selected. */ BLAST_ScoreBlkPtr sbp; /* info on scoring. */ BLAST_ExtendWordParamsPtr ewp_params; /* parameters for extensions.*/ /* For the two-pass method two BLAST_WordFinderPtr's are required. The actual wfp's are in wfp_first and wfp_second. "wfp" is just a pointer to one of those two. If they have been allocated (at all) is signified by setting the bit-fields above. */ BLAST_WordFinderPtr wfp, /* find initial words. */ wfp_first, /* words for first pass. */ wfp_second;/* words for second pass. */ /* For the two-pass this should be set to TRUE on the first (preliminary) pass and FALSE on the second pass. */ Boolean prelim; /* The "current" hit, that is the one being worked on right now. If a hitlist is deemed significant, then "current_hitlist" is moved to "seqalign". current_hitlist_purge specifies whether the hitlist should be purged after each call to a WordFinder; it will generally be purged except for non-initial frames of tblast[nx]. */ Boolean current_hitlist_purge; BLAST_HitListPtr current_hitlist; BlastSequenceBlkPtr PNTR query_dnap; /* query DNAP sequence. */ /* The worst evalue seen by this thread so far. Only filled in if the hitlist is already full, otherwise it should be DBL_MAX. */ Nlm_FloatHi worst_evalue; /* Size of the HSP array on the "current_hitlist" */ Int4 hsp_array_size; /* Contains hits that are significant. */ Int4 result_size; BLASTResultsStructPtr result_struct; Int8 dblen; /* total length of the database. */ Int8 dblen_eff; /* effective length of the database. */ Int8 dblen_eff_real; /* effective length of the database. */ Int4 dbseq_num; /* number of sequences in the database. */ Int4 length_adjustment; /* amount removed from end of query and db sequences. */ Nlm_FloatHi searchsp_eff; /* Effective search space (used for statistics). */ ReadDBFILEPtr rdfp, /* I/O PTR for database files. */ rdfp_list; /* linked rdfp list of all databases. */ /* The subject info (id and defline) is kept here for the current sequence if the readdb facility is not used. This structure should only be used if rdfp is NULL. */ BLASTSubjectInfoPtr subject_info; /* A list of SeqId's from the database to use for the BLAST run. */ /* BlastSeqIdListPtr blast_seqid_list; */ /* BlastGiListPtr blast_gi_list; */ /* Data used in threads - previously global variables */ BlastThrInfoPtr thr_info; /* start and stop of query that must be included for an alignment to be counted. The Boolean whole_query specifies whether these are valid (i.e., have been set) or not. */ Boolean whole_query; Int4 required_start, required_end; /* Callback functions to indicate progress, or lack thereof. */ /* int (LIBCALLBACK *tick_callback)PROTO((Int4 done, Int4 positives)); */ /* int (LIBCALLBACK *star_callback)PROTO((Int4 done, Int4 positives)); */ /* Callback function to handle results (e.g., print them out for neighboring) in place of BlastSaveCurrentHitlist. */ int (LIBCALLBACK *handle_results)PROTO((VoidPtr search)); /* Output stream to put results to */ VoidPtr output; /* These "counters" keep track of how often certain operations were performed. This counting is performed only if BLAST_COLLECT_STATS is defined. */ Int8 first_pass_hits, /* no. of hits on 1st pass. */ second_pass_hits, /* no. of hits on 2nd pass. */ second_pass_trys, /* no. of seqs that made it to 2nd pass. */ first_pass_extends, /* no. extended on 1st pass. */ second_pass_extends, /* no. extended on 2nd pass. */ first_pass_good_extends,/* no. successfully extended on 1st pass. */ second_pass_good_extends,/* no. successfully extended on 2nd pass. */ number_of_seqs_better_E,/* how many sequences were better than E. */ prelim_gap_no_contest, /* No. of HSP's under E=10 alone. */ prelim_gap_passed, /* No. of HSP's that passed prelim gapping. */ prelim_gap_attempts, /* No. of HSP's we attempted to gap. */ real_gap_number_of_hsps, /* How many HSP's were gapped in BlastGetGappedScore. */ semid; /* Here will be stored ID of load-ballance semaphore */ /* Callback for the queueing system. */ int (LIBCALLBACK *queue_callback)PROTO((int semid, int num, int num_cpu)); GreedyAlignMemPtr abmp; /* Memory for megablast greedy extension */ Int4 PNTR query_context_offsets; /* offsets for all queries and strands in a concatenated sequence */ SeqIdPtr PNTR qid_array; /* Ids of all queries in Mega BLAST search */ BLASTResultsStructPtr PNTR mb_result_struct; /* one result struct per query for Mega BLAST */ ValNodePtr mb_endpoint_results; /* Points to linked list of results */ } BlastSearchBlk, PNTR BlastSearchBlkPtr; typedef struct _blast_hsp_segment { Int4 q_start, q_end; Int4 s_start, s_end; struct _blast_hsp_segment PNTR next; } BLASTHSPSegment, PNTR BLASTHSPSegmentPtr; #ifdef __cplusplus } #endif #endif /* !__BLASTSTR__ */