1 /* @include embpat ************************************************************
2 **
3 ** General routines for pattern matching.
4 **
5 ** @author Copyright (C) Alan Bleasby 1999
6 ** @version $Revision: 1.25 $
7 ** @modified $Date: 2012/12/07 10:24:56 $ by $Author: rice $
8 ** @@
9 **
10 ** This library is free software; you can redistribute it and/or
11 ** modify it under the terms of the GNU Lesser General Public
12 ** License as published by the Free Software Foundation; either
13 ** version 2.1 of the License, or (at your option) any later version.
14 **
15 ** This library is distributed in the hope that it will be useful,
16 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 ** Lesser General Public License for more details.
19 **
20 ** You should have received a copy of the GNU Lesser General Public
21 ** License along with this library; if not, write to the Free Software
22 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
23 ** MA  02110-1301,  USA.
24 **
25 ******************************************************************************/
26 
27 #ifndef EMBPAT_H
28 #define EMBPAT_H
29 
30 
31 
32 
33 
34 
35 /* ========================================================================= */
36 /* ============================= include files ============================= */
37 /* ========================================================================= */
38 
39 #include "ajdefine.h"
40 #include "ajstr.h"
41 #include "ajlist.h"
42 #include "ajfile.h"
43 #include "ajpat.h"
44 #include "ajseqdata.h"
45 #include "ajarr.h"
46 
47 AJ_BEGIN_DECLS
48 
49 
50 
51 
52 /* ========================================================================= */
53 /* =============================== constants =============================== */
54 /* ========================================================================= */
55 
56 
57 
58 
59 /* ========================================================================= */
60 /* ============================== public data ============================== */
61 /* ========================================================================= */
62 
63 
64 
65 /* @enum AjEPatType ***********************************************************
66 **
67 ** Enumerated sequence pattern type
68 **
69 ** @value PATSEQ_UNKNOWN type not defined
70 ** @value PATSEQ_BMH     Boyer, Moore, Horspool
71 ** @value PATSEQ_BYP     Baeza-Yates, perleberg
72 ** @value PATSEQ_SO      Shift-OR
73 ** @value PATSEQ_BYGC    Baeza-Yates, Gonnet classes
74 ** @value PATSEQ_PROSITE Prosite pattern as regular expression
75 ** @value PATSEQ_TUB     Tarhito, Ukkonen, Bleasby
76 ** @value PATSEQ_OTHER   Brute force processing
77 ** @value PATSEQ_MAX     Beyond last defined value
78 ******************************************************************************/
79 
80 typedef enum AjOPatseqType
81 {
82     PATSEQ_UNKNOWN,
83     PATSEQ_BMH,
84     PATSEQ_BYP,
85     PATSEQ_SO,
86     PATSEQ_BYGC,
87     PATSEQ_PROSITE,
88     PATSEQ_TUB,
89     PATSEQ_OTHER,
90     PATSEQ_MAX
91 } EmbEPatseqType;
92 
93 
94 
95 
96 /* @data EmbPPatMatch *********************************************************
97 **
98 ** NUCLEUS data structure for pattern matches
99 **
100 ** @attr start [ajuint*] Match start positions
101 ** @attr len [ajuint*] Match lengths
102 ** @attr number [ajuint] Number of matches
103 ** @attr Padding [char[4]] Padding to alignment boundary
104 ** @@
105 ******************************************************************************/
106 
107 typedef struct EmbSPatMatch {
108   ajuint *start;
109   ajuint *len;
110   ajuint number;
111   char Padding[4];
112 } EmbOPatMatch;
113 #define EmbPPatMatch EmbOPatMatch*
114 
115 
116 
117 
118 /* @data EmbPPatRestrict ******************************************************
119 **
120 ** NUCLEUS data structure for pattern matches
121 **
122 ** @attr cod [AjPStr] Restriction Enzyme name
123 ** @attr pat [AjPStr] Recognition site
124 ** @attr bin [AjPStr] Binary converted site
125 ** @attr len [ajuint] Pattern length
126 ** @attr blunt [AjBool] Blunt true, sticky false
127 ** @attr cut1 [ajint] First  3' cut
128 ** @attr cut2 [ajint] First  5' cut
129 ** @attr cut3 [ajint] Second 3' cut
130 ** @attr cut4 [ajint] Second 5' cut
131 ** @attr org [AjPStr] Organism
132 ** @attr iso [AjPStr] Isoschizomers
133 ** @attr meth [AjPStr] Methylation
134 ** @attr sou [AjPStr] Source
135 ** @attr sup [AjPStr] Suppliers
136 ** @attr ncuts [ajuint] Number of cuts
137 ** @attr Padding [char[4]] Padding to alignment boundary
138 ** @@
139 ******************************************************************************/
140 
141 typedef struct EmbSPatRestrict
142 {
143     AjPStr cod;
144     AjPStr pat;
145     AjPStr bin;
146     ajuint  len;
147     AjBool blunt;
148     ajint  cut1;
149     ajint  cut2;
150     ajint  cut3;
151     ajint  cut4;
152     AjPStr org;
153     AjPStr iso;
154     AjPStr meth;
155     AjPStr sou;
156     AjPStr sup;
157     ajuint  ncuts;
158     char Padding[4];
159 } EmbOPatRestrict;
160 #define EmbPPatRestrict EmbOPatRestrict*
161 
162 
163 
164 
165 #define EmbPPatBYPNode AjOPatBYPNode*
166 #define EmbOPatBYPNode AjOPatBYPNode
167 
168 
169 
170 
171 /* ========================================================================= */
172 /* =========================== public functions ============================ */
173 /* ========================================================================= */
174 
175 
176 
177 /*
178 ** Prototype definitions
179 */
180 
181 void            embPatBMHInit (const AjPStr pat, ajuint len, ajint *next);
182 ajuint          embPatBMHSearch (const AjPStr str, const AjPStr pat,
183 				 ajuint slen, ajuint plen,
184 				 const ajint *skip, ajuint start,
185 				 AjBool left, AjBool right,
186 				 AjPList l, const AjPStr name, ajuint begin);
187 
188 ajuint          embPatBruteForce (const AjPStr seq, const AjPStr pat,
189 				  AjBool amino,
190 				  AjBool carboxyl,
191 				  AjPList l, ajuint begin, ajuint mm,
192 				  const AjPStr name);
193 
194 void            embPatBYGCInit (const AjPStr pat, ajuint *m, ajuint *table,
195 				ajuint *limit);
196 ajuint          embPatBYGSearch (const AjPStr str, const AjPStr name,
197 				 ajuint begin, ajuint plen,
198 				 const ajuint *table, ajuint limit,
199 				 AjPList l, AjBool amino, AjBool carboxyl);
200 
201 void            embPatBYPInit (const AjPStr pat, ajuint len,
202 			       EmbPPatBYPNode offset, ajint *buf);
203 ajuint          embPatBYPSearch (const AjPStr str, const AjPStr name,
204 				 ajuint begin,
205 				 ajuint slen, ajuint plen, ajuint mm,
206 				 EmbPPatBYPNode offset, ajint *buf,
207 				 AjPList l, AjBool amino, AjBool carboxyl,
208 				 const AjPStr pat);
209 
210 AjBool          embPatClassify (const AjPStr pat, AjPStr *cleanpat,
211 				AjBool *amino, AjBool *carboxyl,
212 				AjBool *fclass, AjBool *ajcompl,
213 				AjBool *dontcare, AjBool *range,
214 				AjBool protein);
215 
216 void            embPatCompile(ajuint type, const AjPStr pattern,
217 			      ajuint* plen, ajint** buf,
218 			      EmbPPatBYPNode off, ajuint** sotable,
219 			      ajuint* solimit, ajuint* m, AjPStr* regexp,
220 			      ajuint*** skipm,  ajuint mismatch);
221 
222 void            embPatFuzzSearch(ajuint type, ajuint begin,
223 				 const AjPStr pattern,
224 				 const AjPStr name,
225 				 const AjPStr text, AjPList l,
226 				 ajuint plen, ajuint mismatch,
227 				 AjBool left, AjBool right,
228 				 ajint *buf, EmbPPatBYPNode off,
229 				 const ajuint *sotable,
230 				 ajuint solimit, const AjPStr regexp,
231 				 ajuint * const *skipm,
232 				 ajuint *hits, ajuint m, const void **tidy);
233 
234 void            embPatFuzzSearchAll(ajuint type, ajuint begin,
235                                     const AjPStr pattern,
236                                     const AjPStr name,
237                                     const AjPStr text, AjPList l,
238                                     ajuint plen, ajuint mismatch,
239                                     AjBool left, AjBool right,
240                                     ajint *buf, EmbPPatBYPNode off,
241                                     const ajuint *sotable,
242                                     ajuint solimit, const AjPStr regexp,
243                                     ajuint * const *skipm,
244                                     ajuint *hits, ajuint m, const void **tidy);
245 
246 ajuint          embPatGetType(const AjPStr pattern, AjPStr *cleanpat,
247 			      ajuint mismatch,
248 			      AjBool protein,
249 			      ajuint *m, AjBool *left, AjBool *right);
250 
251 void		embPatCompileII (AjPPatComp thys, ajuint mismatch);
252 void		embPatFuzzSearchII (AjPPatComp thys, ajuint begin,
253 				   const AjPStr name, const AjPStr text,
254 				   AjPList l, ajuint mismatch, ajuint *hits,
255 				   const void **tidy);
256 void		embPatFuzzSearchAllII (AjPPatComp thys, ajuint begin,
257                                        const AjPStr name, const AjPStr text,
258                                        AjPList l, ajuint mismatch, ajuint *hits,
259                                        const void **tidy);
260 ajuint   	embPatGetTypeII (AjPPatComp thys, const AjPStr pattern,
261 				 ajuint mismatch, AjBool protein);
262 
263 void            embPatKMPInit (const AjPStr pat, ajuint len, ajint *next);
264 ajuint          embPatKMPSearch (const AjPStr str, const AjPStr pat,
265 				 ajuint slen, ajuint plen,
266 				 const ajint *next, ajuint start);
267 
268 void            embPatMatchDel (EmbPPatMatch* pthis);
269 EmbPPatMatch    embPatMatchFind  (const AjPStr regexp, const AjPStr strng,
270 				  AjBool left, AjBool right);
271 EmbPPatMatch    embPatMatchFindC (const AjPStr regexp, const char *sptr,
272 				  AjBool left, AjBool right);
273 EmbPPatMatch    embPatMatchFindAll  (const AjPStr regexp, const AjPStr strng,
274                                      AjBool left, AjBool right);
275 EmbPPatMatch    embPatMatchFindAllC (const AjPStr regexp, const char *sptr,
276                                      AjBool left, AjBool right);
277 ajuint          embPatMatchGetEnd (const EmbPPatMatch data, ajuint indexnum);
278 ajuint          embPatMatchGetLen (const EmbPPatMatch data, ajuint indexnum);
279 ajuint          embPatMatchGetNumber (const EmbPPatMatch data);
280 ajuint          embPatMatchGetStart (const EmbPPatMatch data, ajuint indexnum);
281 
282 AjPStr          embPatPrositeToRegExp (const AjPStr s);
283 AjPStr          embPatPrositeToRegExpEnds (const AjPStr s,
284 					   AjBool start, AjBool end);
285 
286 void            embPatPushHit (AjPList l, const AjPStr name,
287 			       ajuint pos, ajuint plen,
288 			       ajuint begin, ajuint mm);
289 
290 void            embPatRestrictDel (EmbPPatRestrict *thys);
291 EmbPPatRestrict embPatRestrictNew (void);
292 ajuint          embPatRestrictMatch (const AjPSeq seq,
293 				     ajuint begin, ajuint end,
294 				     AjPFile enzfile, AjPFile methfile,
295                                      const AjPStr enzymes,
296 				     ajuint sitelen, AjBool plasmid,
297 				     AjBool ambiguity, ajuint min, ajuint max,
298 				     AjBool blunt, AjBool sticky,
299 				     AjBool commercial, AjBool methyl,
300                                      AjPList l);
301 void            embPatRestrictPreferred(AjPList l, const AjPTable t);
302 AjBool          embPatRestrictReadEntry (EmbPPatRestrict re, AjPFile inf);
303 
304 ajuint          embPatRestrictRestrict (AjPList l, ajuint hits, AjBool isos,
305 					AjBool alpha);
306 ajuint          embPatRestrictScan (const EmbPPatRestrict enz,
307 				    const AjPStr substr,
308 				    const AjPStr binstr, const AjPStr revstr,
309 				    const AjPStr binrev, ajuint len,
310 				    AjBool ambiguity,
311 				    AjBool plasmid, ajuint min,
312 				    ajuint max, ajuint begin, AjPList l);
313 
314 ajint           embPatRestrictCutCompare(const void *a, const void *b);
315 ajint           embPatRestrictNameCompare(const void *a, const void *b);
316 ajint           embPatRestrictStartCompare(const void *a, const void *b);
317 EmbPPatMatch    embPatSeqMatchFind  (const AjPSeq seq, const AjPStr reg);
318 EmbPPatMatch    embPatSeqMatchFindC (const AjPSeq seq, const char *reg);
319 EmbPPatMatch    embPatSeqMatchFindAll  (const AjPSeq seq, const AjPStr reg);
320 EmbPPatMatch    embPatSeqMatchFindAllC (const AjPSeq seq, const char *reg);
321 AjPStr          embPatSeqCreateRegExp  (const AjPStr thys, AjBool protein);
322 AjPStr          embPatSeqCreateRegExpC (const char *ptr, AjBool protein);
323 
324 void            embPatSOInit (const AjPStr pat, ajuint *table,
325 			      ajuint *limit);
326 ajuint          embPatSOSearch (const AjPStr str, const AjPStr name,
327 				ajint first,
328 				ajuint begin, ajuint plen, const ajuint *table,
329 				ajuint limit, AjPList l,
330 				AjBool amino, AjBool carboxyl);
331 
332 void            embPatTUBInit (const AjPStr pat, ajuint **skipm,
333 			       ajuint m, ajuint k, ajuint plen);
334 ajuint          embPatTUBSearch (const AjPStr pat,const AjPStr text,
335 				 ajuint slen,
336 				 ajuint * const *skipm, ajuint m,
337 				 ajuint k, ajuint begin,
338 				 AjPList l, AjBool amino,
339 				 AjBool carboxyl, const AjPStr name,
340 				 ajuint plen);
341 
342 void            embPatTUInit (const AjPStr pat,
343 			      ajuint **skipm, ajuint m, ajuint k);
344 ajuint          embPatTUSearch (const AjPStr pat,
345 				const AjPStr text, ajuint slen,
346 				ajuint * const *skipm, ajuint m,
347 				ajuint k, ajuint begin,
348 				AjPList l, AjBool amino,
349 				AjBool carboxyl, const AjPStr name);
350 
351 ajuint          embPatVariablePattern (const AjPStr pattern,
352 				       const AjPStr text,
353 				       const AjPStr patname, AjPList l,
354 				       ajuint mode,
355 				       ajuint mismatch, ajuint begin);
356 
357 /*
358 ** End of prototype definitions
359 */
360 
361 AJ_END_DECLS
362 
363 #endif  /* !EMBPAT_H */
364