1 | // =============================================================== // |
---|
2 | // // |
---|
3 | // File : PT_new_design.cxx // |
---|
4 | // Purpose : // |
---|
5 | // // |
---|
6 | // Institute of Microbiology (Technical University Munich) // |
---|
7 | // http://www.arb-home.de/ // |
---|
8 | // // |
---|
9 | // =============================================================== // |
---|
10 | |
---|
11 | |
---|
12 | #include "pt_split.h" |
---|
13 | #include <PT_server_prototypes.h> |
---|
14 | |
---|
15 | #include <struct_man.h> |
---|
16 | #include "probe_tree.h" |
---|
17 | #include "PT_prefixIter.h" |
---|
18 | |
---|
19 | #include <arb_str.h> |
---|
20 | #include <arb_defs.h> |
---|
21 | #include <arb_sort.h> |
---|
22 | |
---|
23 | #include <arb_strbuf.h> |
---|
24 | #include <arb_strarray.h> |
---|
25 | |
---|
26 | #include <climits> |
---|
27 | #include <algorithm> |
---|
28 | #include <map> |
---|
29 | #include <arb_progress.h> |
---|
30 | |
---|
31 | #if defined(DEBUG) |
---|
32 | // # define DUMP_DESIGNED_PROBES |
---|
33 | // # define DUMP_OLIGO_MATCHING |
---|
34 | #endif |
---|
35 | |
---|
36 | #define MIN_DESIGN_PROBE_LENGTH DOMAIN_MIN_LENGTH |
---|
37 | int Complement::calc_complement(int base) { |
---|
38 | switch (base) { |
---|
39 | case PT_A: return PT_T; |
---|
40 | case PT_C: return PT_G; |
---|
41 | case PT_G: return PT_C; |
---|
42 | case PT_T: return PT_A; |
---|
43 | default: return base; |
---|
44 | } |
---|
45 | } |
---|
46 | |
---|
47 | // overloaded functions to avoid problems with type-punning: |
---|
48 | inline void aisc_link(dll_public *dll, PT_tprobes *tprobe) { aisc_link(reinterpret_cast<dllpublic_ext*>(dll), reinterpret_cast<dllheader_ext*>(tprobe)); } |
---|
49 | |
---|
50 | extern "C" { |
---|
51 | int pt_init_bond_matrix(PT_local *THIS) |
---|
52 | { |
---|
53 | THIS->bond[0].val = 0.0; |
---|
54 | THIS->bond[1].val = 0.0; |
---|
55 | THIS->bond[2].val = 0.5; |
---|
56 | THIS->bond[3].val = 1.1; |
---|
57 | THIS->bond[4].val = 0.0; |
---|
58 | THIS->bond[5].val = 0.0; |
---|
59 | THIS->bond[6].val = 1.5; |
---|
60 | THIS->bond[7].val = 0.0; |
---|
61 | THIS->bond[8].val = 0.5; |
---|
62 | THIS->bond[9].val = 1.5; |
---|
63 | THIS->bond[10].val = 0.4; |
---|
64 | THIS->bond[11].val = 0.9; |
---|
65 | THIS->bond[12].val = 1.1; |
---|
66 | THIS->bond[13].val = 0.0; |
---|
67 | THIS->bond[14].val = 0.9; |
---|
68 | THIS->bond[15].val = 0.0; |
---|
69 | |
---|
70 | return 0; |
---|
71 | } |
---|
72 | } |
---|
73 | |
---|
74 | struct dt_bondssum { |
---|
75 | double dt; // sum of mismatches |
---|
76 | double sum_bonds; // sum of bonds of longest non mismatch string |
---|
77 | |
---|
78 | dt_bondssum(double dt_, double sum_bonds_) : dt(dt_), sum_bonds(sum_bonds_) {} |
---|
79 | }; |
---|
80 | |
---|
81 | class Oligo { |
---|
82 | const char *data; |
---|
83 | int length; |
---|
84 | |
---|
85 | public: |
---|
86 | Oligo() : data(NULL), length(0) {} // empty oligo |
---|
87 | Oligo(const char *data_, int length_) : data(data_), length(length_) {} |
---|
88 | Oligo(const Oligo& other) : data(other.data), length(other.length) {} |
---|
89 | DECLARE_ASSIGNMENT_OPERATOR(Oligo); |
---|
90 | |
---|
91 | char at(int offset) const { |
---|
92 | pt_assert(offset >= 0 && offset<length); |
---|
93 | return data[offset]; |
---|
94 | } |
---|
95 | int size() const { return length; } |
---|
96 | |
---|
97 | Oligo suffix(int skip) const { |
---|
98 | return skip <= length ? Oligo(data+skip, length-skip) : Oligo(); |
---|
99 | } |
---|
100 | |
---|
101 | #if defined(DUMP_OLIGO_MATCHING) |
---|
102 | void dump(FILE *out) const { |
---|
103 | char *readable = readable_probe(data, length, 'T'); |
---|
104 | fputs(readable, out); |
---|
105 | free(readable); |
---|
106 | } |
---|
107 | #endif |
---|
108 | }; |
---|
109 | |
---|
110 | class MatchingOligo { |
---|
111 | Oligo oligo; |
---|
112 | int matched; // how many positions matched |
---|
113 | int lastSplit; |
---|
114 | |
---|
115 | bool domain_found; |
---|
116 | double maxDomainBondSum; |
---|
117 | |
---|
118 | dt_bondssum linkage; |
---|
119 | |
---|
120 | MatchingOligo(const MatchingOligo& other, double strength) // expand by 1 (with a split) |
---|
121 | : oligo(other.oligo), |
---|
122 | matched(other.matched+1), |
---|
123 | domain_found(other.domain_found), |
---|
124 | maxDomainBondSum(other.maxDomainBondSum), |
---|
125 | linkage(other.linkage) |
---|
126 | { |
---|
127 | pt_assert(other.dangling()); |
---|
128 | pt_assert(strength<0.0); |
---|
129 | |
---|
130 | lastSplit = matched-1; |
---|
131 | linkage.dt -= strength; |
---|
132 | linkage.sum_bonds = 0.0; |
---|
133 | |
---|
134 | pt_assert(domainLength() == 0); |
---|
135 | } |
---|
136 | |
---|
137 | MatchingOligo(const MatchingOligo& other, double strength, double max_bond) // expand by 1 (binding) |
---|
138 | : oligo(other.oligo), |
---|
139 | matched(other.matched+1), |
---|
140 | domain_found(other.domain_found), |
---|
141 | maxDomainBondSum(other.maxDomainBondSum), |
---|
142 | linkage(other.linkage) |
---|
143 | { |
---|
144 | pt_assert(other.dangling()); |
---|
145 | pt_assert(strength >= 0.0); |
---|
146 | |
---|
147 | lastSplit = other.lastSplit; |
---|
148 | linkage.dt += strength; |
---|
149 | linkage.sum_bonds += max_bond-strength; |
---|
150 | |
---|
151 | pt_assert(linkage.sum_bonds >= 0.0); |
---|
152 | |
---|
153 | if (domainLength() >= DOMAIN_MIN_LENGTH) { |
---|
154 | domain_found = true; |
---|
155 | maxDomainBondSum = std::max(maxDomainBondSum, linkage.sum_bonds); |
---|
156 | } |
---|
157 | } |
---|
158 | |
---|
159 | void accept_rest_dangling() { |
---|
160 | pt_assert(dangling()); |
---|
161 | lastSplit = matched+1; |
---|
162 | matched = oligo.size(); |
---|
163 | pt_assert(!dangling()); |
---|
164 | } |
---|
165 | |
---|
166 | void optimal_bind_rest(const Splits& splits, const double *max_bond) { // @@@ slow -> optimize |
---|
167 | pt_assert(dangling()); |
---|
168 | while (dangling()) { |
---|
169 | char pc = dangling_char(); |
---|
170 | double strength = splits.check(pc, pc); |
---|
171 | double bondmax = max_bond[safeCharIndex(pc)]; |
---|
172 | |
---|
173 | pt_assert(strength >= 0.0); |
---|
174 | |
---|
175 | matched++; |
---|
176 | linkage.dt += strength; |
---|
177 | linkage.sum_bonds += bondmax-strength; |
---|
178 | } |
---|
179 | if (domainLength() >= DOMAIN_MIN_LENGTH) { |
---|
180 | domain_found = true; |
---|
181 | maxDomainBondSum = std::max(maxDomainBondSum, linkage.sum_bonds); |
---|
182 | } |
---|
183 | pt_assert(!dangling()); |
---|
184 | } |
---|
185 | |
---|
186 | public: |
---|
187 | explicit MatchingOligo(const Oligo& oligo_) |
---|
188 | : oligo(oligo_), |
---|
189 | matched(0), |
---|
190 | lastSplit(-1), |
---|
191 | domain_found(false), |
---|
192 | maxDomainBondSum(-1), |
---|
193 | linkage(0.0, 0.0) |
---|
194 | {} |
---|
195 | |
---|
196 | int dangling() const { |
---|
197 | int dangle_count = oligo.size()-matched; |
---|
198 | pt_assert(dangle_count >= 0); |
---|
199 | return dangle_count; |
---|
200 | } |
---|
201 | |
---|
202 | char dangling_char() const { |
---|
203 | pt_assert(dangling()>0); |
---|
204 | return oligo.at(matched); |
---|
205 | } |
---|
206 | |
---|
207 | MatchingOligo bind_against(char c, const Splits& splits, const double *max_bond) const { |
---|
208 | pt_assert(c != PT_QU); |
---|
209 | |
---|
210 | char pc = dangling_char(); |
---|
211 | double strength = splits.check(pc, c); |
---|
212 | |
---|
213 | return strength<0.0 |
---|
214 | ? MatchingOligo(*this, strength) |
---|
215 | : MatchingOligo(*this, strength, max_bond[safeCharIndex(pc)]); |
---|
216 | } |
---|
217 | |
---|
218 | MatchingOligo dont_bind_rest() const { |
---|
219 | MatchingOligo accepted(*this); |
---|
220 | accepted.accept_rest_dangling(); |
---|
221 | return accepted; |
---|
222 | } |
---|
223 | |
---|
224 | int domainLength() const { return matched-(lastSplit+1); } |
---|
225 | |
---|
226 | bool domainSeen() const { return domain_found; } |
---|
227 | bool domainPossible() const { |
---|
228 | pt_assert(!domainSeen()); // you are testing w/o need |
---|
229 | return (domainLength()+dangling()) >= DOMAIN_MIN_LENGTH; |
---|
230 | } |
---|
231 | |
---|
232 | bool completely_bound() const { return !dangling(); } |
---|
233 | |
---|
234 | int calc_centigrade_pos(const PT_tprobes *tprobe, const PT_pdc *const pdc) const { |
---|
235 | pt_assert(completely_bound()); |
---|
236 | pt_assert(domainSeen()); |
---|
237 | |
---|
238 | double ndt = (linkage.dt * pdc->dt + (tprobe->sum_bonds - maxDomainBondSum)*pdc->dte) / tprobe->seq_len; |
---|
239 | int pos = (int)ndt; |
---|
240 | |
---|
241 | pt_assert(pos >= 0); |
---|
242 | return pos; |
---|
243 | } |
---|
244 | |
---|
245 | bool centigrade_pos_out_of_reach(const PT_tprobes *tprobe, const PT_pdc *const pdc, const Splits& splits, const double *max_bond) const { |
---|
246 | MatchingOligo optimum(*this); |
---|
247 | optimum.optimal_bind_rest(splits, max_bond); |
---|
248 | |
---|
249 | if (!optimum.domainSeen()) return true; // no domain -> no centigrade position |
---|
250 | |
---|
251 | int centpos = optimum.calc_centigrade_pos(tprobe, pdc); |
---|
252 | return centpos >= PERC_SIZE; |
---|
253 | } |
---|
254 | |
---|
255 | const Oligo& get_oligo() const { return oligo; } |
---|
256 | |
---|
257 | #if defined(DUMP_OLIGO_MATCHING) |
---|
258 | void dump(FILE *out) const { |
---|
259 | fputs("oligo='", out); |
---|
260 | oligo.dump(out); |
---|
261 | |
---|
262 | const char *domainState = "impossible"; |
---|
263 | if (domainSeen()) domainState = "seen"; |
---|
264 | else if (domainPossible()) domainState = "possible"; |
---|
265 | |
---|
266 | fprintf(out, "' matched=%2i lastSplit=%2i domainLength()=%2i dangling()=%2i domainState=%s maxDomainBondSum=%f dt=%f sum_bonds=%f\n", |
---|
267 | matched, lastSplit, domainLength(), dangling(), domainState, maxDomainBondSum, linkage.dt, linkage.sum_bonds); |
---|
268 | } |
---|
269 | #endif |
---|
270 | }; |
---|
271 | |
---|
272 | static int ptnd_compare_quality(const void *vtp1, const void *vtp2, void *) { |
---|
273 | const PT_tprobes *tp1 = (const PT_tprobes*)vtp1; |
---|
274 | const PT_tprobes *tp2 = (const PT_tprobes*)vtp2; |
---|
275 | |
---|
276 | int cmp = double_cmp(tp2->quality, tp1->quality); // high quality first |
---|
277 | if (!cmp) { |
---|
278 | cmp = tp1->apos - tp2->apos; // low abs.pos first |
---|
279 | if (!cmp) cmp = strcmp(tp1->sequence, tp2->sequence); // alphabetically by probe |
---|
280 | } |
---|
281 | return cmp; |
---|
282 | } |
---|
283 | |
---|
284 | static int ptnd_compare_sequence(const void *vtp1, const void *vtp2, void*) { |
---|
285 | const PT_tprobes *tp1 = (const PT_tprobes*)vtp1; |
---|
286 | const PT_tprobes *tp2 = (const PT_tprobes*)vtp2; |
---|
287 | |
---|
288 | return strcmp(tp1->sequence, tp2->sequence); |
---|
289 | } |
---|
290 | |
---|
291 | enum ProbeSortMode { |
---|
292 | PSM_QUALITY, |
---|
293 | PSM_SEQUENCE, |
---|
294 | }; |
---|
295 | |
---|
296 | static void sort_tprobes_by(PT_pdc *pdc, ProbeSortMode mode) { |
---|
297 | if (pdc->tprobes) { |
---|
298 | int list_len = pdc->tprobes->get_count(); |
---|
299 | if (list_len > 1) { |
---|
300 | PT_tprobes **my_list = (PT_tprobes **)calloc(sizeof(void *), list_len); |
---|
301 | { |
---|
302 | PT_tprobes *tprobe; |
---|
303 | int i; |
---|
304 | |
---|
305 | for (i = 0, tprobe = pdc->tprobes; tprobe; i++, tprobe = tprobe->next) { |
---|
306 | my_list[i] = tprobe; |
---|
307 | } |
---|
308 | } |
---|
309 | |
---|
310 | switch (mode) { |
---|
311 | case PSM_QUALITY: |
---|
312 | GB_sort((void **)my_list, 0, list_len, ptnd_compare_quality, 0); |
---|
313 | break; |
---|
314 | |
---|
315 | case PSM_SEQUENCE: |
---|
316 | GB_sort((void **)my_list, 0, list_len, ptnd_compare_sequence, 0); |
---|
317 | break; |
---|
318 | } |
---|
319 | |
---|
320 | for (int i=0; i<list_len; i++) { |
---|
321 | aisc_unlink(reinterpret_cast<dllheader_ext*>(my_list[i])); |
---|
322 | aisc_link(&pdc->ptprobes, my_list[i]); |
---|
323 | } |
---|
324 | |
---|
325 | free(my_list); |
---|
326 | } |
---|
327 | } |
---|
328 | } |
---|
329 | static void clip_tprobes(PT_pdc *pdc, int count) |
---|
330 | { |
---|
331 | PT_tprobes *tprobe; |
---|
332 | int i; |
---|
333 | |
---|
334 | for (i=0, tprobe = pdc->tprobes; |
---|
335 | tprobe && i< count; |
---|
336 | i++, tprobe = tprobe->next) ; |
---|
337 | |
---|
338 | if (tprobe) { |
---|
339 | while (tprobe->next) { |
---|
340 | destroy_PT_tprobes(tprobe->next); |
---|
341 | } |
---|
342 | } |
---|
343 | } |
---|
344 | static int pt_get_gc_content(char *probe) |
---|
345 | { |
---|
346 | int gc = 0; |
---|
347 | while (*probe) { |
---|
348 | if (*probe == PT_G || |
---|
349 | *probe == PT_C) { |
---|
350 | gc++; |
---|
351 | } |
---|
352 | probe ++; |
---|
353 | } |
---|
354 | return gc; |
---|
355 | } |
---|
356 | static double pt_get_temperature(const char *probe) |
---|
357 | { |
---|
358 | int i; |
---|
359 | double t = 0; |
---|
360 | while ((i=*(probe++))) { |
---|
361 | if (i == PT_G || i == PT_C) t+=4.0; else t += 2.0; |
---|
362 | } |
---|
363 | return t; |
---|
364 | } |
---|
365 | |
---|
366 | static void tprobes_sumup_perc_and_calc_quality(PT_pdc *pdc) { |
---|
367 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; tprobe = tprobe->next) { |
---|
368 | int sum = 0; |
---|
369 | int i; |
---|
370 | for (i=0; i<PERC_SIZE; ++i) { |
---|
371 | sum += tprobe->perc[i]; |
---|
372 | tprobe->perc[i] = sum; |
---|
373 | } |
---|
374 | |
---|
375 | // pt_assert(tprobe->perc[0] == tprobe->mishits); // OutgroupMatcher and count_mishits_for_matched do not agree! |
---|
376 | // @@@ found one case where it differs by 1 (6176 in perc, 6177 in mishits). Can this be caused somehow by N or IUPAC in seq? |
---|
377 | |
---|
378 | int limit = 2*tprobe->mishits; |
---|
379 | for (i=0; i<(PERC_SIZE-1); ++i) { |
---|
380 | if (tprobe->perc[i]>limit) break; |
---|
381 | } |
---|
382 | |
---|
383 | tprobe->quality = ((double)tprobe->groupsize * i) + 1000.0/(1000.0 + tprobe->perc[i]); |
---|
384 | } |
---|
385 | } |
---|
386 | |
---|
387 | static double ptnd_check_max_bond(const PT_local *locs, char base) { |
---|
388 | //! check the bond val for a probe |
---|
389 | |
---|
390 | int complement = get_complement(base); |
---|
391 | return locs->bond[(complement-(int)PT_A)*4 + base-(int)PT_A].val; |
---|
392 | } |
---|
393 | |
---|
394 | static char hitgroup_idx2char(int idx) { |
---|
395 | const int firstSmall = ALPHA_SIZE/2; |
---|
396 | int c; |
---|
397 | if (idx >= firstSmall) { |
---|
398 | c = 'a'+(idx-firstSmall); |
---|
399 | } |
---|
400 | else { |
---|
401 | c = 'A'+idx; |
---|
402 | } |
---|
403 | pt_assert(isalpha(c)); |
---|
404 | return c; |
---|
405 | } |
---|
406 | |
---|
407 | inline int get_max_probelen(const PT_pdc *pdc) { |
---|
408 | return pdc->max_probelen == -1 ? pdc->min_probelen : pdc->max_probelen; |
---|
409 | } |
---|
410 | |
---|
411 | inline int shown_apos(const PT_tprobes *tprobe) { return info2bio(tprobe->apos); } |
---|
412 | inline int shown_ecoli(const PT_tprobes *tprobe) { return PT_abs_2_ecoli_rel(tprobe->apos+1); } |
---|
413 | inline int shown_qual(const PT_tprobes *tprobe) { return int(tprobe->quality+0.5); } |
---|
414 | |
---|
415 | class PD_formatter { |
---|
416 | int width[PERC_SIZE]; // of centigrade list columns |
---|
417 | int maxprobelen; |
---|
418 | |
---|
419 | int apos_width; |
---|
420 | int ecol_width; |
---|
421 | int qual_width; |
---|
422 | int grps_width; |
---|
423 | |
---|
424 | static inline void track_max(int& tracked, int val) { tracked = std::max(tracked, val); } |
---|
425 | |
---|
426 | void collect(const int *perc) { for (int i = 0; i<PERC_SIZE; ++i) width[i] = std::max(width[i], perc[i]); } |
---|
427 | void collect(const PT_tprobes *tprobe) { |
---|
428 | collect(tprobe->perc); |
---|
429 | track_max(apos_width, shown_apos(tprobe)); |
---|
430 | track_max(ecol_width, shown_ecoli(tprobe)); |
---|
431 | track_max(qual_width, shown_qual(tprobe)); |
---|
432 | track_max(grps_width, shown_qual(tprobe)); |
---|
433 | track_max(maxprobelen, tprobe->seq_len); |
---|
434 | } |
---|
435 | |
---|
436 | void clear() { |
---|
437 | for (int i = 0; i<PERC_SIZE; ++i) width[i] = 0; |
---|
438 | |
---|
439 | apos_width = 0; |
---|
440 | ecol_width = 0; |
---|
441 | qual_width = 0; |
---|
442 | grps_width = 0; |
---|
443 | |
---|
444 | maxprobelen = 0; |
---|
445 | } |
---|
446 | |
---|
447 | static inline int width4num(int num) { |
---|
448 | pt_assert(num >= 0); |
---|
449 | |
---|
450 | int digits = 0; |
---|
451 | while (num) { |
---|
452 | ++digits; |
---|
453 | num /= 10; |
---|
454 | } |
---|
455 | return digits ? digits : 1; |
---|
456 | } |
---|
457 | |
---|
458 | public: |
---|
459 | PD_formatter() { clear(); } |
---|
460 | PD_formatter(const PT_pdc *pdc) { |
---|
461 | clear(); |
---|
462 | |
---|
463 | // collect max values for output columns: |
---|
464 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; tprobe = tprobe->next) collect(tprobe); |
---|
465 | |
---|
466 | // convert max.values to needed print-width: |
---|
467 | for (int i = 0; i<PERC_SIZE; ++i) width[i] = width4num(width[i]); |
---|
468 | |
---|
469 | apos_width = std::max(width4num(apos_width), 2); |
---|
470 | ecol_width = std::max(width4num(ecol_width), 4); |
---|
471 | qual_width = std::max(width4num(qual_width), 4); |
---|
472 | grps_width = std::max(width4num(grps_width), 4); |
---|
473 | } |
---|
474 | |
---|
475 | int sprint_centigrade_list(char *buffer, const int *perc) const { |
---|
476 | // format centigrade-decrement-list |
---|
477 | int printed = 0; |
---|
478 | for (int i = 0; i<PERC_SIZE; ++i) { |
---|
479 | buffer[printed++] = ' '; |
---|
480 | printed += perc[i] |
---|
481 | ? sprintf(buffer+printed, "%*i", width[i], perc[i]) |
---|
482 | : sprintf(buffer+printed, "%*s", width[i], "-"); |
---|
483 | } |
---|
484 | return printed; |
---|
485 | } |
---|
486 | |
---|
487 | int get_max_designed_len() const { return maxprobelen; } |
---|
488 | |
---|
489 | int get_apos_width() const { return apos_width; } |
---|
490 | int get_ecol_width() const { return ecol_width; } |
---|
491 | int get_qual_width() const { return qual_width; } |
---|
492 | int get_grps_width() const { return grps_width; } |
---|
493 | }; |
---|
494 | |
---|
495 | typedef std::map<const PT_pdc*const, PD_formatter> PD_Formatter4design; |
---|
496 | static PD_Formatter4design format4design; |
---|
497 | |
---|
498 | inline const PD_formatter& get_formatter(const PT_pdc *pdc) { |
---|
499 | PD_Formatter4design::iterator found = format4design.find(pdc); |
---|
500 | if (found == format4design.end()) { |
---|
501 | format4design[pdc] = PD_formatter(pdc); |
---|
502 | found = format4design.find(pdc); |
---|
503 | } |
---|
504 | pt_assert(found != format4design.end()); |
---|
505 | |
---|
506 | return found->second; |
---|
507 | } |
---|
508 | inline void erase_formatter(const PT_pdc *pdc) { format4design.erase(pdc); } |
---|
509 | |
---|
510 | char *get_design_info(const PT_tprobes *tprobe) { |
---|
511 | pt_assert(tprobe); |
---|
512 | |
---|
513 | const int BUFFERSIZE = 2000; |
---|
514 | char *buffer = (char *)GB_give_buffer(BUFFERSIZE); |
---|
515 | PT_pdc *pdc = (PT_pdc *)tprobe->mh.parent->parent; |
---|
516 | char *p = buffer; |
---|
517 | const PD_formatter& formatter = get_formatter(pdc); |
---|
518 | |
---|
519 | // target |
---|
520 | { |
---|
521 | int len = tprobe->seq_len; |
---|
522 | char *probe = (char *)GB_give_buffer2(len+1); |
---|
523 | strcpy(probe, tprobe->sequence); |
---|
524 | |
---|
525 | probe_2_readable(probe, len); // convert probe to real ASCII |
---|
526 | p += sprintf(p, "%-*s", formatter.get_max_designed_len()+1, probe); |
---|
527 | } |
---|
528 | |
---|
529 | { |
---|
530 | int apos = shown_apos(tprobe); |
---|
531 | int c; |
---|
532 | int cs = 0; |
---|
533 | |
---|
534 | // search nearest previous hit |
---|
535 | for (c=0; c<ALPHA_SIZE; c++) { |
---|
536 | if (!pdc->pos_groups[c]) { // new group |
---|
537 | pdc->pos_groups[c] = apos; |
---|
538 | cs = '='; |
---|
539 | break; |
---|
540 | } |
---|
541 | int dist = abs(apos - pdc->pos_groups[c]); |
---|
542 | if (dist < pdc->min_probelen) { |
---|
543 | apos = apos - pdc->pos_groups[c]; |
---|
544 | if (apos >= 0) { |
---|
545 | cs = '+'; |
---|
546 | break; |
---|
547 | } |
---|
548 | cs = '-'; |
---|
549 | apos = -apos; |
---|
550 | break; |
---|
551 | } |
---|
552 | } |
---|
553 | |
---|
554 | if (cs) { |
---|
555 | c = hitgroup_idx2char(c); |
---|
556 | } |
---|
557 | else { |
---|
558 | // ran out of pos_groups |
---|
559 | c = '?'; |
---|
560 | cs = ' '; |
---|
561 | } |
---|
562 | |
---|
563 | // le apos ecol |
---|
564 | p += sprintf(p, "%2i ", tprobe->seq_len); |
---|
565 | p += sprintf(p, "%c%c%*i ", c, cs, formatter.get_apos_width(), apos); |
---|
566 | p += sprintf(p, "%*i ", formatter.get_ecol_width(), shown_ecoli(tprobe)); // ecoli-bases inclusive apos ("bases before apos+1") |
---|
567 | } |
---|
568 | |
---|
569 | p += sprintf(p, "%*i ", formatter.get_qual_width(), shown_qual(tprobe)); |
---|
570 | p += sprintf(p, "%*i ", formatter.get_grps_width(), tprobe->groupsize); |
---|
571 | p += sprintf(p, "%5.1f", ((double)pt_get_gc_content(tprobe->sequence))/tprobe->seq_len*100.0); // G+C |
---|
572 | p += sprintf(p, "%5.1f ", pt_get_temperature(tprobe->sequence)); // temperature |
---|
573 | |
---|
574 | // probe string |
---|
575 | { |
---|
576 | char *probe = create_reversed_probe(tprobe->sequence, tprobe->seq_len); |
---|
577 | complement_probe(probe, tprobe->seq_len); |
---|
578 | probe_2_readable(probe, tprobe->seq_len); // convert probe to real ASCII |
---|
579 | p += sprintf(p, "%*s |", formatter.get_max_designed_len(), probe); |
---|
580 | free(probe); |
---|
581 | } |
---|
582 | |
---|
583 | // non-group hits by temp. decrease |
---|
584 | p += formatter.sprint_centigrade_list(p, tprobe->perc); |
---|
585 | if (!tprobe->next) erase_formatter(pdc); // erase formatter when done with last probe |
---|
586 | |
---|
587 | pt_assert((p-buffer)<BUFFERSIZE); |
---|
588 | return buffer; |
---|
589 | } |
---|
590 | |
---|
591 | char *get_design_hinfo(const PT_pdc *pdc) { |
---|
592 | const int BUFFERSIZE = 2000; |
---|
593 | char *buffer = (char *)GB_give_buffer(BUFFERSIZE); |
---|
594 | char *s = buffer; |
---|
595 | |
---|
596 | const PD_formatter& formatter = get_formatter(pdc); |
---|
597 | |
---|
598 | { |
---|
599 | char *ecolipos = NULL; |
---|
600 | if (pdc->min_ecolipos == -1) { |
---|
601 | if (pdc->max_ecolipos == -1) { |
---|
602 | ecolipos = strdup("any"); |
---|
603 | } |
---|
604 | else { |
---|
605 | ecolipos = GBS_global_string_copy("<= %i", pdc->max_ecolipos); |
---|
606 | } |
---|
607 | } |
---|
608 | else { |
---|
609 | if (pdc->max_ecolipos == -1) { |
---|
610 | ecolipos = GBS_global_string_copy(">= %i", pdc->min_ecolipos); |
---|
611 | } |
---|
612 | else { |
---|
613 | ecolipos = GBS_global_string_copy("%4i -%5i", pdc->min_ecolipos, pdc->max_ecolipos); |
---|
614 | } |
---|
615 | } |
---|
616 | |
---|
617 | char *mishit_annotation = NULL; |
---|
618 | if (pdc->min_rj_mishits<INT_MAX) { |
---|
619 | mishit_annotation = GBS_global_string_copy(" (lowest rejected nongroup hits: %i)", pdc->min_rj_mishits); |
---|
620 | } |
---|
621 | |
---|
622 | char *coverage_annotation = NULL; |
---|
623 | if (pdc->max_rj_coverage>0.0) { |
---|
624 | coverage_annotation = GBS_global_string_copy(" (max. rejected coverage: %.0f%%)", pdc->max_rj_coverage*100.0); |
---|
625 | } |
---|
626 | |
---|
627 | char *probelen_info; |
---|
628 | if (get_max_probelen(pdc) == pdc->min_probelen) { |
---|
629 | probelen_info = GBS_global_string_copy("%i", pdc->min_probelen); |
---|
630 | } |
---|
631 | else { |
---|
632 | probelen_info = GBS_global_string_copy("%i-%i", pdc->min_probelen, get_max_probelen(pdc)); |
---|
633 | } |
---|
634 | |
---|
635 | s += sprintf(s, |
---|
636 | "Probe design parameters:\n" |
---|
637 | "Length of probe %s\n" |
---|
638 | "Temperature [%4.1f -%5.1f]\n" |
---|
639 | "GC-content [%4.1f -%5.1f]\n" |
---|
640 | "E.Coli position [%s]\n" |
---|
641 | "Max. nongroup hits %i%s\n" |
---|
642 | "Min. group hits %.0f%%%s\n", |
---|
643 | probelen_info, |
---|
644 | pdc->mintemp, pdc->maxtemp, |
---|
645 | pdc->min_gc*100.0, pdc->max_gc*100.0, |
---|
646 | ecolipos, |
---|
647 | pdc->max_mishits, mishit_annotation ? mishit_annotation : "", |
---|
648 | pdc->min_coverage*100.0, coverage_annotation ? coverage_annotation : ""); |
---|
649 | |
---|
650 | free(probelen_info); |
---|
651 | free(coverage_annotation); |
---|
652 | free(mishit_annotation); |
---|
653 | |
---|
654 | free(ecolipos); |
---|
655 | } |
---|
656 | |
---|
657 | if (pdc->tprobes) { |
---|
658 | int maxprobelen = formatter.get_max_designed_len(); |
---|
659 | |
---|
660 | s += sprintf(s, "%-*s", maxprobelen+1, "Target"); |
---|
661 | s += sprintf(s, "le "); |
---|
662 | s += sprintf(s, "%*s ", formatter.get_apos_width()+2, "apos"); |
---|
663 | s += sprintf(s, "%*s ", formatter.get_ecol_width(), "ecol"); |
---|
664 | s += sprintf(s, "%*s ", formatter.get_qual_width(), "qual"); |
---|
665 | s += sprintf(s, "%*s ", formatter.get_grps_width(), "grps"); |
---|
666 | s += sprintf(s, " G+C temp "); |
---|
667 | s += sprintf(s, "%*s | ", maxprobelen, maxprobelen<14 ? "Probe" : "Probe sequence"); |
---|
668 | s += sprintf(s, "Decrease T by n*.3C -> probe matches n non group species"); |
---|
669 | } |
---|
670 | else { |
---|
671 | s += sprintf(s, "No probes found!"); |
---|
672 | erase_formatter(pdc); |
---|
673 | } |
---|
674 | |
---|
675 | pt_assert((s-buffer)<BUFFERSIZE); |
---|
676 | |
---|
677 | return buffer; |
---|
678 | } |
---|
679 | |
---|
680 | struct ptnd_chain_count_mishits { |
---|
681 | int mishits; |
---|
682 | const char *probe; |
---|
683 | int height; |
---|
684 | |
---|
685 | ptnd_chain_count_mishits() : mishits(0), probe(NULL), height(0) {} |
---|
686 | ptnd_chain_count_mishits(const char *probe_, int height_) : mishits(0), probe(probe_), height(height_) {} |
---|
687 | |
---|
688 | int operator()(const AbsLoc& probeLoc) { |
---|
689 | // count all mishits for a probe |
---|
690 | |
---|
691 | psg.abs_pos.announce(probeLoc.get_abs_pos()); |
---|
692 | |
---|
693 | if (probeLoc.get_pid().outside_group()) { |
---|
694 | if (probe) { |
---|
695 | pt_assert(probe[0]); // if this case occurs, avoid entering this branch |
---|
696 | |
---|
697 | DataLoc dataLoc(probeLoc); |
---|
698 | ReadableDataLoc readableLoc(dataLoc); |
---|
699 | for (int i = 0; probe[i] && readableLoc[height+i]; ++i) { |
---|
700 | if (probe[i] != readableLoc[height+i]) return 0; |
---|
701 | } |
---|
702 | } |
---|
703 | mishits++; |
---|
704 | } |
---|
705 | return 0; |
---|
706 | } |
---|
707 | }; |
---|
708 | |
---|
709 | static int count_mishits_for_all(POS_TREE2 *pt) { |
---|
710 | //! go down the tree to chains and leafs; count the species that are in the non member group |
---|
711 | if (pt == NULL) |
---|
712 | return 0; |
---|
713 | |
---|
714 | if (pt->is_leaf()) { |
---|
715 | DataLoc loc(pt); |
---|
716 | psg.abs_pos.announce(loc.get_abs_pos()); |
---|
717 | return loc.get_pid().outside_group(); |
---|
718 | } |
---|
719 | |
---|
720 | if (pt->is_chain()) { |
---|
721 | ptnd_chain_count_mishits counter; |
---|
722 | PT_forwhole_chain(pt, counter); // @@@ expand |
---|
723 | return counter.mishits; |
---|
724 | } |
---|
725 | |
---|
726 | int mishits = 0; |
---|
727 | for (int base = PT_QU; base< PT_BASES; base++) { |
---|
728 | mishits += count_mishits_for_all(PT_read_son(pt, (PT_base)base)); |
---|
729 | } |
---|
730 | return mishits; |
---|
731 | } |
---|
732 | |
---|
733 | static int count_mishits_for_matched(char *probe, POS_TREE2 *pt, int height) { |
---|
734 | //! search down the tree to find matching species for the given probe |
---|
735 | if (!pt) return 0; |
---|
736 | if (pt->is_node() && *probe) { |
---|
737 | int mishits = 0; |
---|
738 | for (int i=PT_A; i<PT_BASES; i++) { |
---|
739 | if (i != *probe) continue; |
---|
740 | POS_TREE2 *pthelp = PT_read_son(pt, (PT_base)i); |
---|
741 | if (pthelp) mishits += count_mishits_for_matched(probe+1, pthelp, height+1); |
---|
742 | } |
---|
743 | return mishits; |
---|
744 | } |
---|
745 | if (*probe) { |
---|
746 | if (pt->is_leaf()) { |
---|
747 | const ReadableDataLoc loc(pt); |
---|
748 | |
---|
749 | int pos = loc.get_rel_pos()+height; |
---|
750 | |
---|
751 | if (pos + (int)(strlen(probe)) >= loc.get_pid().get_size()) // after end // @@@ wrong check ? better return from loop below when ref is PT_QU |
---|
752 | return 0; |
---|
753 | |
---|
754 | for (int i = 0; probe[i] && loc[height+i]; ++i) { |
---|
755 | if (probe[i] != loc[height+i]) { |
---|
756 | return 0; |
---|
757 | } |
---|
758 | } |
---|
759 | } |
---|
760 | else { // chain |
---|
761 | ptnd_chain_count_mishits counter(probe, height); |
---|
762 | PT_forwhole_chain(pt, counter); // @@@ expand |
---|
763 | return counter.mishits; |
---|
764 | } |
---|
765 | } |
---|
766 | return count_mishits_for_all(pt); |
---|
767 | } |
---|
768 | |
---|
769 | static void remove_tprobes_with_too_many_mishits(PT_pdc *pdc) { |
---|
770 | //! Check for direct mishits |
---|
771 | // tracks minimum rejected mishits in 'pdc->min_rj_mishits' |
---|
772 | int min_rej_mishit_amount = INT_MAX; |
---|
773 | |
---|
774 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; ) { |
---|
775 | PT_tprobes *tprobe_next = tprobe->next; |
---|
776 | |
---|
777 | psg.abs_pos.clear(); |
---|
778 | tprobe->mishits = count_mishits_for_matched(tprobe->sequence, psg.TREE_ROOT2(), 0); |
---|
779 | tprobe->apos = psg.abs_pos.get_most_used(); |
---|
780 | if (tprobe->mishits > pdc->max_mishits) { |
---|
781 | min_rej_mishit_amount = std::min(min_rej_mishit_amount, tprobe->mishits); |
---|
782 | destroy_PT_tprobes(tprobe); |
---|
783 | } |
---|
784 | tprobe = tprobe_next; |
---|
785 | } |
---|
786 | psg.abs_pos.clear(); |
---|
787 | |
---|
788 | pdc->min_rj_mishits = std::min(pdc->min_rj_mishits, min_rej_mishit_amount); |
---|
789 | } |
---|
790 | |
---|
791 | static void remove_tprobes_outside_ecoli_range(PT_pdc *pdc) { |
---|
792 | //! Check the probes position. |
---|
793 | // if (pdc->min_ecolipos == pdc->max_ecolipos) return; // @@@ wtf was this for? |
---|
794 | |
---|
795 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; ) { |
---|
796 | PT_tprobes *tprobe_next = tprobe->next; |
---|
797 | long relpos = PT_abs_2_ecoli_rel(tprobe->apos+1); |
---|
798 | if (relpos < pdc->min_ecolipos || (relpos > pdc->max_ecolipos && pdc->max_ecolipos != -1)) { |
---|
799 | destroy_PT_tprobes(tprobe); |
---|
800 | } |
---|
801 | tprobe = tprobe_next; |
---|
802 | } |
---|
803 | } |
---|
804 | |
---|
805 | static size_t tprobes_calculate_bonds(PT_local *locs) { |
---|
806 | /*! check the average bond size. |
---|
807 | * returns number of tprobes |
---|
808 | * |
---|
809 | * @TODO checks probe hairpin bonds |
---|
810 | */ |
---|
811 | |
---|
812 | PT_pdc *pdc = locs->pdc; |
---|
813 | size_t count = 0; |
---|
814 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; ) { |
---|
815 | PT_tprobes *tprobe_next = tprobe->next; |
---|
816 | tprobe->seq_len = strlen(tprobe->sequence); |
---|
817 | double sbond = 0.0; |
---|
818 | for (int i=0; i<tprobe->seq_len; i++) { |
---|
819 | sbond += ptnd_check_max_bond(locs, tprobe->sequence[i]); |
---|
820 | } |
---|
821 | tprobe->sum_bonds = sbond; |
---|
822 | |
---|
823 | ++count; |
---|
824 | tprobe = tprobe_next; |
---|
825 | } |
---|
826 | return count; |
---|
827 | } |
---|
828 | |
---|
829 | class CentigradePos { // track minimum centigrade position for each species |
---|
830 | typedef std::map<int, int> Pos4Name; |
---|
831 | |
---|
832 | Pos4Name cpos; // key = outgroup-species-id; value = min. centigrade position for (partial) probe |
---|
833 | |
---|
834 | public: |
---|
835 | |
---|
836 | static bool is_valid_pos(int pos) { return pos >= 0 && pos<PERC_SIZE; } |
---|
837 | |
---|
838 | void set_pos_for(int name, int pos) { |
---|
839 | pt_assert(is_valid_pos(pos)); // otherwise it should not be put into CentigradePos |
---|
840 | Pos4Name::iterator found = cpos.find(name); |
---|
841 | if (found == cpos.end()) { |
---|
842 | cpos[name] = pos; |
---|
843 | } |
---|
844 | else if (pos<found->second) { |
---|
845 | found->second = pos; |
---|
846 | } |
---|
847 | } |
---|
848 | |
---|
849 | void summarize_centigrade_hits(int *centigrade_hits) const { |
---|
850 | for (int i = 0; i<PERC_SIZE; ++i) centigrade_hits[i] = 0; |
---|
851 | for (Pos4Name::const_iterator p = cpos.begin(); p != cpos.end(); ++p) { |
---|
852 | int pos = p->second; |
---|
853 | pt_assert(is_valid_pos(pos)); // otherwise it should not be put into CentigradePos |
---|
854 | centigrade_hits[pos]++; |
---|
855 | } |
---|
856 | } |
---|
857 | |
---|
858 | bool empty() const { return cpos.empty(); } |
---|
859 | }; |
---|
860 | |
---|
861 | class OutgroupMatcher : virtual Noncopyable { |
---|
862 | const PT_pdc *const pdc; |
---|
863 | |
---|
864 | Splits splits; |
---|
865 | double max_bonds[PT_BASES]; // @@@ move functionality into Splits |
---|
866 | |
---|
867 | PT_tprobes *currTprobe; |
---|
868 | CentigradePos result; |
---|
869 | |
---|
870 | bool only_bind_behind_dot; // true for suffix-matching |
---|
871 | |
---|
872 | void uncond_announce_match(int centPos, const AbsLoc& loc) { |
---|
873 | pt_assert(loc.get_pid().outside_group()); |
---|
874 | #if defined(DUMP_OLIGO_MATCHING) |
---|
875 | fprintf(stderr, "announce_match centPos=%2i loc", centPos); |
---|
876 | loc.dump(stderr); |
---|
877 | fflush_all(); |
---|
878 | #endif |
---|
879 | result.set_pos_for(loc.get_name(), centPos); |
---|
880 | } |
---|
881 | |
---|
882 | bool location_follows_dot(const ReadableDataLoc& loc) const { return loc[-1] == PT_QU; } |
---|
883 | bool location_follows_dot(const DataLoc& loc) const { return location_follows_dot(ReadableDataLoc(loc)); } // very expensive @@@ optimize using relpos |
---|
884 | bool location_follows_dot(const AbsLoc& loc) const { return location_follows_dot(ReadableDataLoc(DataLoc(loc))); } // very very expensive |
---|
885 | |
---|
886 | template<typename LOC> |
---|
887 | bool acceptable_location(const LOC& loc) const { |
---|
888 | return loc.get_pid().outside_group() && |
---|
889 | (only_bind_behind_dot ? location_follows_dot(loc) : true); |
---|
890 | } |
---|
891 | |
---|
892 | template<typename LOC> |
---|
893 | void announce_match_if_acceptable(int centPos, const LOC& loc) { |
---|
894 | if (acceptable_location(loc)) { |
---|
895 | uncond_announce_match(centPos, loc); |
---|
896 | } |
---|
897 | } |
---|
898 | void announce_match_if_acceptable(int centPos, POS_TREE2 *pt) { |
---|
899 | switch (pt->get_type()) { |
---|
900 | case PT2_NODE: |
---|
901 | for (int i = PT_QU; i<PT_BASES; ++i) { |
---|
902 | POS_TREE2 *ptson = PT_read_son(pt, (PT_base)i); |
---|
903 | if (ptson) { |
---|
904 | announce_match_if_acceptable(centPos, ptson); |
---|
905 | } |
---|
906 | } |
---|
907 | break; |
---|
908 | |
---|
909 | case PT2_LEAF: |
---|
910 | announce_match_if_acceptable(centPos, DataLoc(pt)); |
---|
911 | break; |
---|
912 | |
---|
913 | case PT2_CHAIN: { |
---|
914 | ChainIteratorStage2 iter(pt); |
---|
915 | while (iter) { |
---|
916 | announce_match_if_acceptable(centPos, iter.at()); |
---|
917 | ++iter; |
---|
918 | } |
---|
919 | break; |
---|
920 | } |
---|
921 | } |
---|
922 | } |
---|
923 | |
---|
924 | template <typename PT_OR_LOC> |
---|
925 | void announce_possible_match(const MatchingOligo& oligo, PT_OR_LOC pt_or_loc) { |
---|
926 | pt_assert(oligo.domainSeen()); |
---|
927 | pt_assert(!oligo.dangling()); |
---|
928 | |
---|
929 | int centPos = oligo.calc_centigrade_pos(currTprobe, pdc); |
---|
930 | if (centPos<PERC_SIZE) { |
---|
931 | announce_match_if_acceptable(centPos, pt_or_loc); |
---|
932 | } |
---|
933 | } |
---|
934 | |
---|
935 | bool might_reach_centigrade_pos(const MatchingOligo& oligo) const { |
---|
936 | return !oligo.centigrade_pos_out_of_reach(currTprobe, pdc, splits, max_bonds); |
---|
937 | } |
---|
938 | |
---|
939 | void bind_rest(const MatchingOligo& oligo, const ReadableDataLoc& loc, const int height) { |
---|
940 | // unconditionally bind rest of oligo versus sequence |
---|
941 | |
---|
942 | pt_assert(oligo.domainSeen()); // entry-invariant for bind_rest() |
---|
943 | pt_assert(oligo.dangling()); // otherwise ReadableDataLoc is constructed w/o need (very expensive!) |
---|
944 | pt_assert(might_reach_centigrade_pos(oligo)); // otherwise ReadableDataLoc is constructed w/o need (very expensive!) |
---|
945 | pt_assert(loc.get_pid().outside_group()); // otherwise we are not interested in the result |
---|
946 | |
---|
947 | if (loc[height]) { |
---|
948 | MatchingOligo more = oligo.bind_against(loc[height], splits, max_bonds); |
---|
949 | pt_assert(more.domainSeen()); // implied by oligo.domainSeen() |
---|
950 | if (more.dangling()) { |
---|
951 | if (might_reach_centigrade_pos(more)) { |
---|
952 | bind_rest(more, loc, height+1); |
---|
953 | } |
---|
954 | } |
---|
955 | else { |
---|
956 | announce_possible_match(more, loc); |
---|
957 | } |
---|
958 | } |
---|
959 | else { |
---|
960 | MatchingOligo all = oligo.dont_bind_rest(); |
---|
961 | announce_possible_match(all, loc); |
---|
962 | } |
---|
963 | } |
---|
964 | void bind_rest_if_outside_group(const MatchingOligo& oligo, const DataLoc& loc, const int height) { |
---|
965 | if (loc.get_pid().outside_group() && might_reach_centigrade_pos(oligo)) { |
---|
966 | bind_rest(oligo, ReadableDataLoc(loc), height); |
---|
967 | } |
---|
968 | } |
---|
969 | void bind_rest_if_outside_group(const MatchingOligo& oligo, const AbsLoc& loc, const int height) { |
---|
970 | if (loc.get_pid().outside_group() && might_reach_centigrade_pos(oligo)) { |
---|
971 | bind_rest(oligo, ReadableDataLoc(DataLoc(loc)), height); |
---|
972 | } |
---|
973 | } |
---|
974 | |
---|
975 | void bind_rest(const MatchingOligo& oligo, POS_TREE2 *pt, const int height) { |
---|
976 | // unconditionally bind rest of oligo versus complete index-subtree |
---|
977 | pt_assert(oligo.domainSeen()); // entry-invariant for bind_rest() |
---|
978 | |
---|
979 | if (oligo.dangling()) { |
---|
980 | if (might_reach_centigrade_pos(oligo)) { |
---|
981 | switch (pt->get_type()) { |
---|
982 | case PT2_NODE: { |
---|
983 | POS_TREE2 *ptdotson = PT_read_son(pt, PT_QU); |
---|
984 | if (ptdotson) { |
---|
985 | MatchingOligo all = oligo.dont_bind_rest(); |
---|
986 | announce_possible_match(all, ptdotson); |
---|
987 | } |
---|
988 | |
---|
989 | for (int i = PT_A; i<PT_BASES; ++i) { |
---|
990 | POS_TREE2 *ptson = PT_read_son(pt, (PT_base)i); |
---|
991 | if (ptson) { |
---|
992 | bind_rest(oligo.bind_against(i, splits, max_bonds), ptson, height+1); |
---|
993 | } |
---|
994 | } |
---|
995 | break; |
---|
996 | } |
---|
997 | case PT2_LEAF: |
---|
998 | bind_rest_if_outside_group(oligo, DataLoc(pt), height); |
---|
999 | break; |
---|
1000 | |
---|
1001 | case PT2_CHAIN: |
---|
1002 | ChainIteratorStage2 iter(pt); |
---|
1003 | while (iter) { |
---|
1004 | bind_rest_if_outside_group(oligo, iter.at(), height); |
---|
1005 | ++iter; |
---|
1006 | } |
---|
1007 | break; |
---|
1008 | } |
---|
1009 | } |
---|
1010 | } |
---|
1011 | else { |
---|
1012 | announce_possible_match(oligo, pt); |
---|
1013 | } |
---|
1014 | } |
---|
1015 | |
---|
1016 | void bind_till_domain(const MatchingOligo& oligo, const ReadableDataLoc& loc, const int height) { |
---|
1017 | pt_assert(!oligo.domainSeen() && oligo.domainPossible()); // entry-invariant for bind_till_domain() |
---|
1018 | pt_assert(oligo.dangling()); // otherwise ReadableDataLoc is constructed w/o need (very expensive!) |
---|
1019 | pt_assert(might_reach_centigrade_pos(oligo)); // otherwise ReadableDataLoc is constructed w/o need (very expensive!) |
---|
1020 | pt_assert(loc.get_pid().outside_group()); // otherwise we are not interested in the result |
---|
1021 | |
---|
1022 | if (is_std_base(loc[height])) { // do not try to bind domain versus dot or N |
---|
1023 | MatchingOligo more = oligo.bind_against(loc[height], splits, max_bonds); |
---|
1024 | if (more.dangling()) { |
---|
1025 | if (might_reach_centigrade_pos(more)) { |
---|
1026 | if (more.domainSeen()) bind_rest (more, loc, height+1); |
---|
1027 | else if (more.domainPossible()) bind_till_domain(more, loc, height+1); |
---|
1028 | } |
---|
1029 | } |
---|
1030 | else if (more.domainSeen()) { |
---|
1031 | announce_possible_match(more, loc); |
---|
1032 | } |
---|
1033 | } |
---|
1034 | } |
---|
1035 | void bind_till_domain_if_outside_group(const MatchingOligo& oligo, const DataLoc& loc, const int height) { |
---|
1036 | if (loc.get_pid().outside_group() && might_reach_centigrade_pos(oligo)) { |
---|
1037 | bind_till_domain(oligo, ReadableDataLoc(loc), height); |
---|
1038 | } |
---|
1039 | } |
---|
1040 | void bind_till_domain_if_outside_group(const MatchingOligo& oligo, const AbsLoc& loc, const int height) { |
---|
1041 | if (loc.get_pid().outside_group() && might_reach_centigrade_pos(oligo)) { |
---|
1042 | bind_till_domain(oligo, ReadableDataLoc(DataLoc(loc)), height); |
---|
1043 | } |
---|
1044 | } |
---|
1045 | |
---|
1046 | void bind_till_domain(const MatchingOligo& oligo, POS_TREE2 *pt, const int height) { |
---|
1047 | pt_assert(!oligo.domainSeen() && oligo.domainPossible()); // entry-invariant for bind_till_domain() |
---|
1048 | pt_assert(oligo.dangling()); |
---|
1049 | |
---|
1050 | if (might_reach_centigrade_pos(oligo)) { |
---|
1051 | switch (pt->get_type()) { |
---|
1052 | case PT2_NODE: |
---|
1053 | for (int i = PT_A; i<PT_BASES; ++i) { |
---|
1054 | POS_TREE2 *ptson = PT_read_son(pt, (PT_base)i); |
---|
1055 | if (ptson) { |
---|
1056 | MatchingOligo sonOligo = oligo.bind_against(i, splits, max_bonds); |
---|
1057 | |
---|
1058 | if (sonOligo.domainSeen()) bind_rest (sonOligo, ptson, height+1); |
---|
1059 | else if (sonOligo.domainPossible()) bind_till_domain(sonOligo, ptson, height+1); |
---|
1060 | } |
---|
1061 | } |
---|
1062 | break; |
---|
1063 | |
---|
1064 | case PT2_LEAF: |
---|
1065 | bind_till_domain_if_outside_group(oligo, DataLoc(pt), height); |
---|
1066 | break; |
---|
1067 | |
---|
1068 | case PT2_CHAIN: |
---|
1069 | ChainIteratorStage2 iter(pt); |
---|
1070 | while (iter) { |
---|
1071 | bind_till_domain_if_outside_group(oligo, iter.at(), height); |
---|
1072 | ++iter; |
---|
1073 | } |
---|
1074 | break; |
---|
1075 | } |
---|
1076 | } |
---|
1077 | } |
---|
1078 | |
---|
1079 | void reset() { result = CentigradePos(); } |
---|
1080 | |
---|
1081 | public: |
---|
1082 | OutgroupMatcher(PT_local *locs_, PT_pdc *pdc_) |
---|
1083 | : pdc(pdc_), |
---|
1084 | splits(locs_), |
---|
1085 | currTprobe(NULL), |
---|
1086 | only_bind_behind_dot(false) |
---|
1087 | { |
---|
1088 | for (int i = PT_QU; i<PT_BASES; ++i) { |
---|
1089 | max_bonds[i] = ptnd_check_max_bond(locs_, i); |
---|
1090 | } |
---|
1091 | } |
---|
1092 | |
---|
1093 | void calculate_outgroup_matches(PT_tprobes& tprobe) { |
---|
1094 | LocallyModify<PT_tprobes*> assign_tprobe(currTprobe, &tprobe); |
---|
1095 | pt_assert(result.empty()); |
---|
1096 | |
---|
1097 | MatchingOligo fullProbe(Oligo(tprobe.sequence, tprobe.seq_len)); |
---|
1098 | POS_TREE2 *ptroot = psg.TREE_ROOT2(); |
---|
1099 | |
---|
1100 | pt_assert(!fullProbe.domainSeen()); |
---|
1101 | pt_assert(fullProbe.domainPossible()); // probe length too short (probes shorter than DOMAIN_MIN_LENGTH always report 0 outgroup hits -> wrong result) |
---|
1102 | |
---|
1103 | arb_progress progress(tprobe.seq_len); |
---|
1104 | |
---|
1105 | only_bind_behind_dot = false; |
---|
1106 | bind_till_domain(fullProbe, ptroot, 0); |
---|
1107 | ++progress; |
---|
1108 | |
---|
1109 | // match all suffixes of probe |
---|
1110 | // - detect possible partial matches at start of alignment (and behind dots inside the sequence) |
---|
1111 | only_bind_behind_dot = true; |
---|
1112 | for (int off = 1; off<tprobe.seq_len; ++off) { |
---|
1113 | MatchingOligo probeSuffix(fullProbe.get_oligo().suffix(off)); |
---|
1114 | if (!probeSuffix.domainPossible()) break; // abort - no smaller suffix may create a domain |
---|
1115 | bind_till_domain(probeSuffix, ptroot, 0); |
---|
1116 | ++progress; |
---|
1117 | } |
---|
1118 | |
---|
1119 | result.summarize_centigrade_hits(tprobe.perc); |
---|
1120 | progress.done(); |
---|
1121 | |
---|
1122 | reset(); |
---|
1123 | } |
---|
1124 | }; |
---|
1125 | |
---|
1126 | class ProbeOccurrance { |
---|
1127 | const char *seq; |
---|
1128 | |
---|
1129 | public: |
---|
1130 | ProbeOccurrance(const char *seq_) : seq(seq_) {} |
---|
1131 | |
---|
1132 | const char *sequence() const { return seq; } |
---|
1133 | |
---|
1134 | void forward() { ++seq; } |
---|
1135 | |
---|
1136 | bool less(const ProbeOccurrance& other, size_t len) const { |
---|
1137 | const char *mine = sequence(); |
---|
1138 | const char *his = other.sequence(); |
---|
1139 | |
---|
1140 | int cmp = 0; |
---|
1141 | for (size_t i = 0; i<len && !cmp; ++i) { |
---|
1142 | cmp = mine[i]-his[i]; |
---|
1143 | } |
---|
1144 | return cmp<0; |
---|
1145 | } |
---|
1146 | }; |
---|
1147 | |
---|
1148 | class ProbeIterator { |
---|
1149 | ProbeOccurrance cursor; |
---|
1150 | |
---|
1151 | size_t probelen; |
---|
1152 | size_t rest; // size of seqpart behind cursor |
---|
1153 | size_t gc, at; // count G+C and A+T |
---|
1154 | |
---|
1155 | bool has_only_std_bases() const { return (gc+at) == probelen; } |
---|
1156 | |
---|
1157 | bool at_end() const { return !rest; } |
---|
1158 | |
---|
1159 | PT_base base_at(size_t offset) const { |
---|
1160 | pt_assert(offset < probelen); |
---|
1161 | return PT_base(cursor.sequence()[offset]); |
---|
1162 | } |
---|
1163 | |
---|
1164 | void forget(PT_base b) { |
---|
1165 | switch (b) { |
---|
1166 | case PT_A: case PT_T: pt_assert(at>0); --at; break; |
---|
1167 | case PT_C: case PT_G: pt_assert(gc>0); --gc; break; |
---|
1168 | default : break; |
---|
1169 | } |
---|
1170 | } |
---|
1171 | void count(PT_base b) { |
---|
1172 | switch (b) { |
---|
1173 | case PT_A: case PT_T: ++at; break; |
---|
1174 | case PT_C: case PT_G: ++gc; break; |
---|
1175 | default : break; |
---|
1176 | } |
---|
1177 | } |
---|
1178 | |
---|
1179 | void init_counts() { |
---|
1180 | at = gc = 0; |
---|
1181 | for (size_t i = 0; i<probelen; ++i) { |
---|
1182 | count(base_at(i)); |
---|
1183 | } |
---|
1184 | } |
---|
1185 | |
---|
1186 | public: |
---|
1187 | ProbeIterator(const char *seq, size_t seqlen, size_t probelen_) |
---|
1188 | : cursor(seq), |
---|
1189 | probelen(probelen_), |
---|
1190 | rest(seqlen-probelen) |
---|
1191 | { |
---|
1192 | pt_assert(seqlen >= probelen); |
---|
1193 | init_counts(); |
---|
1194 | } |
---|
1195 | |
---|
1196 | bool next() { |
---|
1197 | if (at_end()) return false; |
---|
1198 | forget(base_at(0)); |
---|
1199 | cursor.forward(); |
---|
1200 | --rest; |
---|
1201 | count(base_at(probelen-1)); |
---|
1202 | return true; |
---|
1203 | } |
---|
1204 | |
---|
1205 | int get_temperature() const { return 2*at + 4*gc; } |
---|
1206 | |
---|
1207 | bool gc_in_wanted_range(PT_pdc *pdc) const { |
---|
1208 | return pdc->min_gc*probelen <= gc && gc <= pdc->max_gc*probelen; |
---|
1209 | } |
---|
1210 | bool temperature_in_wanted_range(PT_pdc *pdc) const { |
---|
1211 | int temp = get_temperature(); |
---|
1212 | return pdc->mintemp <= temp && temp <= pdc->maxtemp; |
---|
1213 | } |
---|
1214 | |
---|
1215 | bool feasible(PT_pdc *pdc) const { |
---|
1216 | return has_only_std_bases() && |
---|
1217 | gc_in_wanted_range(pdc) && |
---|
1218 | temperature_in_wanted_range(pdc); |
---|
1219 | } |
---|
1220 | |
---|
1221 | const ProbeOccurrance& occurance() const { return cursor; } |
---|
1222 | |
---|
1223 | void dump(FILE *out) const { |
---|
1224 | char *probe = readable_probe(cursor.sequence(), probelen, 'T'); |
---|
1225 | fprintf(out, "probe='%s' probelen=%zu at=%zu gc=%zu\n", probe, probelen, at, gc); |
---|
1226 | free(probe); |
---|
1227 | } |
---|
1228 | }; |
---|
1229 | |
---|
1230 | class PO_Less { |
---|
1231 | size_t probelen; |
---|
1232 | public: |
---|
1233 | PO_Less(size_t probelen_) : probelen(probelen_) {} |
---|
1234 | bool operator()(const ProbeOccurrance& a, const ProbeOccurrance& b) const { return a.less(b, probelen); } |
---|
1235 | }; |
---|
1236 | |
---|
1237 | struct SCP_Less { |
---|
1238 | bool operator()(const SmartCharPtr& p1, const SmartCharPtr& p2) { return &*p1 < &*p2; } // simply compare addresses |
---|
1239 | }; |
---|
1240 | |
---|
1241 | class ProbeCandidates { |
---|
1242 | typedef std::set<ProbeOccurrance, PO_Less> Candidates; |
---|
1243 | typedef std::map<ProbeOccurrance, int, PO_Less> CandidateHits; |
---|
1244 | typedef std::set<SmartCharPtr, SCP_Less> SeqData; |
---|
1245 | |
---|
1246 | size_t probelen; |
---|
1247 | CandidateHits candidateHits; |
---|
1248 | SeqData data; // locks SmartPtrs to input data (ProbeOccurrances point inside their data) |
---|
1249 | |
---|
1250 | public: |
---|
1251 | ProbeCandidates(size_t probelen_) |
---|
1252 | : probelen(probelen_), |
---|
1253 | candidateHits(probelen) |
---|
1254 | {} |
---|
1255 | |
---|
1256 | void generate_for_sequence(PT_pdc *pdc, const SmartCharPtr& seq, size_t bp) { |
---|
1257 | arb_progress base_progress(2*bp); |
---|
1258 | if (bp >= probelen) { |
---|
1259 | // collect all probe candidates for current sequence |
---|
1260 | Candidates candidates(probelen); |
---|
1261 | { |
---|
1262 | data.insert(seq); |
---|
1263 | ProbeIterator probe(&*seq, bp, probelen); |
---|
1264 | do { |
---|
1265 | if (probe.feasible(pdc)) { |
---|
1266 | candidates.insert(probe.occurance()); |
---|
1267 | ++base_progress; |
---|
1268 | } |
---|
1269 | } while (probe.next()); |
---|
1270 | } |
---|
1271 | |
---|
1272 | // increment overall hitcount for each found candidate |
---|
1273 | for (Candidates::iterator c = candidates.begin(); c != candidates.end(); ++c) { |
---|
1274 | candidateHits[*c]++; |
---|
1275 | ++base_progress; |
---|
1276 | } |
---|
1277 | } |
---|
1278 | base_progress.done(); |
---|
1279 | } |
---|
1280 | |
---|
1281 | void create_tprobes(PT_pdc *pdc, int ingroup_size) { |
---|
1282 | // tracks maximum rejected target-group coverage |
---|
1283 | int min_ingroup_hits = (ingroup_size * pdc->min_coverage + .5); |
---|
1284 | int max_rej_ingroup_hits = 0; |
---|
1285 | |
---|
1286 | for (CandidateHits::iterator c = candidateHits.begin(); c != candidateHits.end(); ++c) { |
---|
1287 | int ingroup_hits = c->second; |
---|
1288 | if (ingroup_hits >= min_ingroup_hits) { |
---|
1289 | const ProbeOccurrance& candi = c->first; |
---|
1290 | |
---|
1291 | PT_tprobes *tprobe = create_PT_tprobes(); |
---|
1292 | |
---|
1293 | tprobe->sequence = GB_strndup(candi.sequence(), probelen); |
---|
1294 | tprobe->temp = pt_get_temperature(tprobe->sequence); |
---|
1295 | tprobe->groupsize = ingroup_hits; |
---|
1296 | |
---|
1297 | aisc_link(&pdc->ptprobes, tprobe); |
---|
1298 | } |
---|
1299 | else { |
---|
1300 | max_rej_ingroup_hits = std::max(max_rej_ingroup_hits, ingroup_hits); |
---|
1301 | } |
---|
1302 | } |
---|
1303 | |
---|
1304 | double max_rejected_coverage = max_rej_ingroup_hits/double(ingroup_size); |
---|
1305 | pdc->max_rj_coverage = std::max(pdc->max_rj_coverage, max_rejected_coverage); |
---|
1306 | } |
---|
1307 | }; |
---|
1308 | |
---|
1309 | class DesignTargets : virtual Noncopyable { |
---|
1310 | PT_pdc *pdc; |
---|
1311 | |
---|
1312 | int targets; // overall target sequence count |
---|
1313 | int known_targets; // known target sequences |
---|
1314 | int added_targets; // added (=unknown) target sequences |
---|
1315 | |
---|
1316 | long datasize; // overall bp of target sequences |
---|
1317 | |
---|
1318 | int min_probe_length; // min. designed probe length |
---|
1319 | |
---|
1320 | int *known2id; |
---|
1321 | |
---|
1322 | ARB_ERROR error; |
---|
1323 | |
---|
1324 | void announce_seq_bp(long bp) { |
---|
1325 | pt_assert(!error); |
---|
1326 | if (bp<long(min_probe_length)) { |
---|
1327 | error = GBS_global_string("Sequence contains only %lu bp. Impossible design request for", bp); |
---|
1328 | } |
---|
1329 | else { |
---|
1330 | datasize += bp; |
---|
1331 | if (datasize<bp) datasize = ULONG_MAX; |
---|
1332 | } |
---|
1333 | } |
---|
1334 | |
---|
1335 | void scan_added_targets() { |
---|
1336 | added_targets = 0; |
---|
1337 | for (PT_sequence *seq = pdc->sequences; seq && !error; seq = seq->next) { |
---|
1338 | announce_seq_bp(seq->seq.size); |
---|
1339 | ++added_targets; |
---|
1340 | } |
---|
1341 | if (error) error = GBS_global_string("%s one of the added sequences", error.deliver()); |
---|
1342 | } |
---|
1343 | void scan_known_targets(int expected_known_targets) { |
---|
1344 | known2id = new int[expected_known_targets]; |
---|
1345 | known_targets = 0; |
---|
1346 | |
---|
1347 | for (int id = 0; id < psg.data_count && !error; ++id) { |
---|
1348 | const probe_input_data& pid = psg.data[id]; |
---|
1349 | if (pid.inside_group()) { |
---|
1350 | announce_seq_bp(pid.get_size()); |
---|
1351 | known2id[known_targets++] = id; |
---|
1352 | pt_assert(known_targets <= expected_known_targets); |
---|
1353 | if (error) error = GBS_global_string("%s species '%s'", error.deliver(), pid.get_shortname()); |
---|
1354 | } |
---|
1355 | } |
---|
1356 | } |
---|
1357 | |
---|
1358 | public: |
---|
1359 | DesignTargets(PT_pdc *pdc_, int expected_known_targets) |
---|
1360 | : pdc(pdc_), |
---|
1361 | targets(0), |
---|
1362 | known_targets(0), |
---|
1363 | datasize(0), |
---|
1364 | min_probe_length(pdc->min_probelen), |
---|
1365 | known2id(NULL) |
---|
1366 | { |
---|
1367 | scan_added_targets(); // calc added_targets |
---|
1368 | if (!error) { |
---|
1369 | scan_known_targets(expected_known_targets); |
---|
1370 | targets = known_targets+added_targets; |
---|
1371 | } |
---|
1372 | } |
---|
1373 | ~DesignTargets() { |
---|
1374 | delete [] known2id; |
---|
1375 | } |
---|
1376 | ARB_ERROR& get_error() { return error; } // needs to be checked after construction! |
---|
1377 | |
---|
1378 | long get_datasize() const { return datasize; } |
---|
1379 | int get_count() const { return targets; } |
---|
1380 | int get_known_count() const { return known_targets; } |
---|
1381 | int get_added_count() const { return added_targets; } |
---|
1382 | |
---|
1383 | void generate(ProbeCandidates& candidates) { |
---|
1384 | arb_progress progress(get_count()); |
---|
1385 | for (int k = 0; k<known_targets; ++k) { |
---|
1386 | const probe_input_data& pid = psg.data[known2id[k]]; |
---|
1387 | candidates.generate_for_sequence(pdc, pid.get_dataPtr(), pid.get_size()); |
---|
1388 | ++progress; |
---|
1389 | } |
---|
1390 | for (PT_sequence *seq = pdc->sequences; seq; seq = seq->next) { |
---|
1391 | candidates.generate_for_sequence(pdc, GB_strndup(seq->seq.data, seq->seq.size), seq->seq.size); |
---|
1392 | ++progress; |
---|
1393 | } |
---|
1394 | } |
---|
1395 | }; |
---|
1396 | |
---|
1397 | #if defined(DUMP_DESIGNED_PROBES) |
---|
1398 | static void dump_tprobe(PT_tprobes *tprobe, int idx) { |
---|
1399 | char *readable = readable_probe(tprobe->sequence, tprobe->seq_len, 'T'); |
---|
1400 | fprintf(stderr, "tprobe='%s' idx=%i len=%i\n", readable, idx, tprobe->seq_len); |
---|
1401 | free(readable); |
---|
1402 | } |
---|
1403 | static void DUMP_TPROBES(const char *where, PT_pdc *pdc) { |
---|
1404 | int idx = 0; |
---|
1405 | fprintf(stderr, "dumping tprobes %s:\n", where); |
---|
1406 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; tprobe = tprobe->next) { |
---|
1407 | dump_tprobe(tprobe, idx++); |
---|
1408 | } |
---|
1409 | } |
---|
1410 | #else |
---|
1411 | #define DUMP_TPROBES(a,b) |
---|
1412 | #endif |
---|
1413 | |
---|
1414 | int PT_start_design(PT_pdc *pdc, int /* dummy */) { |
---|
1415 | PT_local *locs = (PT_local*)pdc->mh.parent->parent; |
---|
1416 | |
---|
1417 | erase_formatter(pdc); |
---|
1418 | while (pdc->tprobes) destroy_PT_tprobes(pdc->tprobes); |
---|
1419 | |
---|
1420 | for (PT_sequence *seq = pdc->sequences; seq; seq = seq->next) { // Convert all external sequence to internal format |
---|
1421 | seq->seq.size = probe_compress_sequence(seq->seq.data, seq->seq.size-1); // no longer convert final zero-byte (PT_QU gets auto-appended) |
---|
1422 | } |
---|
1423 | |
---|
1424 | ARB_ERROR error; |
---|
1425 | int unknown_species_count = 0; |
---|
1426 | { |
---|
1427 | char *unknown_names = ptpd_read_names(locs, pdc->names.data, pdc->checksums.data, error); // read the names |
---|
1428 | if (unknown_names) { |
---|
1429 | ConstStrArray names; |
---|
1430 | GBT_splitNdestroy_string(names, unknown_names, "#", true); |
---|
1431 | pt_assert(!unknown_names); |
---|
1432 | unknown_species_count = names.size(); |
---|
1433 | } |
---|
1434 | } |
---|
1435 | |
---|
1436 | if (!error) { |
---|
1437 | DesignTargets targets(pdc, locs->group_count); // here locs->group_count is amount of known marked species/genes |
---|
1438 | error = targets.get_error(); |
---|
1439 | |
---|
1440 | if (!error) { |
---|
1441 | locs->group_count = targets.get_count(); |
---|
1442 | if (locs->group_count <= 0) { |
---|
1443 | error = GBS_global_string("No %s marked - no probes designed", gene_flag ? "genes" : "species"); |
---|
1444 | } |
---|
1445 | else if (targets.get_added_count() != unknown_species_count) { |
---|
1446 | if (gene_flag) { // cannot add genes |
---|
1447 | pt_assert(targets.get_added_count() == 0); // cannot, but did add?! |
---|
1448 | error = GBS_global_string("Cannot design probes for %i unknown marked genes", unknown_species_count); |
---|
1449 | } |
---|
1450 | else { |
---|
1451 | int added = targets.get_added_count(); |
---|
1452 | error = GBS_global_string("Got %i unknown marked species, but %i custom sequence%s added (has to match)", |
---|
1453 | unknown_species_count, |
---|
1454 | added, |
---|
1455 | added == 1 ? " was" : "s were"); |
---|
1456 | } |
---|
1457 | } |
---|
1458 | else if (pdc->min_probelen < MIN_DESIGN_PROBE_LENGTH) { |
---|
1459 | error = GBS_global_string("Specified min. probe length %i is below the min. allowed probe length of %i", pdc->min_probelen, MIN_DESIGN_PROBE_LENGTH); |
---|
1460 | } |
---|
1461 | else if (get_max_probelen(pdc) < pdc->min_probelen) { |
---|
1462 | error = GBS_global_string("Max. probe length %i is below the specified min. probe length of %i", get_max_probelen(pdc), pdc->min_probelen); |
---|
1463 | } |
---|
1464 | else { |
---|
1465 | // search for possible probes |
---|
1466 | if (!error) { |
---|
1467 | int min_probelen = pdc->min_probelen; |
---|
1468 | int max_probelen = get_max_probelen(pdc); |
---|
1469 | |
---|
1470 | arb_progress progress("Searching probe candidates", max_probelen-min_probelen+1); |
---|
1471 | for (int len = min_probelen; len <= max_probelen; ++len) { |
---|
1472 | ProbeCandidates candidates(len); |
---|
1473 | |
---|
1474 | targets.generate(candidates); |
---|
1475 | pt_assert(!targets.get_error()); |
---|
1476 | |
---|
1477 | candidates.create_tprobes(pdc, targets.get_count()); |
---|
1478 | ++progress; |
---|
1479 | } |
---|
1480 | } |
---|
1481 | |
---|
1482 | while (pdc->sequences) destroy_PT_sequence(pdc->sequences); |
---|
1483 | |
---|
1484 | if (!error) { |
---|
1485 | sort_tprobes_by(pdc, PSM_SEQUENCE); |
---|
1486 | remove_tprobes_with_too_many_mishits(pdc); |
---|
1487 | remove_tprobes_outside_ecoli_range(pdc); |
---|
1488 | size_t tprobes = tprobes_calculate_bonds(locs); |
---|
1489 | DUMP_TPROBES("after tprobes_calculate_bonds", pdc); |
---|
1490 | |
---|
1491 | if (tprobes) { |
---|
1492 | arb_progress progress(GBS_global_string("Calculating probe quality for %zu probe candidates", tprobes), tprobes); |
---|
1493 | OutgroupMatcher om(locs, pdc); |
---|
1494 | for (PT_tprobes *tprobe = pdc->tprobes; tprobe; tprobe = tprobe->next) { |
---|
1495 | om.calculate_outgroup_matches(*tprobe); |
---|
1496 | ++progress; |
---|
1497 | } |
---|
1498 | } |
---|
1499 | else { |
---|
1500 | fputs("No probe candidates found\n", stdout); |
---|
1501 | } |
---|
1502 | |
---|
1503 | tprobes_sumup_perc_and_calc_quality(pdc); |
---|
1504 | sort_tprobes_by(pdc, PSM_QUALITY); |
---|
1505 | clip_tprobes(pdc, pdc->clipresult); |
---|
1506 | } |
---|
1507 | } |
---|
1508 | } |
---|
1509 | } |
---|
1510 | |
---|
1511 | pt_export_error_if(locs, error); |
---|
1512 | return 0; |
---|
1513 | } |
---|
1514 | |
---|
1515 | // -------------------------------------------------------------------------------- |
---|
1516 | |
---|
1517 | #ifdef UNIT_TESTS |
---|
1518 | #ifndef TEST_UNIT_H |
---|
1519 | #include <test_unit.h> |
---|
1520 | #endif |
---|
1521 | |
---|
1522 | static const char *concat_iteration(PrefixIterator& prefix) { |
---|
1523 | static GBS_strstruct out(50); |
---|
1524 | |
---|
1525 | out.erase(); |
---|
1526 | |
---|
1527 | while (!prefix.done()) { |
---|
1528 | if (out.filled()) out.put(','); |
---|
1529 | |
---|
1530 | char *readable = probe_2_readable(prefix.copy(), prefix.length()); |
---|
1531 | out.cat(readable); |
---|
1532 | free(readable); |
---|
1533 | |
---|
1534 | ++prefix; |
---|
1535 | } |
---|
1536 | |
---|
1537 | return out.get_data(); |
---|
1538 | } |
---|
1539 | |
---|
1540 | void TEST_PrefixIterator() { |
---|
1541 | // straight-forward permutation |
---|
1542 | PrefixIterator p0(PT_A, PT_T, 0); TEST_EXPECT_EQUAL(p0.steps(), 1); |
---|
1543 | PrefixIterator p1(PT_A, PT_T, 1); TEST_EXPECT_EQUAL(p1.steps(), 4); |
---|
1544 | PrefixIterator p2(PT_A, PT_T, 2); TEST_EXPECT_EQUAL(p2.steps(), 16); |
---|
1545 | PrefixIterator p3(PT_A, PT_T, 3); TEST_EXPECT_EQUAL(p3.steps(), 64); |
---|
1546 | |
---|
1547 | TEST_EXPECT_EQUAL(p1.done(), false); |
---|
1548 | TEST_EXPECT_EQUAL(p0.done(), false); |
---|
1549 | |
---|
1550 | TEST_EXPECT_EQUAL(concat_iteration(p0), ""); |
---|
1551 | TEST_EXPECT_EQUAL(concat_iteration(p1), "A,C,G,U"); |
---|
1552 | TEST_EXPECT_EQUAL(concat_iteration(p2), "AA,AC,AG,AU,CA,CC,CG,CU,GA,GC,GG,GU,UA,UC,UG,UU"); |
---|
1553 | |
---|
1554 | // permutation truncated at PT_QU |
---|
1555 | PrefixIterator q0(PT_QU, PT_T, 0); TEST_EXPECT_EQUAL(q0.steps(), 1); |
---|
1556 | PrefixIterator q1(PT_QU, PT_T, 1); TEST_EXPECT_EQUAL(q1.steps(), 6); |
---|
1557 | PrefixIterator q2(PT_QU, PT_T, 2); TEST_EXPECT_EQUAL(q2.steps(), 31); |
---|
1558 | PrefixIterator q3(PT_QU, PT_T, 3); TEST_EXPECT_EQUAL(q3.steps(), 156); |
---|
1559 | PrefixIterator q4(PT_QU, PT_T, 4); TEST_EXPECT_EQUAL(q4.steps(), 781); |
---|
1560 | |
---|
1561 | TEST_EXPECT_EQUAL(concat_iteration(q0), ""); |
---|
1562 | TEST_EXPECT_EQUAL(concat_iteration(q1), ".,N,A,C,G,U"); |
---|
1563 | TEST_EXPECT_EQUAL(concat_iteration(q2), |
---|
1564 | ".," |
---|
1565 | "N.,NN,NA,NC,NG,NU," |
---|
1566 | "A.,AN,AA,AC,AG,AU," |
---|
1567 | "C.,CN,CA,CC,CG,CU," |
---|
1568 | "G.,GN,GA,GC,GG,GU," |
---|
1569 | "U.,UN,UA,UC,UG,UU"); |
---|
1570 | TEST_EXPECT_EQUAL(concat_iteration(q3), |
---|
1571 | ".," |
---|
1572 | "N.," |
---|
1573 | "NN.,NNN,NNA,NNC,NNG,NNU," |
---|
1574 | "NA.,NAN,NAA,NAC,NAG,NAU," |
---|
1575 | "NC.,NCN,NCA,NCC,NCG,NCU," |
---|
1576 | "NG.,NGN,NGA,NGC,NGG,NGU," |
---|
1577 | "NU.,NUN,NUA,NUC,NUG,NUU," |
---|
1578 | "A.," |
---|
1579 | "AN.,ANN,ANA,ANC,ANG,ANU," |
---|
1580 | "AA.,AAN,AAA,AAC,AAG,AAU," |
---|
1581 | "AC.,ACN,ACA,ACC,ACG,ACU," |
---|
1582 | "AG.,AGN,AGA,AGC,AGG,AGU," |
---|
1583 | "AU.,AUN,AUA,AUC,AUG,AUU," |
---|
1584 | "C.," |
---|
1585 | "CN.,CNN,CNA,CNC,CNG,CNU," |
---|
1586 | "CA.,CAN,CAA,CAC,CAG,CAU," |
---|
1587 | "CC.,CCN,CCA,CCC,CCG,CCU," |
---|
1588 | "CG.,CGN,CGA,CGC,CGG,CGU," |
---|
1589 | "CU.,CUN,CUA,CUC,CUG,CUU," |
---|
1590 | "G.," |
---|
1591 | "GN.,GNN,GNA,GNC,GNG,GNU," |
---|
1592 | "GA.,GAN,GAA,GAC,GAG,GAU," |
---|
1593 | "GC.,GCN,GCA,GCC,GCG,GCU," |
---|
1594 | "GG.,GGN,GGA,GGC,GGG,GGU," |
---|
1595 | "GU.,GUN,GUA,GUC,GUG,GUU," |
---|
1596 | "U.," |
---|
1597 | "UN.,UNN,UNA,UNC,UNG,UNU," |
---|
1598 | "UA.,UAN,UAA,UAC,UAG,UAU," |
---|
1599 | "UC.,UCN,UCA,UCC,UCG,UCU," |
---|
1600 | "UG.,UGN,UGA,UGC,UGG,UGU," |
---|
1601 | "UU.,UUN,UUA,UUC,UUG,UUU"); |
---|
1602 | } |
---|
1603 | |
---|
1604 | #endif // UNIT_TESTS |
---|
1605 | |
---|
1606 | // -------------------------------------------------------------------------------- |
---|