1 /* $Id: smith_waterman.h,v 1.2 2005/12/19 15:38:01 gertz Exp $ 2 * =========================================================================== 3 * 4 * PUBLIC DOMAIN NOTICE 5 * National Center for Biotechnology Information 6 * 7 * This software/database is a "United States Government Work" under the 8 * terms of the United States Copyright Act. It was written as part of 9 * the author's official duties as a United States Government employee and 10 * thus cannot be copyrighted. This software/database is freely available 11 * to the public for use. The National Library of Medicine and the U.S. 12 * Government have not placed any restriction on its use or reproduction. 13 * 14 * Although all reasonable efforts have been taken to ensure the accuracy 15 * and reliability of the software and data, the NLM and the U.S. 16 * Government do not and cannot warrant the performance or results that 17 * may be obtained by using this software or data. The NLM and the U.S. 18 * Government disclaim all warranties, express or implied, including 19 * warranties of performance, merchantability or fitness for any particular 20 * purpose. 21 * 22 * Please cite the author in any work or product based on this material. 23 * 24 * ===========================================================================*/ 25 /** 26 * @file smith_waterman.h 27 * Definitions for computing Smith-Waterman alignments 28 * 29 * @author Alejandro Schaffer, E. Michael Gertz 30 */ 31 #ifndef __SMITH_WATERMAN__ 32 #define __SMITH_WATERMAN__ 33 34 #include <algo/blast/core/blast_export.h> 35 #include <algo/blast/core/ncbi_std.h> 36 37 #ifdef __cplusplus 38 extern "C" { 39 #endif 40 41 /** 42 * An instance of Blast_ForbiddenRanges is used by the Smith-Waterman 43 * algorithm to represent ranges in the database that are not to be 44 * aligned. 45 */ 46 typedef struct Blast_ForbiddenRanges { 47 int isEmpty; /**< True if there are no forbidden ranges */ 48 int *numForbidden; /**< how many forbidden ranges at each 49 database position */ 50 int **ranges; /**< forbidden ranges for each database 51 position */ 52 int capacity; /**< length of the query sequence */ 53 } Blast_ForbiddenRanges; 54 55 56 /** 57 * Initialize a new, empty Blast_ForbiddenRanges 58 * 59 * @param self object to be initialized 60 * @param capacity the number of ranges that may be stored 61 * (must be at least as long as the length 62 * of the query) 63 */ 64 NCBI_XBLAST_EXPORT 65 int Blast_ForbiddenRangesInitialize(Blast_ForbiddenRanges * self, 66 int capacity); 67 68 69 /** Reset self to be empty */ 70 NCBI_XBLAST_EXPORT 71 void Blast_ForbiddenRangesClear(Blast_ForbiddenRanges * self); 72 73 74 /** Add some ranges to self 75 * @param self an instance of Blast_ForbiddenRanges [in][out] 76 * @param queryStart start of the alignment in the query sequence 77 * @param queryEnd the end of the alignment in the query sequence 78 * @param matchStart start of the alignment in the subject sequence 79 * @param matchEnd the end of the alignment in the subject sequence 80 */ 81 NCBI_XBLAST_EXPORT 82 int Blast_ForbiddenRangesPush(Blast_ForbiddenRanges * self, 83 int queryStart, int queryEnd, 84 int matchStart, int matchEnd); 85 86 87 /** 88 * Release the storage associated with the fields of self, but do not 89 * delete self 90 * 91 * @param self an instance of Blast_ForbiddenRanges [in][out] 92 */ 93 NCBI_XBLAST_EXPORT 94 void Blast_ForbiddenRangesRelease(Blast_ForbiddenRanges * self); 95 96 97 /** 98 * Find the left-hand endpoints of the locally optimal Smith-Waterman 99 * alignment given the score and right-hand endpoints computed by 100 * Blast_SmithWatermanScoreOnly. 101 * 102 * @param *score_out the score of the optimal alignment -- should 103 * equal score_in. 104 * @param *matchSeqStart the left-hand endpoint of the alignment in 105 * the database sequence 106 * @param *queryStart the right-hand endpoint of the alignment 107 * in the query sequence 108 * @param subject_data the database sequence data 109 * @param subject_length length of matchSeq 110 * @param query_data the query sequence data 111 * @param matrix amino-acid scoring matrix 112 * @param gapOpen penalty for opening a gap 113 * @param gapExtend penalty for extending a gap by one amino acid 114 * @param matchSeqEnd right-hand endpoint of the alignment in 115 * the database sequence 116 * @param queryEnd right-hand endpoint of the alignment in 117 * the query 118 * @param score_in the score of the alignment 119 * @param positionSpecific determines whether matrix is position 120 * specific or not 121 * @param forbiddenRanges ranges that must not be included in the alignment 122 * 123 * @return 0 on success, -1 on out-of-memory 124 */ 125 NCBI_XBLAST_EXPORT 126 int Blast_SmithWatermanFindStart(int * score_out, 127 int *matchSeqStart, 128 int *queryStart, 129 const Uint1 * subject_data, 130 int subject_length, 131 const Uint1 * query_data, 132 int **matrix, 133 int gapOpen, 134 int gapExtend, 135 int matchSeqEnd, 136 int queryEnd, 137 int score_in, 138 int positionSpecific, 139 const Blast_ForbiddenRanges * 140 forbiddenRanges); 141 142 /** 143 * Compute the score and right-hand endpoints of the locally optimal 144 * Smith-Waterman alignment, possibly subject to the restriction that some 145 * ranges are forbidden. 146 * 147 * @param *score the computed score 148 * @param *matchSeqEnd the right-hand end of the alignment in the 149 * database sequence 150 * @param *queryEnd the right-hand end of the alignment in the 151 * query sequence 152 * @param subject_data the database sequence data 153 * @param subject_length length of matchSeq 154 * @param query_data the query sequence data 155 * @param query_length length of query 156 * @param matrix amino-acid scoring matrix 157 * @param gapOpen penalty for opening a gap 158 * @param gapExtend penalty for extending a gap by one amino acid 159 * @param forbiddenRanges lists areas that should not be aligned [in] 160 * @param positionSpecific determines whether matrix is position 161 * specific or not 162 * @return 0 on success; -1 on out-of-memory 163 */ 164 NCBI_XBLAST_EXPORT 165 int Blast_SmithWatermanScoreOnly(int *score, 166 int *matchSeqEnd, int *queryEnd, 167 const Uint1 * subject_data, 168 int subject_length, 169 const Uint1 * query_data, 170 int query_length, int **matrix, 171 int gapOpen, int gapExtend, 172 int positionSpecific, 173 const Blast_ForbiddenRanges * 174 forbiddenRanges); 175 176 #ifdef __cplusplus 177 } 178 #endif 179 180 #endif 181