|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/tools/bandalg3.c |
source navigation diff markup identifier search freetext search file search |
1 static char const rcsid[] = "$Id: bandalg3.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: bandalg3.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_band3_align(Uint1Ptr A, Uint1Ptr B,
40 Int4 M, Int4 N,
41 Int4 low, Int4 up, data_t *data);
42
43 static Int4 g_band3_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
44 Int4 M, Int4 N,
45 Int4 PNTR S, data_t *data);
46
47 Int4 LIBCALL gband_linear_qgap(Uint1Ptr A, Uint1Ptr B,
48 Int4 M, Int4 N,
49 Int4Ptr PNTR matrix,
50 PSUGapOptionsPtr option,
51 Int4Ptr S, Int4Ptr Slen)
52 {
53 data_t data;
54 Int4 c, i, j;
55 Int4 low, up;
56 Int4 band;
57 Int4 score;
58
59 /* Setup global parameters */
60 data.g = option->gopen;
61 data.zzh = option->gext;
62 data.w = matrix;
63 data.m = data.g + data.zzh;
64
65 data.sapp = S;
66 data.last = 0;
67 *Slen = 0;
68
69 low = option->start_diag;
70 band = option->width;
71 up = band + low - 1;
72
73 low = MIN(MAX(-M, low),MIN(N-M,0));
74 up = MAX(MIN(N, up),MAX(N-M,0));
75
76 if(up < 0 || low > 0) {
77 ErrPostEx(SEV_WARNING, 0, 0,
78 "The band does not include (0,0) grid point");
79 return 0;
80 }
81 if(up+M < N || low+M > N) {
82 ErrPostEx(SEV_WARNING, 0, 0,
83 "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 = data.leghA =
106 data.leghB = data.reghA = data.reghB = 0;
107
108 data.CD = (dp_ptr)MemGet(sizeof(dp_node) * (band + 2), MGET_ERRPOST);
109
110 /* if((c = g_band3_align(A,B,M,N,low,up,0,0)) != (score = g_band3_CHECK_SCORE(A,B,M,N,S))) */
111 c = g_band3_align(A, B, M, N, low, up, &data);
112 score = g_band3_CHECK_SCORE(A, B, M, N, S, &data);
113 if(c != score) {
114 ErrPostEx(SEV_WARNING, 0, 0, "Check_Score = %ld align_score = %ld ",
115 (long) score, (long) c);
116 return 0;
117 }
118 MemFree(data.CD);
119
120 *Slen = data.sapp - S;
121
122 return c;
123 }
124
125 /* g_band3_CHECK_SCORE - return the score of the alignment stored in S */
126
127 static Int4 g_band3_CHECK_SCORE(Uint1Ptr A, Uint1Ptr B,
128 Int4 M, Int4 N,
129 Int4 PNTR S, data_t *data)
130 {
131 register Int4 i, j, op;
132 Int4 score;
133
134 score = i = j = op = 0;
135 if (*S < 0) {
136 score -= data->leggA - *S * data->leghA;
137 i = i - *S++;
138 } else if ((*S) > 0) {
139 score -= data->leggB + *S * data->leghB;
140 j = j + *S++;
141 }
142 while (i < M || j < N) {
143 op = *S++;
144 if(op == 0)
145 score = data->w[A[++i]][B[++j]] + score;
146 else if(op > 0) {
147 score = score - (data->g + op * data->zzh);
148 j = j + op;
149 }
150 else {
151 score = score - (data->g - op * data->zzh);
152 i = i - op;
153 }
154 }
155 if(op < 0)
156 score += (data->g - op * data->zzh) - (data->reggA - data->reghA * op);
157 else if(op > 0)
158 score += (data->g + op * data->zzh) - (data->reggB + data->reghB * op);
159
160
161 return(score);
162 }
163
164
165 /* g_band3_align(A, B, M, N, up, low, tb, te, data) returns the cost
166 of an optimum conversion between
167 A[1..M] and B[1..N] and appends such a conversion to the current script.
168 tb(te)= 1 no gap-open penalty if the conversion begins(ends) with a delete.
169 tb(te)= 2 no gap-open penalty if the conversion begins(ends) with an insert.
170 */
171 static Int4 g_band3_align(Uint1Ptr A, Uint1Ptr B,
172 Int4 M, Int4 N,
173 Int4 low, Int4 up, data_t *data)
174 {
175 Int4 k, v;
176 Int4 band, j;
177 Int4 leftd, rightd; /* for CC, DD, CP and DP */
178 register Int4 curd; /* current index for CC, DD CP and DP */
179 register Int4 i;
180 register Int4 c, d, e, x;
181 register dp_ptr ap;
182 Int4 t;
183 Int4Ptr wa;
184 Int1Ptr PNTR state, st, tmp;
185 Int4 ib, best=MININT, X, Y;
186
187
188 /* Boundary cases: M <= 0 , N <= 0, or up-low <= 0 */
189 band = up - low + 1;
190 state = (Int1Ptr PNTR) MemGet(sizeof(Int1Ptr)*(M+1), MGET_ERRPOST);
191 state[0] = (Int1Ptr) MemGet((M+1)*(band+2), MGET_ERRPOST);
192 for (i = 1; i <= M; i++) state[i] = state[i-1]+band+2;
193
194 /* Initialization */
195 leftd = 1-low;
196 rightd = up-low+1;
197
198 data->CD[leftd].CC = 0; state[0][leftd] = -1;
199
200 t = -data->leggB;
201 for(j = leftd + 1; j <= rightd; j++) {
202 data->CD[j].CC = t = t - data->leghB;
203 data->CD[j-1].DD = t - data->m;
204 state[0][j] = 1;
205 }
206 data->CD[rightd+1].CC = MININT;
207 data->CD[rightd].DD = MININT;
208 data->CD[leftd-1].DD = -data->leggA;
209 data->CD[leftd-1].CC = MININT;
210 for (i = 1; i <= M; i++) {
211 if (i > N-up) rightd--;
212 if (leftd > 1) leftd--;
213 wa = data->w[A[i]];
214 d = data->CD[leftd].DD;
215 k = 0;
216 if ((ib = leftd+low-1+i) > 0) c = data->CD[leftd].CC+wa[B[ib]];
217 if (d > c || ib <= 0) {
218 c = d;
219 k = 2;
220 }
221 e = c - data->m;
222 if(ib <= 0) {
223 data->CD[leftd - 1].DD = d - data->leghA;
224 k += 20;
225 }
226 st = &state[i][leftd];
227 *st++ = (Int1) k;
228 data->CD[leftd].CC = c;
229 for(curd = leftd + 1, ap = &data->CD[curd]; curd <= rightd; curd++) {
230 c = ap->CC + wa[B[curd + low - 1 + i]];
231 if((d = ap->DD) > c) {
232 if(d > e) {
233 ap->CC = d;
234 *st++ =32;
235 }
236 else {
237 ap->CC = e;
238 *st++=31;
239 }
240 e -= data->zzh;
241 (ap++ - 1)->DD = d - data->zzh;
242 }
243 else if (e > c) {
244 ap->CC = e;
245 e -= data->zzh;
246 (ap++ - 1)->DD = d - data->zzh;
247 *st++ = 31;
248 }
249 else {
250 ap->CC = c;
251 if((c -= data->m) > (e -= data->zzh)) {
252 if(c > (d -= data->zzh)) {
253 (ap++ - 1)->DD = e = c;
254 *st++ = 0;
255 }
256 else {
257 e = c;
258 (ap++ - 1)->DD = d;
259 *st++ = 20;
260 }
261 }
262 else {
263 if(c > (d -= data->zzh)) {
264 (ap++ - 1)->DD = c;
265 *st++ = 10;
266 }
267 else {
268 (ap++ - 1)->DD = d;
269 *st++ = 30;
270 }
271 }
272 }
273 }
274 if(i > N-up &&
275 best < (j = (ap - 1)->CC - data->reggA - (N - i) * data->reghA)) {
276 best = j; X = i; 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)))
282 > best) {
283 X = M;
284 best = j;
285 Y = rightd - x;
286 }
287 }
288 if (data->CD[rightd].CC > best) {X=M; Y= N; best = data->CD[rightd].CC;}
289 v= best;
290 tmp = MemGet(M+N, MGET_ERRPOST);
291 for (i = X, j = Y, e=0, c = 0; i>=0; i--, c++) {
292 k = (t=state[i][j]) %10;
293 if (t == -1) break;
294 if (e == 1 && (t/10)%2 == 1) k = 1;
295 if (e == 2 && (t/20)== 1) k = 2;
296 if (k == 1) { j--; i++;}
297 else if (k == 2) j++;
298 e = k;
299 tmp[c] = (Int1) e;
300 }
301 for (i = c-1; i >= 0; i--)
302 switch(tmp[i]) {
303 case 0:
304 _REP;
305 break;
306 case 1:
307 _INS(1);
308 break;
309 case 2:
310 _DEL(1);
311 break;
312 }
313 if(X != M) _DEL(M - X)
314 else if(Y != rightd) _INS(rightd-Y)
315
316 MemFree(state[0]);
317 MemFree(state);
318 MemFree(tmp);
319 return(v);
320 }
321
322
323 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |