NCBI C++ ToolKit
thrdslo0.c
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: thrdslo0.c 32839 2007-03-05 20:41:55Z kazimird $
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 Name: thrdslo0.c
27 *
28 * Author: Stephen Bryant
29 *
30 * Initial Version Creation Date: 08/16/2000
31 *
32 * $Revision: 32839 $
33 *
34 * File Description: threader
35 */
36 
37 
38 
39 #include <stdlib.h>
42 
43 /*----------------------------------------------------------------------------*/
44 /* Find constraints on the initial extent of the n- or c-terminus of a core */
45 /* element, given elements already located, the length of the query sequence, */
46 /* and any explicit alignment constraints. Aside from explict constraints */
47 /* the query sequence is assumed to be as yet unaligned with the core folding */
48 /* motif. The constraints on element termini extents are therefore derived */
49 /* from the overall length of the query sequence, as compared to the lengths */
50 /* of core elements already located, and the minimum lengths of loops and */
51 /* core elements not yet located. Explicit alignment constraints may further */
52 /* limit possible locations, by restricting the region of the query sequence */
53 /* in which remaining core segments must be placed. Extent constraints as */
54 /* specified in the core definition are also considered, and the returned */
55 /* minimum and maxixum core segment terminus locations will fall within these */
56 /* limits. */
57 /*----------------------------------------------------------------------------*/
58 /* A return code of zero indicates that no valid extent could be found, i.e. */
59 /* that the query sequence is too short to allow placement of the the current */
60 /* core segment, even at its minimum length. */
61 /*----------------------------------------------------------------------------*/
62 
63 int slo0(Fld_Mtf* mtf, Cor_Def* cdf, Qry_Seq* qsq, Cur_Loc* sli,
64  int cs, int ct, int* mn, int* mx) {
65 /*----------------------------------------------------------*/
66 /* mtf: Contact matrices defining the folding motif */
67 /* cdf: Contains min/max segment locations */
68 /* qsq: Sequence to thread with alignment contraints */
69 /* sli: Contains segment location values to be set */
70 /* cs: Index of core segment to locate */
71 /* ct: Flag indicating the n or c-terminus */
72 /* mn: Minimum folding motif index for this terminus */
73 /* mx: Maximum folding motif index for this terminus */
74 /*----------------------------------------------------------*/
75 
76  int i; /* Counters */
77  int nsc; /* Number of core segments */
78  int sl; /* Segment length */
79  int ec; /* Alignment limit due to explicit constraint */
80  int lm1,lm2; /* Loop length limits */
81  int ntmn,ntmx; /* Alignment limit due to n-terminal segments */
82  int ctmn,ctmx; /* Alignment limit due to c-terminal segments */
83  int *no,*co; /* Left and right offsets of core segment terminii */
84  int qmn,qmx; /* Combined alignment limits */
85 
86 
87 /*----------------------------------------------------------------------------*/
88 /* Allocate local storage for segment extents */
89 /*----------------------------------------------------------------------------*/
90  nsc=cdf->sll.n;
91  no=(int *)calloc(nsc,sizeof(int));
92  co=(int *)calloc(nsc,sizeof(int));
93 
94 #ifdef SLO0_DEBUG
95  printf("cs: %d ct: %d\n",cs,ct);
96  for(i=0; i<nsc; i++) printf("%d ",qsq->sac.mn[i]); printf("qsq->sac.mn\n");
97  for(i=0; i<nsc; i++) printf("%d ",qsq->sac.mx[i]); printf("qsq->sac.mx\n");
98 #endif
99 
100 /*----------------------------------------------------------------------------*/
101 /* Assume minimum extents for segments not yet located */
102 /*----------------------------------------------------------------------------*/
103  for(i=0;i<nsc;i++) {
104  no[i]=(sli->no[i]<0) ? cdf->sll.nomn[i] : sli->no[i];
105  co[i]=(sli->co[i]<0) ? cdf->sll.comn[i] : sli->co[i];
106  }
107 
108 #ifdef SLO0_DEBUG
109  for(i=0;i<nsc;i++) printf("%d ",no[i]); printf("no\n");
110  for(i=0;i<nsc;i++) printf("%d ",co[i]); printf("co\n");
111 #endif
112 
113 /*----------------------------------------------------------------------------*/
114 /* Find alignment constraints arising from segments n-terminal to this one. */
115 /* These are indices of the most c-terminal query sequence residue which must */
116 /* be assigned to an n-terminal element or loop. The minimum index assumes */
117 /* minimum loop lengths and explicitly constrained segments at their most */
118 /* n-terminal positions. The maximum index assumes maximum loop lengths and */
119 /* explicitly constrained segments at their most c-terminal positions. */
120 /*----------------------------------------------------------------------------*/
121 /* Allow for the minimum length of a tail */
122 /*----------------------------------------------------------------------------*/
123  ntmn=-1+cdf->lll.llmn[0];
124 
125 /*----------------------------------------------------------------------------*/
126 /* Initialize the maximum alignment allowed by n-terminal segments to the */
127 /* end of the sequence. They constrain alignment only if an n-terminal */
128 /* segment is explicitly constrained. */
129 /*----------------------------------------------------------------------------*/
130  ntmx=qsq->n;
131 
132 /*----------------------------------------------------------------------------*/
133 /* Loop over n-terminal segments */
134 /*----------------------------------------------------------------------------*/
135 #ifdef SLO0_DEBUG
136  printf("initial ntmn:%d initial ntmx:%d\n",ntmn,ntmx);
137 #endif
138  for(i=0; i<cs; i++) {
139 
140 /*----------------------------------------------------------------------------*/
141 /* Add segment length */
142 /*----------------------------------------------------------------------------*/
143  sl=no[i]+co[i]+1;
144  ntmn+=sl;
145  ntmx+=sl;
146 #ifdef SLO0_DEBUG
147  printf("sl:%d ntmn:%d ntmx:%d\n",sl,ntmn,ntmx);
148 #endif
149 
150 /*----------------------------------------------------------------------------*/
151 /* Reset limits to reflect any explicit constraints */
152 /*----------------------------------------------------------------------------*/
153  if(qsq->sac.mn[i]>0) {
154  ec=qsq->sac.mn[i]+co[i];
155  ntmn=(ec>ntmn) ? ec : ntmn;
156 #ifdef SLO0_DEBUG
157  printf("ec:%d ntmn:%d\n",ec,ntmn);
158 #endif
159  }
160  if(qsq->sac.mx[i]>0) {
161  ec=qsq->sac.mx[i]+co[i];
162  ntmx=(ec>ntmx) ? ec : ntmx;
163 #ifdef SLO0_DEBUG
164  printf("ec:%d ntmx:%d\n",ec,ntmx);
165 #endif
166  }
167 
168 /*----------------------------------------------------------------------------*/
169 /* Add lengths of the following loop */
170 /*----------------------------------------------------------------------------*/
171  lm1=mtf->mll[cdf->sll.rfpt[i]+co[i]][cdf->sll.rfpt[i+1]-no[i+1]];
172  lm2=cdf->lll.llmn[i+1];
173  ntmn+= (lm1>lm2) ? lm1 : lm2;
174 #ifdef SLO0_DEBUG
175  printf("lm1:%d lm2:%d ntmn:%d\n",lm1,lm2,ntmn);
176 #endif
177  lm2=cdf->lll.llmx[i+1];
178  ntmx+= (lm1>lm2) ? lm1 : lm2;
179 #ifdef SLO0_DEBUG
180  printf("lm1:%d lm2:%d ntmx:%d\n",lm1,lm2,ntmx);
181 #endif
182  }
183 
184 /*----------------------------------------------------------------------------*/
185 /* Add n-terminal offset of current segment to give alignment limits */
186 /*----------------------------------------------------------------------------*/
187  ntmn+=no[cs]+1;
188  ntmx+=no[cs]+1;
189 #ifdef SLO0_DEBUG
190  printf("final ntmn: %d final ntmx: %d\n",ntmn,ntmx);
191 #endif
192 
193 /*----------------------------------------------------------------------------*/
194 /* Find alignment constraints arising from segments c-terminal to this one. */
195 /*----------------------------------------------------------------------------*/
196 /* Allow for the minimum length of a tail */
197 /*----------------------------------------------------------------------------*/
198  ctmx=qsq->n-cdf->lll.llmn[nsc];
199 
200 /*----------------------------------------------------------------------------*/
201 /* Initialize the minimum alignment allowed by c-terminal segments to the */
202 /* start of the sequence. They constrain alignment only one of the */
203 /* c-terminal segments is already aligned or explicitly constrained. */
204 /*----------------------------------------------------------------------------*/
205  ctmn=-1;
206 
207 /*----------------------------------------------------------------------------*/
208 /* Loop over all c-terminal segments */
209 /*----------------------------------------------------------------------------*/
210 #ifdef SLO0_DEBUG
211  printf("initial ctmn:%d initial ctmx:%d\n",ctmn,ctmx);
212 #endif
213  for(i=nsc-1; i>cs; i--) {
214 /*----------------------------------------------------------------------------*/
215 /* Subtract segment length */
216 /*----------------------------------------------------------------------------*/
217  sl=no[i]+co[i]+1;
218  ctmn-=sl;
219  ctmx-=sl;
220 #ifdef SLO0_DEBUG
221  printf("sl:%d ctmn:%d ctmx:%d\n",sl,ctmn,ctmx);
222 #endif
223 
224 /*----------------------------------------------------------------------------*/
225 /* Reset limits to reflect any explicit constraints */
226 /*----------------------------------------------------------------------------*/
227  if(qsq->sac.mn[i]>0) {
228  ec=qsq->sac.mn[i]-no[i];
229  ctmn=(ec>ctmn) ? ec : ctmn;
230 #ifdef SLO0_DEBUG
231  printf("ec:%d ctmn:%d\n",ec,ctmn);
232 #endif
233  }
234  if(qsq->sac.mx[i]>0) {
235  ec=qsq->sac.mx[i]-no[i];
236  ctmx=(ec<ctmx) ? ec : ctmx;
237 #ifdef SLO0_DEBUG
238  printf("ec:%d ctmx:%d\n",ec,ctmx);
239 #endif
240  }
241 
242 /*----------------------------------------------------------------------------*/
243 /* Subtract lengths of the preceeding loop */
244 /*----------------------------------------------------------------------------*/
245  lm1=mtf->mll[cdf->sll.rfpt[i-1]+co[i-1]][cdf->sll.rfpt[i]-no[i]];
246  lm2=cdf->lll.llmn[i];
247  ctmx-= (lm1>lm2) ? lm1 : lm2;
248 #ifdef SLO0_DEBUG
249  printf("lm1:%d lm2:%d ctmx:%d\n",lm1,lm2,ctmx);
250 #endif
251  lm2=cdf->lll.llmx[i];
252  ctmn-= (lm1>lm2) ? lm1 : lm2;
253 #ifdef SLO0_DEBUG
254  printf("lm1:%d lm2:%d ctmn:%d\n",lm1,lm2,ctmn);
255 #endif
256  }
257 
258 /*----------------------------------------------------------------------------*/
259 /* Subtract c-terminal offset of current segment to give alignment limits */
260 /*----------------------------------------------------------------------------*/
261  ctmn-=co[cs]+1;
262  ctmx-=co[cs]+1;
263 #ifdef SLO0_DEBUG
264  printf("final ctmn:%d final ctmx:%d\n",ctmn,ctmx);
265 #endif
266 
267 /*----------------------------------------------------------------------------*/
268 /* Signal an error if no alignment falls within the limits identified. */
269 /* This means the core motif is too big to be threaded by the query sequence. */
270 /*----------------------------------------------------------------------------*/
271  if(ntmn>ctmx||ntmx<ctmn) return(0);
272 
273 /*----------------------------------------------------------------------------*/
274 /* Reconcile n-terminal and c-terminal aligment limits */
275 /*----------------------------------------------------------------------------*/
276  qmn=(ntmn>ctmn) ? ntmn : ctmn;
277  qmx=(ntmx<ctmx) ? ntmx : ctmx;
278 #ifdef SLO0_DEBUG
279  printf("qmn: %d qmx: %d\n",qmn,qmx);
280 #endif
281 
282 /*----------------------------------------------------------------------------*/
283 /* Further reconcile any explict limits on the current segment alignment, */
284 /* and signal an error if these constraints cannot be satisfied. */
285 /*----------------------------------------------------------------------------*/
286 
287 #ifdef SLO0_DEBUG
288  printf("qsq->sac.mn[%d]: %d\n",cs,qsq->sac.mn[cs]);
289 #endif
290 
291  if(qsq->sac.mn[cs]>=0) {
292  lm1=qsq->sac.mn[cs];
293  if(lm1>qmx) return(0);
294  }
295 /*----------------------------------------------------------------------------*/
296 /* if(lm1>qmn) qmn=lm1;} */
297 /*----------------------------------------------------------------------------*/
298 #ifdef SLO0_DEBUG
299  printf("qsq->sac.mx[%d]: %d\n",cs,qsq->sac.mx[cs]);
300 #endif
301  if(qsq->sac.mx[cs]>=0) {
302  lm1=qsq->sac.mx[cs];
303  if(lm1<qmn) return(0); }
304 /*----------------------------------------------------------------------------*/
305 /* if(lm1<qmx) qmx=lm1; } */
306 /*----------------------------------------------------------------------------*/
307 /*----------------------------------------------------------------------------*/
308 /* The maximum change in extent of the current core segment above it's */
309 /* assumed minimal extent is the width of the alignment window. */
310 /*----------------------------------------------------------------------------*/
311  sl=qmx-qmn;
312 #ifdef SLO0_DEBUG
313  printf("sl: %d\n",sl);
314 #endif
315 
316 /*----------------------------------------------------------------------------*/
317 /* If this is negative the current segment cannot be fitted onto the query */
318 /* sequence, even at it's minimum extent. Return a zero error code. */
319 /*----------------------------------------------------------------------------*/
320  if(sl<0) return(0);
321 
322 /*----------------------------------------------------------------------------*/
323 /* Define limits on of the current terminus using the maximum change in */
324 /* extent. If this is greater than the maximum extent specified in the core */
325 /* definition, set it to the latter. Return the minimum extent as */
326 /* specified in the core definition, and the maximum extent as determined. */
327 /*----------------------------------------------------------------------------*/
328  switch(ct) {
329  case 0:{
330  *mn=cdf->sll.nomn[cs];
331  *mx=cdf->sll.nomx[cs];
332  if((sl+(*mn))<*mx) *mx=sl+(*mn);
333 /*----------------------------------------------------------------------------*/
334 /* if(sl<*mx) *mx=sl; */
335 /*----------------------------------------------------------------------------*/
336  break;
337  }
338  case 1: {
339  *mn=cdf->sll.comn[cs];
340  *mx=cdf->sll.comx[cs];
341  if((sl+(*mn))<*mx) *mx=sl+(*mn);
342 /*----------------------------------------------------------------------------*/
343 /* if(sl<*mx) *mx=sl; */
344 /*----------------------------------------------------------------------------*/
345  break;
346  }
347  }
348 
349 #ifdef SLO0_DEBUG
350  printf("mn: %d mx: %d\n",*mn,*mx);
351 #endif
352 
353 /*----------------------------------------------------------------------------*/
354 /* Free local storage */
355 /*----------------------------------------------------------------------------*/
356  free(no);
357  free(co);
358 
359  return(1);
360 }
int i
int * comn
Definition: thrdatd.h:72
int * nomn
Definition: thrdatd.h:70
struct _Cor_Def::@23 sll
int * nomx
Definition: thrdatd.h:71
struct _Cor_Def::@24 lll
int * rfpt
Definition: thrdatd.h:69
int * comx
Definition: thrdatd.h:73
int * llmx
Definition: thrdatd.h:78
int * llmn
Definition: thrdatd.h:77
int n
Definition: thrdatd.h:74
int * no
Definition: thrdatd.h:179
int * co
Definition: thrdatd.h:180
int ** mll
Definition: thrdatd.h:63
int * mx
Definition: thrdatd.h:96
int * mn
Definition: thrdatd.h:95
int n
Definition: thrdatd.h:93
struct _Qry_Seq::@26 sac
int slo0(Fld_Mtf *mtf, Cor_Def *cdf, Qry_Seq *qsq, Cur_Loc *sli, int cs, int ct, int *mn, int *mx)
Definition: thrdslo0.c:63
void free(voidpf ptr)
voidp calloc(uInt items, uInt size)
Modified on Fri Sep 20 14:57:21 2024 by modify_doxy.py rev. 669887