|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/tools/bandalg5.c |
source navigation diff markup identifier search freetext search file search |
1 static char const rcsid[] = "$Id: bandalg5.c,v 6.3 2003/05/30 17:25:36 coulouri Exp $";
2
3 /* ===========================================================================
4 *
5 * PUBLIC DOMAIN NOTICE
6 * National Center for Biotechnology Information
7 *
8 * This software/database is a "United States Government Work" under the
9 * terms of the United States Copyright Act. It was written as part of
10 * the author's official duties as a United States Government employee and
11 * thus cannot be copyrighted. This software/database is freely available
12 * to the public for use. The National Library of Medicine and the U.S.
13 * Government have not placed any restriction on its use or reproduction.
14 *
15 * Although all reasonable efforts have been taken to ensure the accuracy
16 * and reliability of the software and data, the NLM and the U.S.
17 * Government do not and cannot warrant the performance or results that
18 * may be obtained by using this software or data. The NLM and the U.S.
19 * Government disclaim all warranties, express or implied, including
20 * warranties of performance, merchantability or fitness for any particular
21 * purpose.
22 *
23 * Please cite the author in any work or product based on this material.
24 *
25 * ===========================================================================*/
26 /*****************************************************************************
27
28 File name: bandalgn.c
29
30 Author: Gennadiy Savchuk, Jinqhui Zhang, Tom Madden
31
32 Contents: Functions to perform both local and global banded alignments.
33
34 ****************************************************************************/
35
36 #include <bandalgn.h>
37
38 static Int4 g_band5_align(Uint1Ptr A, Uint1Ptr B,
39 Int4 M, Int4 N,
40 Int4 low, Int4 up,
41 data_t *data);
42
43 static Int4 g_band5_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
44 Int4 M, Int4 N,
45 Int4 PNTR S,
46 data_t *data);
47
48 /************************************************************/
49 Int4 LIBCALL gband_q3gap(Uint1Ptr A, Uint1Ptr B,
50 Int4 M, Int4 N,
51 Int4Ptr PNTR matrix,
52 PSUGapOptionsPtr option,
53 Int4Ptr S, Int4Ptr Slen)
54 {
55 data_t data;
56 Int4 c, i, j;
57 Int4 low, up;
58 Int4 band;
59 Int4 score;
60
61 data.g = option->gopen;
62 data.zzh = option->gext;
63 data.w = matrix; /* Setup global parameters */
64 data.m = data.g + data.zzh;
65 data.rr = 2;
66
67 data.sapp = S;
68 data.last = 0;
69 *Slen = 0;
70
71 low = option->start_diag;
72 band = option->width;
73 up = band + low - 1;
74
75 low = MIN(MAX(-M, low), MIN(N - M, 0));
76 up = MAX(MIN(N, up), MAX(N - M, 0));
77
78 if (up < 0 || low > 0) {
79 ErrPostEx(SEV_WARNING, 0, 0, "The band does not include (0,0) grid point");
80 return 0;
81 }
82 if (up + M < N || low + M > N) {
83 ErrPostEx(SEV_WARNING, 0, 0, "The band does not include lower corner");
84 return 0;
85 }
86
87 if (N <= 0) {
88 if (M > 0) DEL_(M);
89 return -gap_(M);
90 }
91 if (M <= 0) {
92 INS_(N);
93 return -gap_(N);
94 }
95 if ((band = up-low+1) <= 1) {
96 c = 0;
97 for (i = 1; i <= M; i++) {
98 REP_;
99 c += data.w[A[i]][B[i]];
100 }
101 return c;
102 }
103
104 j = (band+2) * sizeof(Int4);
105 data.leggA = data.leggB = data.reggA = data.reggB =
106 data.leghA = data.leghB = data.reghA = data.reghB = 0;
107 data.CD = (dp_ptr) MemGet(sizeof(dp_node) * (band + 2), MGET_ERRPOST);
108
109 c = g_band5_align(A, B, M, N, low, up, &data);
110
111 score = g_band5_CHECK_SCORE( A, B, M, N, S, &data);
112 if (score != c) {
113 ErrPostEx(SEV_WARNING, 0, 0, "Check_Score = %ld align_score = %ld ",
114 (long) score, (long) c);
115 return 0;
116 }
117 MemFree(data.CD);
118
119 *Slen = data.sapp - S;
120
121 return c;
122 }
123
124 /* g_band5_align(A,B,M,N,up,low,tb,te, data) returns the cost of an optimum
125 conversion between
126 A[1..M] and B[1..N] and appends such a conversion to the current script.
127 tb(te)= 1 no gap-open penalty if the conversion begins(ends) with a delete.
128 tb(te)= 2 no gap-open penalty if the conversion begins(ends) with an insert.
129 */
130 static Int4 g_band5_align(Uint1Ptr A, Uint1Ptr B,
131 Int4 M, Int4 N,
132 Int4 low, Int4 up,
133 data_t *data)
134 {
135 Int4 k, v;
136 Int4 band, j;
137 Int4 leftd, rightd; /* for CC, DD, CP and DP */
138 register Int4 curd; /* current index for CC, DD CP and DP */
139 register Int4 i;
140 register Int4 c, d, e, x, f;
141 register dp_ptr ap;
142 Int4 t;
143 Int4Ptr wa;
144 Int1Ptr PNTR state, st;
145 Uint1Ptr tmp;
146 Int4 ib, best=MININT, X, Y;
147
148 /* Boundary cases: M <= 0 , N <= 0, or up-low <= 0 */
149 band = up - low + 1;
150 state = (Int1Ptr PNTR) MemGet(sizeof(Uint1 *) * (M + 1), MGET_ERRPOST);
151 state[0] = (Int1Ptr) MemGet((M + 1) * (band + 2), MGET_ERRPOST);
152 for(i = 1; i <= M; i++) state[i] = state[i - 1] + band + 2;
153
154 /* Initialization */
155 leftd = 1-low;
156 rightd = up-low+1;
157
158 data->CD[leftd].CC = 0; state[0][leftd] = -1;
159
160 t = -data->leggB;
161 data->CD[leftd].FF = -data->g - data->rr;
162 for(j = leftd + 1; j <= rightd; j++) {
163 data->CD[j].CC = t = t - data->leghB;
164 data->CD[j].FF = t - data->g - data->rr;
165 data->CD[j-1].DD = t - data->m;
166 state[0][j] = 1;
167 }
168 for(j = 0; j < leftd; j++) data->CD[j].FF = MININT;
169 data->CD[rightd+1].CC = MININT;
170 data->CD[rightd].DD = MININT;
171 data->CD[leftd-1].DD = -data->leggA;
172 data->CD[leftd-1].CC = MININT;
173 for (i = 1; i <= M; i++) {
174 if (i > N-up) rightd--;
175 if (leftd > 1) leftd--;
176 wa = data->w[A[i]];
177 d = data->CD[leftd].DD;
178 k = 0;
179 if ((ib = leftd+low-1+i) > 0) c = data->CD[leftd].CC+wa[B[ib]];
180 if (d > c || ib <= 0) {
181 c = d;
182 k = 2;
183 }
184 if(c < data->CD[leftd].FF) { c= data->CD[leftd].FF; k = 3;}
185 e = c - data->m;
186 if(e < data->CD[leftd].FF - data->zzh) {
187 e = data->CD[leftd].FF - data->zzh;
188 k += 20;
189 }
190 if (c-data->g > data->CD[leftd].FF) {data->CD[leftd].FF = c-data->g-data->rr;}
191 else {data->CD[leftd].FF -= data->rr; k+=5;}
192 if (ib <= 0) {
193 data->CD[leftd-1].DD = d - data->leghA;
194 k += 30;
195 }
196 st = &state[i][leftd];
197 *st++ = (Uint1) k;
198 data->CD[leftd].CC = c;
199 for(curd=leftd+1, ap = &data->CD[curd]; curd <= rightd; curd++) {
200 c = ap->CC + wa[B[curd+low-1+i]];
201 if((d = ap->DD) > e) {
202 if(d > c) {
203 if(d < (f = ap->FF)) {
204 ap->CC = f;
205 e = (ap - 1)->DD = f - data->zzh;
206 *st++ = 88;
207 }
208 else {
209 if(e < f) {
210 e = f - data->zzh;
211 *st++ = 57;
212 }
213 else {
214 e -= data->zzh;
215 *st++ = 47;
216 }
217 (ap - 1)->DD = d - data->zzh;
218 ap->CC = d;
219 }
220 ap++->FF -= data->rr;
221 continue;
222 }
223 } else if(e > c) {
224 if(e < (f = ap->FF)) {
225 ap->CC = f;
226 e = (ap - 1)->DD = f - data->zzh;
227 *st++ = 88;
228 }
229 else {
230 ap->CC = e;
231 e -= data->zzh;
232 if(d < f) {
233 (ap-1)->DD = f - data->zzh;
234 *st++ = 76;
235 }
236 else {
237 (ap-1)->DD = d - data->zzh;
238 *st++ = 46;
239 }
240 }
241 ap++->FF -= data->rr;
242 continue;
243 }
244 if((f = ap->FF) > c) {
245 ap->CC = f;
246 (ap-1)->DD = e = f-data->zzh;
247 ap++->FF -= data->rr;
248 *st++ = 88;
249 } else {
250 ap->CC = c;
251 c -= data->g;
252 if (c > f) {
253 ap->FF = c-data->rr;
254 if (c > e) {e = c-data->zzh;k=0;}
255 else { e -= data->zzh; k=10;}
256 if (c > d) { (ap++-1)->DD = c-data->zzh; }
257 else { (ap++-1)->DD = d-data->zzh; k+=30;}
258 } else {
259 ap->FF -= data->rr;
260 if (f > e) {
261 if (f > d) {e = (ap++-1)->DD = f-data->zzh; k = 85;}
262 else { e = f-data->zzh; (ap++-1)->DD = d-data->zzh; k=55; }
263 } else {
264 e -= data->zzh;
265 if (f > d) {(ap++-1)->DD = f-data->zzh; k=75;}
266 else {(ap++-1)->DD = d-data->zzh; k=45;}
267 }
268 }
269 *st++= (Uint1) k;
270 }
271 }
272 if(i > N - up && best < (j = (ap - 1)->CC - data->reggA - (N - i) *
273 data->reghA)) {
274 best = j;
275 X = i;
276 Y = rightd;
277 }
278 }
279 for(ap = &data->CD[leftd]; ap <= &data->CD[rightd]; ap++) {
280 if((j = ap->CC - data->reggB - data->reghB *
281 (x = (&data->CD[rightd] - ap))) > best) {
282 X = M;
283 best = j;
284 Y = rightd - x;
285 }
286 }
287 v = best;
288 tmp = MemGet(M + N, MGET_ERRPOST);
289 for (i = X, j = Y, e=0, c = 0; i>=0; i--, c++) {
290 k = (t=state[i][j]) %5;
291 if (t == -1) break;
292 if (e == 1)
293 if ((t/10)%3 == 1) k = 1;
294 else if ((t/10)%3 == 2) k = 3;
295 if (e == 2)
296 if ((t/30)== 1) k = 2;
297 else if ((t/30) == 2) k = 3;
298 if (e == 3 && ((t/5)%2==1)) k = 3;
299 if (k == 1) { j--; i++;}
300 else if (k == 2) j++;
301 e = k;
302 tmp[c] = (Uint1) e;
303 }
304 for (i = c-1; i >= 0; i--)
305 switch(tmp[i]) {
306 case 0:
307 _REP;
308 break;
309 case 1:
310 _INS(1);
311 break;
312 case 2:
313 _DEL(1);
314 break;
315 case 3:
316 _REPP;
317 break;
318 }
319 if (X != M) _DEL(M - X);
320 if (Y != rightd) _INS(rightd - Y);
321
322 MemFree(tmp);
323 MemFree(state[0]);
324 MemFree(state);
325 return(v);
326 }
327
328
329 /* g_band5_CHECK_SCORE - return the score of the alignment stored in S */
330
331 static Int4 g_band5_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
332 Int4 M, Int4 N,
333 Int4 PNTR S,
334 data_t *data)
335 {
336 register Int4 i, j, op;
337 Int4 score;
338
339 score = i = j = op = 0;
340 if (*S < 0 && *S != MININT) {
341 score -= data->leggA - *S * data->leghA;
342 i = i - *S++;
343 }
344 else if((*S) >0) {
345 score -= data->leggB + *S * data->leghB;
346 j = j + *S++;
347 }
348 while(i < M || j < N) {
349 op = *S++;
350 if (op == 0)
351 score = data->w[A[++i]][B[++j]] + score;
352 else if(op == MININT) {
353 i++;
354 j++;
355 if(*(S - 2) == MININT) score -= data->rr;
356 else score -= data->g + data->rr;
357 }
358 else if(op > 0) {
359 score = score - (data->g+op*data->zzh);
360 j = j + op;
361 if(*(S - 2) == MININT) score += data->g;
362 }
363 else {
364 score = score - (data->g - op * data->zzh);
365 i = i - op;
366 if(*(S - 2)== MININT) score += data->g;
367 }
368 }
369 if(op < 0 && op != MININT)
370 score += (data->g - op * data->zzh) - (data->reggA - data->reghA * op);
371 else if(op > 0)
372 score += (data->g + op * data->zzh) - (data->reggB + data->reghB * op);
373 return(score);
374 }
375 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |