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