|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/tools/gapxdrop.h |
source navigation diff markup identifier search freetext search file search |
1 /* ===========================================================================
2 *
3 * PUBLIC DOMAIN NOTICE
4 * National Center for Biotechnology Information
5 *
6 * This software/database is a "United States Government Work" under the
7 * terms of the United States Copyright Act. It was written as part of
8 * the author's official duties as a United States Government employee and
9 * thus cannot be copyrighted. This software/database is freely available
10 * to the public for use. The National Library of Medicine and the U.S.
11 * Government have not placed any restriction on its use or reproduction.
12 *
13 * Although all reasonable efforts have been taken to ensure the accuracy
14 * and reliability of the software and data, the NLM and the U.S.
15 * Government do not and cannot warrant the performance or results that
16 * may be obtained by using this software or data. The NLM and the U.S.
17 * Government disclaim all warranties, express or implied, including
18 * warranties of performance, merchantability or fitness for any particular
19 * purpose.
20 *
21 * Please cite the author in any work or product based on this material.
22 *
23 * ===========================================================================*/
24
25 /*****************************************************************************
26
27 File name: gapxdrop.h
28
29 Author: Gennadiy Savchuk, Jinqhui Zhang, Tom Madden
30
31 Contents: prototypes to perform a gapped alignment on two sequences.
32
33 ****************************************************************************/
34 /* $Revision: 6.19 $
35 * $Log: gapxdrop.h,v $
36 * Revision 6.19 2003/02/28 22:57:24 dondosha
37 * Added prototype for OOFTracebackToGapXEditBlock
38 *
39 * Revision 6.18 2002/05/09 17:01:23 dondosha
40 * Renamed typedefs dp_ptr and dp_node to GapXDPPtr and GapXDP
41 *
42 * Revision 6.17 2002/05/09 16:13:51 dondosha
43 * Changed name of the dp_node structure
44 *
45 * Revision 6.16 2002/05/08 22:48:27 dondosha
46 * Allocate memory for dynamic programming upfront in Mega BLAST case
47 *
48 * Revision 6.15 2001/07/19 22:13:32 dondosha
49 * Made GapXEditScriptDelete public for use in mblast.c
50 *
51 * Revision 6.14 2000/11/30 21:37:39 madden
52 * Roll back before GapXDropSetAlignMask changes
53 *
54 * Revision 6.13 2000/11/15 15:15:57 madden
55 * Add GapXDrop_dp, align_mask, and x_align_mask
56 *
57 * Revision 6.12 2000/08/08 21:46:20 shavirin
58 * Added boolean discontinuous to GapAlignBlk and GapXEditBlock
59 *
60 * Revision 6.11 2000/07/17 15:26:06 shavirin
61 * Added parameter to function OOFGapXEditBlockToSeqAlign().
62 *
63 * Revision 6.10 2000/07/11 20:49:07 shavirin
64 * Added all major functions for Out-Of-Frame alignment.
65 *
66 * Revision 6.8 2000/05/16 18:36:15 dondosha
67 * Added prototype for GXECollectDataForSeqalign
68 *
69 * Revision 6.7 2000/03/29 21:54:57 dondosha
70 * Added prototype for GapXEditScriptNew
71 *
72 * Revision 6.6 1999/11/26 22:07:48 madden
73 * Added PerformNtGappedAlignment and ALIGN_packed_nucl
74 *
75 * Revision 6.5 1999/03/17 16:49:10 madden
76 * Removed comment within comment
77 *
78 * Revision 6.4 1998/11/17 13:39:03 madden
79 * Made ALIGN non-static
80 *
81 * Revision 6.3 1998/08/26 18:51:08 kans
82 * fixed -v -fd warning
83 *
84 * Revision 6.2 1998/04/17 19:41:18 madden
85 * Zhengs changes for decline to align
86 *
87 * Revision 6.1 1997/09/22 17:36:31 madden
88 * MACROS for position-specific matrices from Andy Neuwald
89 *
90 * Revision 6.0 1997/08/25 18:53:17 madden
91 * Revision changed to 6.0
92 *
93 * Revision 1.17 1997/04/15 22:01:53 madden
94 * Added original_length[12] for translating searches.
95 *
96 * Revision 1.16 1997/03/14 21:01:59 madden
97 * Changed to use less memory in ALIGN, with GapXDropStateArrayStructPtr.
98 *
99 * Revision 1.15 1997/03/01 18:25:33 madden
100 * Boolean reverse added to GapXEditBlock.
101 *
102 * Revision 1.14 1997/02/23 16:44:47 madden
103 * Memory, saved on GapAlignBlkPtr, reuses.
104 *
105 * Revision 1.13 1997/02/20 22:58:49 madden
106 * Added CODON_LENGTH define.
107 *
108 * Revision 1.12 1997/02/20 21:50:24 madden
109 * Added frame and translation information to GapAlignBlk, assigned it.
110 *
111 * Revision 1.11 1997/02/10 15:25:33 madden
112 * Added posConverged and posMatrix.
113 *
114 * Revision 1.10 1997/02/04 16:22:32 madden
115 * Changes to enable gapped alignments on the reverse strand.
116 *
117 * Revision 1.9 1997/01/17 17:41:44 madden
118 * Added flags for position based BLAST.
119 *
120 * Revision 1.8 1997/01/16 20:20:49 madden
121 * TracebackToGapXEditBlock made non-static.
122 *
123 * Revision 1.7 1997/01/06 22:40:55 madden
124 * Added function SimpleIntervalToGapXEditBlock.
125 *
126 * Revision 1.6 1997/01/06 19:31:49 madden
127 * Removed subject and query ID from GapAlignBlk.
128 *
129 * Revision 1.5 1997/01/06 17:22:59 madden
130 * Added GapXEditBlockPtr.
131 *
132 * Revision 1.4 1996/12/30 15:44:25 madden
133 * Added capability to require a portion of the query sequence.
134 *
135 * Revision 1.3 1996/12/16 15:29:12 madden
136 * Changed gapalign.h to gapxdrop.h
137 *
138 * Revision 1.2 1996/12/12 16:45:03 madden
139 * GapAlignBlkPtr used instead of arguments in functions.
140 *
141 * Revision 1.1 1996/12/12 14:02:51 madden
142 * Initial revision
143 *
144 */
145
146
147 #ifndef __GAPXDROP__
148 #define __GAPXDROP__
149
150 #include <ncbi.h>
151 #include <readdb.h>
152 #include <sequtil.h>
153
154 #ifdef __cplusplus
155 extern "C" {
156 #endif
157
158 #define CODON_LENGTH 3
159
160 #define GAPALIGN_SUB ((Uint1)0) /*op types within the edit script*/
161 #define GAPALIGN_INS ((Uint1)1)
162 #define GAPALIGN_DEL ((Uint1)2)
163 #define GAPALIGN_DECLINE ((Uint1)3)
164
165 typedef struct gapx_edit_script {
166 Uint1 op_type; /* GAPALIGN_SUB, GAPALIGN_INS, or GAPALIGN_DEL */
167 Int4 num; /* Number of operations */
168 struct gapx_edit_script PNTR next;
169 } GapXEditScript, PNTR GapXEditScriptPtr;
170
171 typedef struct gapx_edit_block {
172 Int4 start1, start2, /* starts of alignments. */
173 length1, length2, /* total lengths of the sequences. */
174 original_length1, /* Untranslated lengths of the sequences. */
175 original_length2;
176 Int2 frame1, frame2; /* frames of the sequences. */
177 Boolean translate1, translate2; /* are either of these be translated. */
178 Boolean reverse; /* reverse sequence 1 and 2 when producing SeqALign? */
179 Boolean is_ooframe; /* Is this out_of_frame edit block? */
180 Boolean discontinuous; /* Is this OK to produce discontinuous SeqAlign? */
181 GapXEditScriptPtr esp;
182 } GapXEditBlock, PNTR GapXEditBlockPtr;
183
184 /*
185 Structure to keep memory for state structure.
186 */
187 typedef struct _state_array_struct {
188 Int4 length, /* length of the state_array. */
189 used; /* how much of length is used. */
190 Uint1Ptr state_array; /* array to be used. */
191 struct _state_array_struct PNTR next;
192 } GapXDropStateArrayStruct, PNTR GapXDropStateArrayStructPtr;
193
194 /***************************************************************************
195 Macros added by Andy Neuwald in order to allow easy modification of matrices.
196 ***************************************************************************/
197
198 #define MtrxScoreGapAlign(S,x,y) ((S)->posMatrix[(x)][(y)])
199 #define PtrMtrxScoreGapAlign(S,x) ((S)->posMatrix[(x)])
200
201 #define MtrxScoreGapAlign2(S,x,y) \
202 ((S)->posMatrix[( (x) %(S)->query_length)][(y)])
203 #define PtrMtrxScoreGapAlign2(S,x) \
204 ((S)->posMatrix[( (x) %(S)->query_length)])
205
206 /********************************************************************/
207
208 /* Dynamic Programming structure. */
209 typedef struct _gapxdrop_DP_ {
210 Int4 CC, DD, FF; /* Values for gap opening and extensions (?). */
211 } PNTR GapXDPPtr, GapXDP;
212
213 /*
214 Structure used to pass arguments for gapped alignment functions.
215 */
216
217 typedef struct _gapalign_blk {
218 /*
219 The following must be supplied by caller.
220 */
221 Uint1Ptr query, /* The query sequence. */
222 subject; /* The subject sequence. */
223 Int4 query_length, /* the length of the query. */
224 subject_length, /* The subject length. */
225 q_start, /* query letter to start the gapped align. */
226 s_start, /* subject letter to start the gapped align.*/
227 include_query, /* length of query (starting from q_start) that
228 MUST be included in an alignment. */
229 gap_open, /* Cost to open a gap. */
230 gap_extend, /* cost to extend a gap. */
231 decline_align, /* decline to align penalty */
232 x_parameter, /* values of X-dropoff parameter. */
233 shift_pen; /* penalty for the frame shift */
234 Int4Ptr PNTR matrix; /* Matrix for the alignment. */
235 Int4Ptr PNTR posMatrix; /* Matrix for position-based searches. */
236 Boolean translate1, /* are either of these be translated. */
237 translate2;
238
239 /*
240 The state, state_column_length, and state_row_length are used by ALIGN.
241 If state is NULL, then ALIGN allocates a memory block and frees it before
242 returning (for "call and forget" applications).
243 */
244 GapXDropStateArrayStructPtr state_struct;
245 /*
246 The score, start, and stop of alignments are filled in by the
247 functions PerformGappedAlignment and PerformGappedAlignmentWithTraceback
248 */
249 Int4 score, /* score of alignment. */
250 query_start, /* start of alignment on query. */
251 query_stop, /* end of alignment on query. */
252 subject_start, /* start of alignment on subject. */
253 subject_stop; /* end of alignment on subject. */
254 Int2 query_frame, /* Frame of the query (0 is no-frame) */
255 subject_frame; /* Frame of the subject (0 is no-frame). */
256 /*
257 GapXEditBlockPtr filled in by PerformGappedAlignmentWithTraceback, used
258 to make a SeqAlignPtr.
259 */
260 GapXEditBlockPtr edit_block;
261 /* Another TLM kludge for display. */
262 Int4Ptr tback;
263 /* Is the search position based. */
264 Boolean positionBased;
265 Boolean posConverged;
266 Boolean is_ooframe;
267 Boolean discontinuous;
268 GapXDPPtr dyn_prog;
269 } GapAlignBlk, PNTR GapAlignBlkPtr;
270
271 GapXDropStateArrayStructPtr GapXDropStateDestroy PROTO((GapXDropStateArrayStructPtr state_struct));
272
273
274 SeqAlignPtr LIBCALL GapXEditBlockToSeqAlign PROTO((GapXEditBlockPtr edit_block, SeqIdPtr subject_id, SeqIdPtr query_id));
275 SeqAlignPtr LIBCALL OOFGapXEditBlockToSeqAlign PROTO((GapXEditBlockPtr edit_block, SeqIdPtr subject_id, SeqIdPtr query_id, Int4 query_length));
276
277 GapXEditBlockPtr LIBCALL SimpleIntervalToGapXEditBlock PROTO((Int4 start1, Int4 start2, Int4 length));
278
279 GapXEditBlockPtr LIBCALL GapXEditBlockNew PROTO((Int4 start1, Int4 start2));
280 GapXEditBlockPtr LIBCALL GapXEditBlockDelete PROTO((GapXEditBlockPtr edit_block));
281 GapXEditScriptPtr LIBCALL GapXEditScriptDelete PROTO((GapXEditScriptPtr esp));
282
283 Boolean LIBCALL PerformNtGappedAlignment PROTO((GapAlignBlkPtr gap_align));
284
285 Boolean LIBCALL PerformGappedAlignment PROTO((GapAlignBlkPtr));
286
287 Boolean LIBCALL PerformGappedAlignmentWithTraceback PROTO((GapAlignBlkPtr));
288
289 GapXEditBlockPtr LIBCALL TracebackToGapXEditBlock PROTO((Uint1Ptr A, Uint1Ptr B, Int4 M, Int4 N, Int4Ptr S, Int4 start1, Int4 start2));
290 GapXEditBlockPtr LIBCALL
291 OOFTracebackToGapXEditBlock PROTO((Int4 M, Int4 N, Int4Ptr S, Int4 start1, Int4 start2));
292
293 /*
294 Allocates GapAlignBlkPtr and "state", if state_column_length and
295 state_row_length are not NULL.
296
297 For "call and forget" applications, state_column_length and
298 state_row_length should both be set to zero. ALIGN will
299 then allocate and deallocate this memory.
300 */
301 GapAlignBlkPtr LIBCALL GapAlignBlkNew PROTO((Int4 state_column_length, Int4 state_row_length));
302
303 /*
304 Destruct Function for GapAlignBlk. If "state" is not NULL, then
305 it's deallocated.
306 */
307 GapAlignBlkPtr LIBCALL GapAlignBlkDelete PROTO((GapAlignBlkPtr gap_align));
308
309
310 Int4 SEMI_G_ALIGN PROTO((Uint1Ptr A, Uint1Ptr B, Int4 M, Int4 N,
311 Int4Ptr S, Int4Ptr pei, Int4Ptr pej,
312 Boolean score_only, Int4Ptr PNTR sapp, GapAlignBlkPtr gap_align,
313 Int4 query_offset, Boolean reversed));
314
315 Int4 LIBCALL ALIGN PROTO((Uint1Ptr A, Uint1Ptr B, Int4 M, Int4 N,
316 Int4Ptr S, Int4Ptr pei, Int4Ptr pej, Int4Ptr PNTR sapp,
317 GapAlignBlkPtr gap_align, Int4 query_offset, Boolean reversed));
318
319 GapXEditScriptPtr
320 GapXEditScriptNew PROTO((GapXEditScriptPtr old));
321
322 Boolean GXECollectDataForSeqalign PROTO((GapXEditBlockPtr edit_block,
323 GapXEditScriptPtr curr_in, Int4 numseg,
324 Int4Ptr PNTR start_out,
325 Int4Ptr PNTR length_out,
326 Uint1Ptr PNTR strands_out,
327 Int4Ptr start1, Int4Ptr start2));
328 #ifdef __cplusplus
329 }
330 #endif
331 #endif /* !__GAPXDROP__ */
332
333 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |