Debian Codegraph @

CDnaString2.h

raw
1 /* BaitFisher (version 1.2.7) a program for designing DNA target enrichment baits
2 * Copyright 2013-2016 by Christoph Mayer
3 *
4 * This source file is part of the BaitFisher-package.
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
18 *
19 *
20 * For any enquiries send an Email to Christoph Mayer
21 * [email protected]
22 *
23 * When publishing work that is based on the results please cite:
24 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
25 *
26 */
27 #ifndef DNASTRING_H
28 #define DNASTRING_H
29
30 #include "primefactors.h"
31 #include "faststring2.h"
32 #include <cctype>
33 #include "basic-DNA-RNA-AA-routines.h"
34
35
36 // Todo:
37 // - Check for correct nucl. in push_back, set routine
38
39 inline bool isReducibleUnit_global(const char *beg, const char* end)
40 {
41 unsigned len = end-beg;
42 const char *test_pos;
43
44 int factor_index;
45 unsigned factor;
46 unsigned factor_len;
47 unsigned i;
48 bool composite;
49
50 factor_index = 0;
51 while( (factor = primeFactors[len][factor_index]) != 0 )
52 {
53 composite = true;
54 factor_len = len/factor;
55 test_pos = beg;
56 for (i=1; i<factor; ++i, test_pos += factor_len)
57 if ( strncmp(test_pos, (test_pos + factor_len), factor_len) != 0)
58 composite = false;
59
60 if (composite)
61 return true;
62 ++factor_index;
63 }
64 return false;
65 }
66
67
68
69 class CDnaString : public faststring
70 {
71 public:
72 /* using faststring::c_str; */
73 /* using faststring::reserve; */
74 /* using faststring::size; */
75 /* using faststring::capacity; */
76 /* using faststring::clear; */
77 /* using faststring::check_pos; */
78 /* using faststring::set_unckecked; */
79 /* using faststring::assign; */
80 /* using faststring::push_back; */
81 /* using faststring::set_unchecked; */
82 /* using faststring::begin; */
83 /* using faststring::end; */
84 /* using faststring::tolower; */
85 /* using faststring::toupper; */
86
87
88 CDnaString():faststring()
89 {}
90
91 CDnaString(const char *s):faststring(s)
92 {}
93
94 CDnaString(const faststring &s):faststring(s)
95 {}
96
97 void toupper_assign(const char *str)
98 {
99 faststring::assign(str);
100 toupper();
101 }
102
103 void toupper_assign(const char *str_begin, const char *str_end)
104 {
105 faststring::assign(str_begin, str_end);
106 toupper();
107 }
108
109 void toupper_push_back(char c)
110 {
111 faststring::push_back(std::toupper(c));
112 }
113
114 void toupper_set_unckecked(unsigned pos, char c)
115 {
116 faststring::set_unckecked(pos, std::toupper(c));
117 }
118
119 bool toupper_set(unsigned pos, char c)
120 {
121 return faststring::set(pos, std::toupper(c));
122 }
123
124 unsigned countUnknownBases()
125 {
126 char *b = begin();
127 char *e = end();
128 char c;
129 unsigned errors = 0;
130
131 while (b != e)
132 {
133 c = *b;
134 if (c != 'A' && c != 'C' && c != 'G' && c != 'T' &&
135 c != 'R' && c != 'Y' &&
136 c != 'M' && c != 'K' &&
137 c != 'B' && c != 'V' &&
138 c != 'D' && c != 'H' &&
139 c != 'N' )
140 ++errors;
141 ++b;
142 }
143 return errors;
144 }
145
146
147 unsigned setToComplementOf(const CDnaString &a)
148 {
149 unsigned len = a.size();
150 const char *pos = a.begin();
151 const char *pos_end = a.end();
152 unsigned error = 0;
153
154 reserve(len);
155 clear();
156
157 while( pos != pos_end )
158 {
159 switch (*pos)
160 {
161 case 'A': faststring::push_back('T'); break;
162 case 'T': faststring::push_back('A'); break;
163 case 'G': faststring::push_back('C'); break;
164 case 'C': faststring::push_back('G'); break;
165
166 case 'R': faststring::push_back('Y'); break;
167 case 'Y': faststring::push_back('R'); break;
168
169 case 'M': faststring::push_back('K'); break;
170 case 'K': faststring::push_back('M'); break;
171
172 case 'B': faststring::push_back('V'); break;
173 case 'V': faststring::push_back('B'); break;
174
175 case 'D': faststring::push_back('H'); break;
176 case 'H': faststring::push_back('D'); break;
177
178 case 'N': faststring::push_back('N'); break;
179 default:
180 ++error;
181 push_back('?');
182 break;
183 };
184 ++pos;
185 }
186 return error;
187 }
188
189 unsigned setToReverseComplementOf(const CDnaString &a)
190 {
191 unsigned len = a.size();
192 const char *pos = a.rbegin();
193 const char *pos_end = a.rend();
194 unsigned error = 0;
195
196 reserve(len);
197 clear();
198
199 while( pos != pos_end )
200 {
201 switch (*pos)
202 {
203 case 'A': faststring::push_back('T'); break;
204 case 'T': faststring::push_back('A'); break;
205 case 'G': faststring::push_back('C'); break;
206 case 'C': faststring::push_back('G'); break;
207
208 case 'R': faststring::push_back('Y'); break;
209 case 'Y': faststring::push_back('R'); break;
210
211 case 'M': faststring::push_back('K'); break;
212 case 'K': faststring::push_back('M'); break;
213
214 case 'B': faststring::push_back('V'); break;
215 case 'V': faststring::push_back('B'); break;
216
217 case 'D': faststring::push_back('H'); break;
218 case 'H': faststring::push_back('D'); break;
219
220 case 'N': faststring::push_back('N'); break;
221 default:
222 ++error;
223 push_back('?');
224 break;
225 };
226 --pos;
227 }
228 return error;
229 }
230
231
232 void setToReverseOf(const CDnaString &a)
233 {
234 unsigned len = a.size();
235 const char *pos = a.rbegin();
236 const char *pos_end = a.rend();
237
238 reserve(len);
239 clear();
240
241 while( pos != pos_end )
242 {
243 faststring::push_back(*pos);
244 --pos;
245 }
246 }
247
248
249 // Returns true if a subpattern has been found,
250 // false if no subpattern has been found.
251 void correct_unit_with_subpattern(unsigned &ulen)
252 {
253 unsigned len = size();
254 char *tmp = new char [2*len+1];
255 const char *orig = c_str();
256
257 char *pos = tmp;
258 char *pos_end = pos + len;
259 int strncmp_result;
260
261 strcpy(tmp, orig);
262 strcpy(tmp+len, orig);
263
264 // std::cerr << "Correcting unit: " << *this << std::endl;
265 ++pos;
266 for (; pos != pos_end; ++pos)
267 {
268 strncmp_result = strncmp(tmp, pos, len);
269 if ( strncmp_result == 0 ) // Subpattern has been found
270 {
271 ulen = pos-tmp;
272 shorten(ulen);
273 // std::cerr << "New unit: " << ulen << " " << *this << std::endl;
274 break;
275 }
276 }
277 delete [] tmp;
278 }
279
280
281 // Returns true if a subpattern has been found,
282 // false if no subpattern has been found.
283 bool setToMinAlphaRepModCyclicPermOf(const CDnaString &s)
284 {
285 unsigned len = s.size();
286 char *tmp = new char [2*len+1];
287 const char *orig = const_cast<CDnaString&>(s).c_str();
288
289 char *pos = tmp;
290 char *pos_end = pos + len;
291 //unsigned i;
292 char *min_str;
293 int strncmp_result;
294
295 bool found_subpattern = false;
296
297 strcpy(tmp, orig);
298 strcpy(tmp+len, orig);
299
300 min_str = tmp;
301 ++pos;
302 for (; pos != pos_end; ++pos)
303 {
304 strncmp_result = strncmp(pos, min_str, len);
305 if ( strncmp_result < 0 )
306 min_str = pos;
307 else if ( strncmp_result == 0 )
308 {
309 // New pattern is from
310 found_subpattern = true;
311 }
312 }
313 *(min_str+len) = '\0'; /* At this position within tmp we have the end of the unit */
314 faststring::assign(min_str);
315 delete [] tmp;
316 return found_subpattern;
317 }
318
319 // Returns true if a subpattern has been found,
320 // false if no subpattern has been found.
321 bool setToMinAlphaRepModRevCompAndCyclicPermOf(const CDnaString &s)
322 {
323 CDnaString tmp;
324 bool found_subpattern;
325
326 tmp.setToReverseComplementOf(s);
327 found_subpattern = setToMinAlphaRepModCyclicPermOf(tmp); // *this contains minimum representation of rev comp of s
328
329 tmp.setToMinAlphaRepModCyclicPermOf(s); // tmp contains minimum representation of s itself
330
331 if ( strcmp(c_str(), tmp.c_str() ) > 0 )
332 {
333 assign( tmp.c_str() );
334 }
335 return found_subpattern;
336 }
337
338 // Returns true if a subpattern has been found,
339 // false if no subpattern has been found.
340 bool setToMinAlphaRepModRevCompAndCyclicPermOf(const CDnaString &s, signed char &direction)
341 {
342 CDnaString tmp;
343 bool found_subpattern;
344
345 tmp.setToReverseComplementOf(s);
346 found_subpattern = setToMinAlphaRepModCyclicPermOf(tmp); // *this contains minimum representation of rev comp of s
347
348 tmp.setToMinAlphaRepModCyclicPermOf(s); // tmp contains minimum representation of s itself
349 direction = 1;
350
351 if ( strcmp(c_str(), tmp.c_str() ) > 0 )
352 {
353 assign( tmp.c_str() );
354 direction = -1;
355 }
356 return found_subpattern;
357 }
358
359
360 bool isCompositeUnitLength(int x)
361 {
362 return primeFactors[x][0];
363 }
364
365 // Old and inefficient:
366 /* bool isReducibleUnit_old() */
367 /* { */
368 /* unsigned len = size(); */
369 /* char *tmp = new char [2*len+1]; */
370 /* const char *orig = c_str(); */
371
372 /* int factor_index; */
373 /* unsigned shift; */
374
375 /* strcpy(tmp, orig); */
376 /* strcpy(tmp+len, orig); */
377
378 /* factor_index = 0; */
379 /* while( (shift = primeFactors[len][factor_index]) != 0 ) */
380 /* { */
381 /* if ( strncmp(tmp, tmp+shift, len) == 0) */
382 /* return true; */
383 /* ++factor_index; */
384 /* } */
385 /* return false; */
386 /* } */
387
388 // New and works but is redundent - equivalent to current version
389 /* bool isReducibleUnit_ok() */
390 /* { */
391 /* unsigned len = size(); */
392 /* const char *orig = c_str(); */
393
394 /* int factor_index; */
395 /* unsigned factor; */
396 /* unsigned factor_len; */
397 /* unsigned i; */
398 /* bool composite; */
399
400 /* factor_index = 0; */
401 /* while( (factor = primeFactors[len][factor_index]) != 0 ) */
402 /* { */
403 /* composite = true; */
404 /* factor_len = len/factor; */
405 /* orig = c_str(); */
406 /* for (i=1; i<factor; ++i, orig += factor_len) */
407 /* if ( strncmp(orig, orig+factor_len, factor_len) != 0) */
408 /* composite = false; */
409
410 /* if (composite) */
411 /* return true; */
412 /* ++factor_index; */
413 /* } */
414 /* return false; */
415 /* } */
416
417 bool isReducibleUnit()
418 {
419 return isReducibleUnit_global(c_str(), c_str()+size());
420 }
421
422
423 friend bool operator<(const CDnaString &a, const CDnaString &b)
424 {
425 // Possibly more efficient would be a strncmp. If equally long, take the shorter one.
426 // Not tested yet - thats why its not used!
427
428 // unsigned minlen = (a.length() < b.length() ? a.length() : b.length());
429 // short test = strncmp(a.begin(), b.begin(), minlen);
430
431 // if (test == 0)
432 // return a.length() < b.length();
433 // else
434 // return (test < 0);
435
436 // Hi compiler - how do you like this: Haahaahaahaaaaaaaa
437 return (strcmp(const_cast<CDnaString&>(a).c_str(), const_cast<CDnaString&>(b).c_str() ) < 0);
438 }
439
440 };
441
442
443
444
445 #endif