|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/tools/bandalg4.c |
source navigation diff markup identifier search freetext search file search |
1 static char const rcsid[] = "$Id: bandalg4.c,v 6.4 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
29 File name: bandalgn.c
30
31 Author: Gennadiy Savchuk, Jinqhui Zhang, Tom Madden
32
33 Contents: Functions to perform global banded alignment.
34
35 ****************************************************************************/
36
37 #include <bandalgn.h>
38
39 static Int4 g_band4_align(Uint1Ptr A, Uint1Ptr B,
40 Int4 M, Int4 N,
41 Int4 low, Int4 up,
42 Uint1 tb, Uint1 te,
43 Uint1 legA, Uint1 legB,
44 Uint1 regA, Uint1 regB,
45 data_t *data);
46
47 static Int4 g_band4_align_small(Uint1Ptr A, Uint1Ptr B,
48 Int4 M, Int4 N,
49 Int4 low, Int4 up,
50 Uint1 tb, Uint1 te,
51 Uint1 leA, Uint1 leB,
52 Uint1 reA, Uint1 reB,
53 data_t *data);
54
55 static Int4 g_band4_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
56 Int4 M, Int4 N,
57 Int4 PNTR S,
58 data_t *data);
59
60 /************************************************************/
61 Int4 LIBCALL gband_l3gap(Uint1Ptr A, Uint1Ptr B,
62 Int4 M, Int4 N,
63 Int4Ptr PNTR matrix,
64 PSUGapOptionsPtr option,
65 Int4Ptr S, Int4Ptr Slen)
66 {
67 data_t data;
68 Int4 c, i, j;
69 Int4 low, up;
70 Int4 band;
71 Int4 score;
72
73 /* Setup global parameters */
74 data.g = option->gopen;
75 data.zzh = option->gext;
76 data.w = matrix;
77 data.m = data.g + data.zzh;
78 data.rr = 2;
79
80 data.sapp = data.sapp0= S;
81 data.last = 0;
82 *Slen = 0;
83
84 low = option->start_diag;
85 band = option->width;
86 up = band + low - 1;
87
88 low = MIN(MAX(-M, low), MIN(N - M, 0));
89 up = MAX(MIN(N, up), MAX(N - M, 0));
90
91 if(up < 0 || low > 0) {
92 ErrPostEx(SEV_WARNING, 0, 0,
93 "The band does not include (0,0) grid point");
94 return 0;
95 }
96 if(up + M < N || low + M > N) {
97 ErrPostEx(SEV_WARNING, 0, 0,
98 "The band does not include lower corner");
99 return 0;
100 }
101
102 data.state = (Int1Ptr PNTR) MemGet(sizeof(Uint1Ptr)*(M+1), MGET_ERRPOST);
103 data.state[0] = (Int1Ptr) MemGet((M+1)*(SMBAND+2), MGET_ERRPOST);
104 for (i = 1; i <= M; i++) data.state[i] = data.state[i-1]+SMBAND+2;
105
106 if(N <= 0) {
107 if(M > 0) DEL_(M);
108 return -gap_(M);
109 }
110 if(M <= 0) {
111 INS_(N);
112 return -gap_(N);
113 }
114 if((band = up - low + 1) <= 1) {
115 c = 0;
116 for(i = 1; i <= M; i++) {
117 REP_;
118 c += data.w[A[i]][B[i]];
119 }
120 return c;
121 }
122
123 j = (band + 2) * sizeof(Int4);
124
125 data.CD = (dp_ptr) MemGet(sizeof(dp_node)*(band+2), MGET_ERRPOST);
126 j = M + 1;
127 data.MT[0] = (Uint1Ptr) MemGet(j, MGET_ERRPOST);
128 data.MT[1] = (Uint1Ptr) MemGet(j, MGET_ERRPOST);
129 data.MT[2] = (Uint1Ptr) MemGet(j, MGET_ERRPOST);
130 data.MT[3] = MemGet(j, MGET_ERRPOST);
131 data.FT = (Uint1Ptr) MemGet(j, MGET_ERRPOST);
132 j *= sizeof(Int4);
133 data.MP[0] = (Int4Ptr) MemGet(j, MGET_ERRPOST);
134 data.MP[1] = (Int4Ptr) MemGet(j, MGET_ERRPOST);
135 data.MP[2] = (Int4Ptr) MemGet(j, MGET_ERRPOST);
136 data.MP[3] = (Int4Ptr) MemGet(j, MGET_ERRPOST);
137 data.FP = (Int4Ptr) MemGet(j, MGET_ERRPOST);
138
139 data.leggA = data.leggB = data.reggA = data.reggB = data.leghA =
140 data.leghB = data.reghA = data.reghB = 0;
141
142 c = g_band4_align(A, B, M, N, low, up, 0, 0, 0, 0, 0, 0, &data);
143 score = g_band4_CHECK_SCORE( A, B, M, N, S, &data);
144
145 if (score != c) {
146 ErrPostEx(SEV_WARNING, 0, 0, "Check_Score = %ld align_score = %ld ",
147 (long) score, (long) c);
148 return 0;
149 }
150
151 /* Now deallocating memory */
152 MemFree(data.state[0]);
153 MemFree(data.state);
154 MemFree(data.CD);
155 MemFree(data.FT);
156 MemFree(data.FP);
157 for(j = 0; j < 4; j++) {
158 MemFree(data.MT[j]);
159 MemFree(data.MP[j]);
160 }
161
162 *Slen = data.sapp - S;
163
164 return c;
165 }
166
167 /************************************************************/
168 /* g_band4_align(A, B, M, N, up, low, tb, te, data) returns the cost of an
169 optimum conversion between
170 A[1..M] and B[1..N] and appends such a conversion to the current script.
171 tb(te)= 1 no gap-open penalty if the conversion begins(ends) with a delete.
172 tb(te)= 2 no gap-open penalty if the conversion begins(ends) with an insert.
173 */
174
175 static Int4 g_band4_align(Uint1Ptr A, Uint1Ptr B,
176 Int4 M, Int4 N,
177 Int4 low, Int4 up,
178 Uint1 tb, Uint1 te,
179 Uint1 legA, Uint1 legB,
180 Uint1 regA, Uint1 regB,
181 data_t *data)
182 {
183 Int4 rmid, k, l, r, v, kt, X, Y;
184 Int4 t1, t2, t3;
185 Uint1Ptr FT;
186 Int4Ptr FP;
187 {
188 Int4 band, midd, j;
189 Int4 leftd, rightd; /* for CC, DD, CP and DP */
190 register Int4 curd; /* current index for CC, DD CP and DP */
191 register Int4 i;
192 register Int4 c, d, e, x, f;
193 register dp_ptr ap;
194 Int4 t, fr;
195 Int4Ptr wa;
196 Int4 ib, best = MININT;
197
198 /* Boundary cases: M <= 0 , N <= 0, or up-low <= 0 */
199 if(N <= 0) {
200 if(M > 0) _DEL(M);
201 return 0;
202 }
203 if(M <= 0) {
204 _INS(N);
205 return 0;
206 }
207 if((band = up - low + 1) <= SMBAND) {
208 return g_band4_align_small(A, B, M, N, low, up, tb, te,
209 legA, legB, regA, regB, data);
210 }
211
212 /* Divide: Find all crossing points */
213
214 /* Initialization */
215 midd = band/2 + 1;
216 rmid = low + midd - 1;
217 leftd = 1-low;
218 rightd = up-low+1;
219 if (leftd < midd) {
220 fr = -1;
221 for (j = 0; j < midd; j++)
222 data->CD[j].CP = data->CD[j].DPDP = data->CD[j].FP = -1;
223 for (j = midd; j <= rightd; j++) {
224 data->CD[j].CP = data->CD[j].DPDP = data->CD[j].FP = 0;
225 }
226 data->CD[midd-1].DPDP = 0;
227 data->MP[0][0] = -1;
228 data->MP[1][0] = -1;
229 data->MP[2][0] = -1;
230 data->MP[3][0] = -1;
231 } else if (leftd > midd) {
232 fr = leftd-midd;
233 for (j = 0; j <= midd; j++) {
234 data->CD[j].CP = data->CD[j].DPDP = data->CD[j].FP = fr;
235 }
236 for (j = midd+1; j <= rightd; j++)
237 data->CD[j].CP = data->CD[j].DPDP = data->CD[j].FP = -1;
238 data->CD[midd].DPDP = -1;
239 data->MP[0][fr] = -1;
240 data->MP[1][fr] = -1;
241 data->MP[2][fr] = -1;
242 data->MP[3][fr] = -1;
243 } else {
244 for (j = 0; j < rightd; j++) {
245 data->CD[j].CP = data->CD[j].DPDP = data->CD[j].FP = 0;
246 }
247 data->MP[0][0] = -1;
248 data->MP[1][0] = -1;
249 data->MP[2][0] = -1;
250 data->MP[3][0] = -1;
251 }
252
253 data->CD[leftd].CC = 0; data->CD[leftd].FF = -data->g - data->rr;
254 if(!legB) {
255 t = -data->leggB;
256 for(j = leftd + 1; j <= rightd; j++) {
257 data->CD[j].CC = t = t - data->leghB;
258 data->CD[j].FF = t - data->g - data->rr;
259 data->CD[j-1].DD = t - data->m;
260 }
261 }
262 else {
263 if(tb == 2) t = 0;
264 else t = -data->g;
265 for(j = leftd + 1; j <= rightd; j++) {
266 data->CD[j].CC = t = t - data->zzh;
267 data->CD[j].FF = t - data->g - data->rr;
268 data->CD[j-1].DD = t - data->m;
269 }
270 }
271 for(j = 0; j < leftd; j++) data->CD[j].FF = MININT;
272 data->CD[rightd+1].CC = MININT;
273 data->CD[rightd].DD = MININT;
274 data->CD[rightd+1].CP = data->CD[rightd].DPDP = 0;
275 if(tb == 1) data->CD[leftd-1].DD = -data->zzh;
276 else data->CD[leftd-1].DD = -data->m;
277 if(!legA) data->CD[leftd-1].DD = -data->leggA - data->leghA;
278 data->CD[leftd-1].CC = MININT;
279 for (i = 1; i <= M; i++) {
280 if (i > N-up) rightd--;
281 if (leftd > 1) leftd--;
282 wa = data->w[A[i]];
283 d = data->CD[leftd].DD;
284 if ((ib = leftd+low-1+i) > 0) c = data->CD[leftd].CC+wa[B[ib]];
285 f = data->CD[leftd].FF;
286 if (d > c || ib <= 0) {
287 c = d;
288 data->CD[leftd].CP = data->CD[leftd].DPDP;
289 }
290 if(c < f) {
291 c = f;
292 data->CD[leftd].CP = data->CD[leftd].FP;
293 }
294 e = c - data->m;
295 data->IP = data->CD[leftd].CP;
296 if(leftd > 1 && !legA) d -= data->leghA;
297 else d -= data->zzh;
298 data->CD[leftd-1].DD = d;
299 data->CD[leftd-1].DPDP = data->CD[leftd].DPDP;
300 if(f > c - data->g) {
301 data->CD[leftd].FF -= data->rr;
302 e = f - data->zzh;
303 data->IP = data->CD[leftd].FP;
304 }
305 else {
306 data->CD[leftd].FF = c - data->g - data->rr;
307 data->CD[leftd].FP = data->CD[leftd].CP;
308 }
309 if (leftd == midd)
310 data->CD[leftd].CP = data->CD[leftd-1].DPDP = data->CD[leftd].FP =
311 data->IP = i;
312 data->CD[leftd].CC = c;
313 curd=leftd + 1;
314 ap = &data->CD[curd];
315 if(midd <= rightd && midd >= leftd + 1) x = midd;
316 else x = rightd + 1;
317 while(1) {
318 for(; curd < x; curd++) {
319 c = ap->CC + wa[B[curd + low - 1 + i]];
320 d = ap->DD;
321 f = ap->FF;
322 if(d < e) {
323 if(e > c) {
324 if(e > f) {
325 ap->CC = e;
326 e -= data->zzh;
327 ap->CP = data->IP;
328 if(f > d) {
329 (ap-1)->DD = f - data->zzh;
330 (ap-1)->DPDP = ap->FP;
331 }
332 else {
333 (ap-1)->DD = d - data->zzh;
334 (ap-1)->DPDP = ap->DPDP;
335 }
336 }
337 else {
338 ap->CC = f;
339 ap->CP = data->IP = (ap-1)->DPDP = ap->FP;
340 e = (ap-1)->DD = f - data->zzh;
341 }
342 ap++->FF -= data->rr;
343 continue;
344 }
345 } else if (d > c) {
346 if (d > f) {
347 ap->CC = d; (ap-1)->DPDP = ap->CP = ap->DPDP;
348 (ap - 1)->DD = d - data->zzh;
349 if(f > e) {
350 e = f - data->zzh;
351 data->IP = ap->FP;
352 }
353 else e -= data->zzh;
354 }
355 else {
356 ap->CC = f;
357 ap->CP = (ap - 1)->DPDP = data->IP = ap->FP;
358 e = (ap - 1)->DD = f - data->zzh;
359 }
360 ap++->FF -= data->rr;
361 continue;
362 }
363 if(c < f) {
364 ap->CC = f; ap->CP = (ap - 1)->DPDP = data->IP = ap->FP;
365 e = (ap - 1)->DD = f - data->zzh;
366 ap++->FF -= data->rr;
367 }
368 else {
369 ap->CC = c;
370 if((c -= data->g) > f) {
371 if(c > e) {
372 e = c - data->zzh;
373 ap->FP = data->IP = ap->CP;
374 }
375 else {
376 ap->FP = ap->CP;
377 e -= data->zzh;
378 }
379 if(c > d) {
380 (ap - 1)->DD = c - data->zzh;
381 (ap - 1)->DPDP = ap->CP;
382 }
383 else {
384 (ap - 1)->DD = d - data->zzh;
385 (ap - 1)->DPDP = ap->DPDP;
386 }
387 ap++->FF = c - data->rr;
388 }
389 else {
390 if (f > e) {
391 data->IP = ap->FP; e = f - data->zzh;
392 if(f > d) {
393 (ap - 1)->DD = e;
394 (ap - 1)->DPDP = data->IP;
395 }
396 else {
397 (ap - 1)->DD = d - data->zzh;
398 (ap - 1)->DPDP = ap->DPDP;
399 }
400 }
401 else {
402 e -= data->zzh;
403 if (f > d) {
404 (ap - 1)->DD = f - data->zzh;
405 (ap - 1)->DPDP = ap->FP;
406 }
407 else {
408 (ap-1)->DD = d - data->zzh;
409 (ap-1)->DPDP = ap->DPDP;
410 }
411 }
412 ap++->FF -= data->rr;
413 }
414 }
415 }
416 if(x != rightd+1) {
417 c = ap->CC + wa[B[curd+low-1+i]];
418 d = ap->DD;
419 f = ap->FF;
420 data->MP[0][i] = i - 1;
421 data->MT[0][i] = 0;
422 if(e > c) {
423 c = e;
424 data->MP[0][i] = data->IP;
425 data->MT[0][i] = 2;
426 }
427 if(f > c) {
428 c = f;
429 data->MP[0][i] = i - 1;
430 data->MT[0][i] = 3;
431 }
432 if(d > c) {
433 c = d;
434 data->MP[0][i] = ap->DPDP;
435 data->MT[0][i] = 1;
436 }
437 ap->CC = c;
438 c -= data->g;
439 if(c > f) {
440 if(c > e) {
441 e = c - data->zzh;
442 data->MP[1][i] = data->MP[0][i];
443 data->MT[1][i] = data->MT[0][i];
444 }
445 else {
446 e -= data->zzh;
447 data->MP[1][i] = data->IP;
448 data->MT[1][i] = 2;
449 }
450 if(c > d) {
451 data->MP[2][i] = data->MP[0][i];
452 data->MT[2][i] = data->MT[0][i];
453 (ap-1)->DD = c - data->zzh;
454 }
455 else {
456 data->MP[2][i] = ap->DPDP;
457 data->MT[2][i] = 1;
458 (ap-1)->DD = d - data->zzh;
459 }
460 ap->FF = c - data->rr;
461 data->MP[3][i] = data->MP[0][i];
462 data->MT[3][i] = data->MT[0][i];
463 }
464 else {
465 if(e > f) {
466 e -= data->zzh;
467 data->MP[1][i] = data->IP;
468 data->MT[1][i] = 2;
469 }
470 else {
471 e = f - data->zzh;
472 data->MP[1][i] = i - 1;
473 data->MT[1][i] = 3;
474 }
475 if(d > f) {
476 data->MP[2][i] = ap->DPDP;
477 data->MT[2][i] = 1;
478 (ap-1)->DD = d - data->zzh;
479 }
480 else {
481 data->MP[2][i] = i - 1;
482 data->MT[2][i] = 3;
483 (ap-1)->DD = f - data->zzh;
484 }
485 ap->FF -= data->rr;
486 data->MP[3][i] = i - 1;
487 data->MT[3][i] = 3;
488 }
489 ap->CP = (ap - 1)->DPDP = data->IP = ap->FP = i; ap++;
490 x = rightd + 1; curd++;
491 } else break;
492 }
493 if (!regA && i > N-up &&
494 best < (j = (ap - 1)->CC - data->reggA - (M - i) * data->reghA)) {
495 best = j; X = i; Y = N; k = (ap-1)->CP;
496 }
497 }
498 if((ap - 1)->CC > best) {
499 best = (ap - 1)->CC;
500 X = M;
501 Y = N;
502 k = (ap - 1)->CP;
503 }
504 if(!regB) {
505 for(ap = &data->CD[leftd]; ap <= &data->CD[rightd - 1]; ap++) {
506 if((j = ap->CC - data->reggB - data->reghB *
507 (x = (&data->CD[rightd] - ap))) > best) {
508 X = M;
509 best = j;
510 Y = N - x;
511 k = ap->CP;
512 }
513 }
514 }
515
516 /* decide which path to be traced back */
517 if (regA && regB) {
518 X = M; Y = N;
519 v = c = data->CD[rightd].CC; d = data->CD[rightd-1].DD;
520 if(te == 1 && d + data->m > c) {
521 k = data->CD[rightd - 1].DPDP;
522 l = 1;
523 } else if(te == 2 && e + data->m > c) {
524 k = data->IP;
525 l = 2;
526 }
527 else {
528 k = data->CD[rightd].CP;
529 l = 0;
530 }
531 }
532 else {
533 l = 0; v = best;
534 if(X != M || Y != N) regA = regB = 1;
535 }
536 if(rmid > Y - X) l = 2;
537 else if(rmid < Y - X) l = 1;
538 }
539 /* Conquer: Solve subproblems recursively */
540 /* trace back */
541 r = -1;
542 FP = (Int4Ptr) MemGet(sizeof(Int4)*(M+1), MGET_ERRPOST);
543 FT = MemGet(M+1, MGET_ERRPOST);
544 for(; k > -1; r = k, k = data->MP[l][r], l = data->MT[l][r]){
545 FP[k] = r;
546 FT[k] = (Uint1) l;
547 }
548 /* forward dividing */
549 if(r == -1) { /* optimal alignment did not cross the middle diagonal */
550 if(rmid < 0)
551 g_band4_align(A, B, X, Y, rmid + 1, up, tb, te, legA, legB, regA, regB, data);
552 else
553 g_band4_align(A, B, X, Y, low, rmid - 1, tb, te, legA, legB, regA, regB, data);
554 }
555 else {
556 k = r;
557 l = FP[k];
558 kt = FT[k];
559
560 /* first block */
561 if (rmid < 0) {
562 g_band4_align(A, B, r - 1, r + rmid, rmid + 1,
563 MIN(up, r + rmid), tb, 1, legA, legB, 1, 1, data);
564 _DEL(1);
565 legB = 1;
566 if(data->sapp > data->sapp0 + 1) legA = 1;
567 }
568 else if (rmid > 0) {
569 g_band4_align(A, B, r, r + rmid - 1,
570 MAX(-r, low), rmid - 1, tb, 2, legA, legB, 1, 1, data);
571 _INS(1);
572 legA = 1;
573 if(data->sapp > data->sapp0 + 1) legB = 1;
574 }
575 /* intermediate blocks */
576 t2 = up-rmid-1;
577 t3 = low-rmid+1;
578 for(; l > -1; k = l, l = FP[k], kt = FT[k]) {
579 if(kt == 0) _REP
580 else if(kt == 3) _REPP
581 else if(kt == 1) { /* right-hand side triangle */
582 _INS(1);
583 t1 = l - k - 1;
584 g_band4_align(A + k, B + k + rmid + 1, t1, t1, 0,
585 MIN(t1, t2), 2, 1, legA, legB, 1,1, data);
586 _DEL(1);
587 }
588 else { /* kt == 2, left-hand side triangle */
589 _DEL(1);
590 t1 = l - k - 1;
591 g_band4_align(A + k + 1, B + k + rmid, t1, t1,
592 MAX(-t1, t3), 0, 1, 2, legA, legB, 1, 1, data);
593 _INS(1);
594 }
595 legA = legB = 1;
596 }
597
598 /* last block */
599 if(Y - X > rmid) {
600 _INS(1);
601 t1 = k + rmid + 1;
602 g_band4_align(A + k, B + t1, X - k, Y - t1, 0,
603 MIN(Y - t1, t2), 2, te, legA, legB, 1, 1, data);
604 }
605 else if(Y - X < rmid) {
606 _DEL(1);
607 t1 = X - (k + 1);
608 g_band4_align(A + k + 1, B + k + rmid, t1, Y - (k + rmid),
609 MAX(-t1, t3), 0, 1, te, legA, legB, 1, 1, data);
610 }
611 }
612 if(X != M) _DEL(M-X)
613 else if(Y != N) _INS(N - Y);
614 MemFree(FP);
615 MemFree(FT);
616
617 return(v);
618 }
619
620 /************************************************************/
621 static Int4 g_band4_align_small(Uint1Ptr A, Uint1Ptr B,
622 Int4 M, Int4 N,
623 Int4 low, Int4 up,
624 Uint1 tb, Uint1 te,
625 Uint1 leA, Uint1 leB,
626 Uint1 reA, Uint1 reB,
627 data_t *data)
628 {
629 Int4 k, l, v;
630 Int4 band, j;
631 Int4 leftd, rightd; /* for CC, DD, CP and DP */
632 register Int4 curd; /* current index for CC, DD CP and DP */
633 register Int4 i;
634 register Int4 c, d, e, x, f;
635 register dp_ptr ap;
636 Int4 t;
637 Int4Ptr wa;
638 Int1Ptr st;
639 Uint1Ptr tmp;
640 Int4 ib, best=MININT, X, Y;
641 Int4 legga = data->leggA, leggb = data->leggB, regga = data->reggA,
642 reggb = data->reggB, legha = data->leghA, leghb = data->leghB,
643 regha = data->reghA, reghb = data->reghB;
644
645 if(leA) {
646 data->leggA = data->g;
647 data->leghA = data->zzh;
648 }
649 if(leB) {
650 data->leggB = data->g;
651 data->leghB = data->zzh;
652 }
653 if(reA) {
654 data->reggA = data->g;
655 data->reghA = data->zzh;
656 }
657 if(reB) {
658 data->reggB = data->g;
659 data->reghB = data->zzh;
660 }
661 /* Boundary cases: M <= 0 , N <= 0, or up-low <= 0 */
662 band = up - low + 1;
663
664 /* Initialization */
665 leftd = 1 - low;
666 rightd = up - low + 1;
667
668 data->CD[leftd].CC = 0;
669 data->state[0][leftd] = -1;
670
671 if(tb == 2) t = 0;
672 else t = -data->leggB;
673 data->CD[leftd].FF = -data->g - data->rr;
674 for(j = leftd + 1; j <= rightd; j++) {
675 data->CD[j].CC = t = t - data->leghB;
676 data->CD[j].FF = t - data->g - data->rr;
677 data->CD[j-1].DD = t - data->m;
678 data->state[0][j] = 1;
679 }
680 for(j = 0; j < leftd; j++) data->CD[j].FF = MININT;
681 data->CD[rightd+1].CC = MININT;
682 data->CD[rightd].DD = MININT;
683 if(tb == 1) data->CD[leftd - 1].DD = -data->leghA;
684 else data->CD[leftd - 1].DD = -data->leghA - data->leggA;
685 data->CD[leftd - 1].CC = MININT;
686 for(i = 1; i <= M; i++) {
687 if(i > N - up) rightd--;
688 if(leftd > 1) leftd--;
689 wa = data->w[A[i]];
690 d = data->CD[leftd].DD;
691 k = 0;
692 f = data->CD[leftd].FF;
693 if((ib = leftd + low - 1 + i) > 0) c = data->CD[leftd].CC + wa[B[ib]];
694 if(d > c || ib <= 0) {
695 c = d;
696 k = 2;
697 }
698 if(c < data->CD[leftd].FF) {
699 c= data->CD[leftd].FF;
700 k = 3;
701 }
702 e = c - data->g;
703 if(e < f) {
704 e = f - data->zzh; k += 25;
705 data->CD[leftd].FF -= data->rr;
706 }
707 else {
708 data->CD[leftd].FF = e - data->rr;
709 e -= data->zzh;
710 }
711 if(ib <= 0) {
712 data->CD[leftd - 1].DD = d - data->leghA;
713 k += 30;
714 }
715 if(d < f) k = k%30 + 60;
716 st = &data->state[i][leftd];
717 *st++ = (Uint1) k;
718 data->CD[leftd].CC = c;
719 for (curd=leftd+1, ap = &data->CD[curd]; curd <= rightd; curd++) {
720 c = ap->CC + wa[B[curd+low-1+i]];
721 if((d=ap->DD) > e) {
722 if(d > c) {
723 if(d < (f = ap->FF)) {
724 ap->CC = f; e = (ap - 1)->DD = f - data->zzh;
725 *st++ = 88;
726 }
727 else {
728 if(e < f) {
729 e = f - data->zzh;
730 *st++ = 57;
731 }
732 else {
733 e -= data->zzh;
734 *st++ = 47;
735 }
736 (ap-1)->DD = d - data->zzh;
737 ap->CC = d;
738 }
739 ap++->FF -= data->rr;
740 continue;
741 }
742 }
743 else if(e > c) {
744 if(e < (f = ap->FF)) {
745 ap->CC = f;
746 e = (ap-1)->DD = f - data->zzh;
747 *st++ = 88;
748 }
749 else {
750 ap->CC = e; e -= data->zzh;
751 if(d < f) {
752 (ap-1)->DD = f - data->zzh;
753 *st++ = 76;
754 }
755 else {
756 (ap - 1)->DD = d - data->zzh;
757 *st++ = 46;
758 }
759 }
760 ap++->FF -= data->rr;
761 continue;
762 }
763 if((f = ap->FF) > c) {
764 ap->CC = f;
765 (ap-1)->DD = e = f-data->zzh;
766 ap++->FF -= data->rr;
767 *st++ = 88;
768 } else {
769 ap->CC = c;
770 c -= data->g;
771 if (c > f) {
772 ap->FF = c-data->rr;
773 if (c > e) {e = c-data->zzh;k=0;}
774 else { e -= data->zzh; k=10;}
775 if (c > d) { (ap++-1)->DD = c-data->zzh; }
776 else { (ap++-1)->DD = d-data->zzh; k+=30;}
777 } else {
778 ap->FF -= data->rr;
779 if (f > e) {
780 if (f > d) {e = (ap++-1)->DD = f-data->zzh; k = 85;}
781 else { e = f-data->zzh; (ap++-1)->DD = d-data->zzh; k=55; }
782 } else {
783 e -= data->zzh;
784 if (f > d) {(ap++-1)->DD = f-data->zzh; k=75;}
785 else {(ap++-1)->DD = d-data->zzh; k=45;}
786 }
787 }
788 *st++= (Uint1) k;
789 }
790 }
791 if(!reA && i > N-up && best < (j = (ap - 1)->CC - data->reggA -
792 (M - i) * data->reghA)) {
793 best = j;
794 X = i;
795 Y = rightd;
796 }
797 }
798 if((ap - 1)->CC > best) {
799 best = (ap - 1)->CC;
800 X = M;
801 Y = rightd;
802 }
803 if(!reB)
804 for(ap = &data->CD[leftd]; ap <= &data->CD[rightd]; ap++) {
805 if((j = ap->CC - data->reggB - data->reghB *
806 (x = (&data->CD[rightd] - ap))) > best) {
807 X = M;
808 best = j;
809 Y = rightd - x;
810 }
811 }
812 v = best; l = 0;
813 if (reA && reB) {
814 X = M; Y = rightd;
815 v = c = (ap-1)->CC; d = (ap-2)->DD;
816 if (te == 1) {
817 l = 2;
818 } else if (te == 2) {
819 l = 1;
820 }
821 }
822 tmp = MemGet(M+N, MGET_ERRPOST);
823 for (i = X, j = Y, e=l, c = 0; i>=0; i--, c++) {
824 k = (t=data->state[i][j]) %5;
825 if (t == -1) break;
826 if (e == 1)
827 if ((t/10)%3 == 1) k = 1;
828 else if ((t/10)%3 == 2) k = 3;
829 if (e == 2)
830 if ((t/30)== 1) k = 2;
831 else if ((t/30) == 2) k = 3;
832 if (e == 3 && ((t/5)%2==1)) k = 3;
833 if (k == 1) { j--; i++;}
834 else if (k == 2) j++;
835 e = k;
836 tmp[c] = (Uint1) e;
837 }
838 for (i = c-1; i >= 0; i--)
839 switch(tmp[i]) {
840 case 0:
841 _REP;
842 break;
843 case 1:
844 _INS(1);
845 break;
846 case 2:
847 _DEL(1);
848 break;
849 case 3:
850 _REPP;
851 break;
852 }
853
854 MemFree(tmp);
855
856 if (X != M) _DEL(M - X)
857 else if (Y != rightd) _INS(rightd - Y);
858 data->leggA = legga; data->leggB = leggb;
859 data->reggA = regga; data->reggB = reggb;
860 data->leghA = legha; data->leghB = leghb;
861 data->reghA = regha; data->reghB = reghb;
862 return(v);
863 }
864
865 /* g_band4_CHECK_SCORE - return the score of the alignment stored in S */
866
867 static Int4 g_band4_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
868 Int4 M, Int4 N,
869 Int4 PNTR S, data_t *data)
870 {
871 register Int4 i, j, op;
872 Int4 score;
873
874 score = i = j = op = 0;
875 if(*S < 0 && *S != MININT) {
876 score -= data->leggA - *S * data->leghA;
877 i = i - *S++;
878 }
879 else if((*S) >0) {
880 score -= data->leggB + *S * data->leghB;
881 j = j + *S++;
882 }
883 while(i < M || j < N) {
884 op = *S++;
885 if(op == 0) score = data->w[A[++i]][B[++j]] + score;
886 else if(op == MININT) {
887 i++;
888 j++;
889 if(*(S - 2) == MININT) score -= data->rr;
890 else score -= data->g + data->rr;
891 }
892 else if(op > 0) {
893 score = score - (data->g + op * data->zzh);
894 j = j + op;
895 if(*(S - 2) == MININT) score += data->g;
896 }
897 else {
898 score = score - (data->g - op * data->zzh);
899 i = i - op;
900 if(*(S - 2)== MININT) score += data->g;
901 }
902 }
903 if(op < 0 && op != MININT)
904 score += (data->g - op * data->zzh) - (data->reggA - data->reghA * op);
905 else if(op > 0) score += (data->g + op * data->zzh) -
906 (data->reggB + data->reghB * op);
907 return(score);
908 }
909 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |