Debian Codegraph @

Csequence_cluster_and_center_sequence.cpp

raw
1 /* BaitFisher (version 1.2.8) 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 #include "Csequence_cluster_and_center_sequence.h"
28 #include "DEBUG_STUFF.h"
29
30 using namespace std;
31
32 CDistance_Cluster *p_global_distcluster;
33 bool global_bad_dist_this_range;
34
35
36 void call_back_distance(short i1, short i2, double dist)
37 {
38 if (dist < 0)
39 global_bad_dist_this_range = true;
40 else
41 p_global_distcluster->add(i1, i2, dist);
42 }
43
44
45
46 void Csequence_loci_cluster_collection::cluster_locus(faststring & region_name, const faststring &filename)
47 {
48 // TODO:
49 // We have to check how many (valid) sequences we have.
50 // If this number is just 0 or 1, the clustering will fail and we need a workaround.
51
52 // The number of valid sequences has been determined in the constructor of this object.
53 if (number_of_valid_sequences < 2)
54 {
55 if (number_of_valid_sequences == 0)
56 {
57 if (global_VERBOSITY >= VERBOSITY_MOREWARNINGS)
58 {
59 cout << "WARNING: Found 0 valid sequences in bait window in Csequence_loci_cluster_collection::cluster_locus()." << endl;
60 cout << " Alignment file: " << filename << endl;
61 cout << " Region/gene name: " << region_name << endl;
62 cout << " Within gene coordinates: " << pos_start+1 << "-" << pos_end << endl;
63 }
64 }
65 if (number_of_valid_sequences == 1)
66 {
67 // TODO: Report this only if
68 if (global_VERBOSITY >= VERBOSITY_MOREWARNINGS)
69 {
70 cout << "Note: Found 1 valid sequence in bait window in Csequence_loci_cluster_collection::cluster_locus(). Clustering will be skipped. Bait will be constructed from single sequence." << endl;
71 cout << " Alignment file: " << filename << endl;
72 cout << " Region/gene name: " << region_name << endl;
73 cout << " Within gene coordinates: " << pos_start+1 << "-" << pos_end << endl;
74 }
75
76 // TODO: Uncomment and adapt:
77 Csequence_cluster_and_center_sequence empty_cluster_and_center_sequence;
78
79 // Add an empty object
80 list_of_clusters.push_back(empty_cluster_and_center_sequence);
81
82 if (global_VERBOSITY > 2000)
83 {
84 cout << "Object that will be assigned: *******" << endl;
85 list_of_clusters.back().print(cout);
86 cout << "*************************************" << endl;
87 }
88 // Fill the object
89 set<short> seq_set;
90 unsigned i, N = valid_sequences.size();
91 for (i=0; i < N; ++i)
92 {
93 if (valid_sequences[i])
94 seq_set.insert(i);
95 }
96 list_of_clusters.back().assign(pos_start, pos_end, 0, seq_set, this, msa);
97 if (global_VERBOSITY > 2000)
98 {
99 cout << "Object after having been assigned:***" << endl;
100 list_of_clusters.back().print(cout);
101 cout << "*************************************" << endl;
102 }
103 } // END if (number_of_valid_sequences == 1)
104 // Prints data for all clusters in this locus. Center sequences are not computed yet.
105 if (global_VERBOSITY > 2000)
106 {
107 print(cout);
108 }
109 return;
110 } // END if (number_of_valid_sequences < 2)
111
112 // Create cluster object:
113 CDistance_Cluster cluster_object;
114
115 // We initialise the global pointer to the cluster_object.
116 // This pointer is used by the global call_back_distance function,
117 // which we pass to the CSequences2 class where it is used to
118 // fill the cluster_object with the distances of the sequences.
119 p_global_distcluster = &cluster_object;
120
121 // One problem exists with the sequences that contain gaps or Ns in the window we investigate.
122 // The clustering algorithm assumes that all sequence numbers are present during clustering,
123 // so we cannot skip sequences. So. we have to add distances for all sequences in the sequences objects.
124 // We also do not want to copy the sequences to a new CSequences2 object. Then we have to keep track
125 // of the new sequence number, and we have global unique numbers, sequence numbers in the exon,
126 // sequence numbers in the window.
127 // The best compromise is to add very large distances to the clustering algorithm and to remove
128 // the "non-present" sequences after the clustering has been done.
129 // Due to the large distances we assign to all sequence pairs in which one sequence is not valid, non of
130 // the invalid sequences will be clustered with any other sequence.
131
132 // Valid distances among sequences are in the range 0..1.
133 // With a larger value we indicate a problem, e.g. Ns or gaps in the sequences.
134 // In order not to cluster sequences that contain Ns or gaps, we
135 // set the dist_threshold to a maximum value of 10.
136 // Distances with a value >10 will not be clustered.
137 // A good value for distances of sequences that contain gaps or Ns is 100.
138
139 // Add distances:
140 seqs->get_sequences_distances(pos_start, pos_end,
141 call_back_distance,
142 valid_sequences, 0);
143
144 if (global_VERBOSITY > 3000)
145 {
146 cout << "Sorted distances in this cluster object" << endl;
147 cluster_object.print_sorted(cout);
148 cout << endl;
149 }
150
151 if (global_VERBOSITY >= 900)
152 {
153 // Print filename, region name, within gene/alignment coordinate, maximum sequence distance
154 // for this starting position/locus.
155 cout << "Maximum distance:\t" << filename << "\t" << region_name << "\t" << pos_start+1 << "\t"
156 << cluster_object.max_distance() << endl;
157 }
158
159 // Do clustering:
160 cluster_object.run_clustering(dist_threshold);
161
162 if (global_VERBOSITY > 900)
163 {
164 faststring cluster_string;
165 cluster_object.get_cluster_string2(cluster_string);
166 cout << "Clustering string: " << cluster_string << endl;
167 }
168
169 // Retrieve results: Store all valid clusters in the list of clusters "list_of_clusters" of this locus.
170 set<short> seq_set;
171 // set<short> seq_set_uniq_numbers;
172 set<short>::iterator it_set, it_set_end;
173 double max_dist_in_clu;
174 short i;
175 bool valid_cluster;
176
177 Csequence_cluster_and_center_sequence empty_cluster_and_center_sequence;
178
179 i=0;
180 // For all clusters at this locus:
181 while ( cluster_object.get_cluster_by_index(i, seq_set, max_dist_in_clu) )
182 {
183 valid_cluster = true;
184 // Determine whether this is a good set of sequences in this range.
185 // Bad sequences should never cluster with others with our settings. (distance=100)
186 // So bad sequences should be clusters with just one sequence.
187 if (seq_set.size() == 1)
188 {
189 it_set = seq_set.begin();
190 unsigned seq_index = *it_set;
191
192 valid_cluster = valid_sequences[seq_index];
193 }
194 // else - the cluster must be valid in our setup since clusters with more than 1 element cannot contain bad sequences.
195
196
197 // Do something with the cluster:
198 // Debug code - more important it shows how to extract
199 // the resulting clustering data
200 if (global_VERBOSITY > 3000)
201 {
202 it_set = seq_set.begin();
203 it_set_end = seq_set.end();
204
205 cout << "Found cluster: (";
206 while (it_set != it_set_end)
207 {
208 cout << *it_set;
209 ++it_set;
210 if (it_set != it_set_end)
211 cout << ",";
212 }
213 cout << "):" << max_dist_in_clu;
214 if (valid_cluster)
215 cout << endl;
216 else
217 cout << "(invalid)" << endl;
218 }
219
220 // Copy the clustering data to the Csequence_loci_cluster_collection data
221
222 if (valid_cluster)
223 {
224 // Too bad: emplace_back is a C++11 feature
225 // list_of_clusters.emplace_back(pos_start, pos_end, max_dist_in_clu, seq_set, this);
226
227 // Add an empty object
228 list_of_clusters.push_back(empty_cluster_and_center_sequence);
229
230 if (global_VERBOSITY > 2000)
231 {
232 cout << "Object that will be assigned: *******" << endl;
233 list_of_clusters.back().print(cout);
234 cout << "*************************************" << endl;
235 }
236 // Fill the object
237 list_of_clusters.back().assign(pos_start, pos_end, max_dist_in_clu, seq_set, this, msa);
238 if (global_VERBOSITY > 2000)
239 {
240 cout << "Object after having been assigned:***" << endl;
241 list_of_clusters.back().print(cout);
242 cout << "*************************************" << endl;
243 }
244 }
245 ++i;
246
247 } // END while ( cluster_object.get_cluster_by_index(i, seq_set, max_dist_in_clu) )
248
249 // Prints data for all clusters in this locus. Center sequences are not computed yet.
250 if (global_VERBOSITY > 1000)
251 {
252 print(cout);
253 }
254 } // END Csequence_loci_cluster_collection::cluster_locus()
255
256 ///////////////////////////////////////////////////////
257 ///////////////// CLUSTERING //////////////////////////
258 ///////////////////////////////////////////////////////
259
260 // Helper functions:
261
262 // Indices:
263 // First index: Row, i.e. sequence
264 // Second index: Col, i.e. sequence position
265
266 void recode_range(char * b, char *e)
267 {
268 while (b != e)
269 {
270 *b = recode_DNA(*b);
271 ++b;
272 }
273 }
274
275 void back_recode_range(char * b, char *e)
276 {
277 while (b != e)
278 {
279 *b = backrecode_DNA(*b);
280 ++b;
281 }
282 }
283
284 // inline bool is_valid_recode_DNA_range(const char *p1, const char *p2)
285 // {
286 // while (p1 != p2)
287 // {
288 // if (!is_valid_recode_DNA(*p1))
289 // return false;
290 // ++p1;
291 // }
292 // return true;
293 // }
294
295
296 void recode_MSA(char **sequences, int num_taxa, int num_pos)
297 {
298 int row;
299
300 for (row=0; row < num_taxa; ++row)
301 {
302 recode_range(sequences[row], sequences[row]+num_pos);
303 }
304 }
305
306 // Requires recoded sequences as input.
307 // The consensus will also be recoded.
308 ////////////////// UPDATED/////////////////
309 void find_consensus(char **msa, int num_taxa, unsigned pos_start_msa,
310 unsigned pos_end_msa, char *consensus, char *isAmbig)
311 {
312 int row, col, col_in_msa;
313 char c;
314
315 int len = pos_end_msa - pos_start_msa;
316
317 for (col=0, col_in_msa = pos_start_msa; col < len; ++col, ++col_in_msa)
318 {
319 c = msa[0][col_in_msa]; // Take symbol from row=0
320 for (row=1; row < num_taxa; ++row)
321 {
322 c = c | msa[row][col_in_msa]; // Add all symbols of all other rows.
323 }
324 consensus[col] = c;
325 if (recode_is_DNA_ambig(c) )
326 {
327 isAmbig[col] = 1; // Keep track of amibig characters: set isAmbig to true
328 }
329 else
330 {
331 isAmbig[col] = 0; // Keep track of amibig characters: set isAmbig to false
332 }
333 }
334 }
335
336 // ONLY DEBUGGING OUTPUT:
337 // Should work unchanged. CHECK!!!!
338 void print_all_variants(char *consensus, char *variant, char *isAmbig, int pos, int len)
339 {
340 while (pos < len && !isAmbig[pos])
341 ++pos;
342
343 if (pos == len)
344 {
345 faststring p = variant;
346 back_recode_range(p.begin(), p.end());
347 cout << p << endl;
348 }
349 else
350 {
351 if (consensus[pos]&1)
352 {
353 variant[pos] = 1;
354 print_all_variants(consensus, variant, isAmbig, pos+1, len);
355 }
356 if (consensus[pos]&2)
357 {
358 variant[pos] = 2;
359 print_all_variants(consensus, variant, isAmbig, pos+1, len);
360 }
361 if (consensus[pos]&4)
362 {
363 variant[pos] = 4;
364 print_all_variants(consensus, variant, isAmbig, pos+1, len);
365 }
366 if (consensus[pos]&8)
367 {
368 variant[pos] = 8;
369 print_all_variants(consensus, variant, isAmbig, pos+1, len);
370 }
371 }
372 } // END find_consensus(..)
373
374
375
376
377 // Important: msa, consensus, and variant are expected to be passed as recoded msa.
378 //
379 // pos1 ... pos2 is the range to work on. pos2 is the index after the end of the range.
380 //
381 ////////////////// UPDATED/////////////////
382 void find_center_sequence_exhaustive(char **msa, char *consensus,
383 char *variant, char *isAmbig,
384 int len_variant,
385 int pos_start, int num_taxa,
386 int pos_start_msa, int pos_end_msa,
387 int *distances, faststring &best_variant,
388 int *p_best_maximum_distance)
389 {
390 int i;
391 int len_remaining = pos_end_msa - pos_start_msa;
392 int pos_end = pos_start + len_remaining;
393
394 // Skip all bases for which isAmbig == 0
395 while (pos_start < pos_end && !isAmbig[pos_start])
396 {
397 ++pos_start;
398 ++pos_start_msa;
399 }
400
401 if (pos_start == pos_end)
402 {
403 // We have a new variant:
404 // Check wether this is better than the best we found so far.
405
406 // Determine maximum distance:
407 int m_dist = maximum(distances, distances+num_taxa);
408
409 if (global_VERBOSITY > 800)
410 {
411 cout << "Current sequence:\nDistance: " << m_dist << endl;
412 faststring p = variant;
413 back_recode_range(p.begin(), p.end());
414 cout << p << endl;
415
416 print_container(cout, distances, distances+num_taxa, "distances: ", ":", "\n\n");
417 }
418
419 if (m_dist < *p_best_maximum_distance) // We found a better sequence:
420 {
421
422 // Be careful in the following assignment: "=" does not work here, since variant is not 0 terminated!!!
423 best_variant.assign(variant, 0, len_variant);
424 *p_best_maximum_distance = m_dist;
425
426 // Some debug output:
427 if (global_VERBOSITY > 500)
428 {
429 cout << "*** New best variant: ***" << endl;
430 faststring tmp = best_variant;
431 back_recode_range(tmp.begin(), tmp.end() );
432 cout << tmp << endl;
433 cout << "Distance: " << *p_best_maximum_distance << endl << endl;
434 }
435 }
436 }
437 else
438 {
439 int *tmp_dist = new int [num_taxa];
440
441 // If we get here, we have an non unique "consensus at pos_start.
442 // So let us try all variants which are found in the msa.
443 if (consensus[pos_start]&1)
444 {
445 variant[pos_start] = 1;
446
447 // Determine new distances:
448 memcpy(tmp_dist, distances, sizeof(int)*num_taxa);
449 // Adjust distances for this new base:
450 for (i=0; i<num_taxa; ++i)
451 {
452 if (variant[pos_start] != msa[i][pos_start_msa])
453 ++tmp_dist[i];
454 }
455
456 find_center_sequence_exhaustive(msa, consensus, variant, isAmbig, len_variant,
457 pos_start+1, num_taxa, pos_start_msa+1, pos_end_msa,
458 tmp_dist, best_variant, p_best_maximum_distance);
459 }
460 if (consensus[pos_start]&2)
461 {
462 variant[pos_start] = 2;
463
464 // Determine new distances:
465 memcpy(tmp_dist, distances, sizeof(int)*num_taxa);
466 // Adjust distances for this new base:
467 for (i=0; i<num_taxa; ++i)
468 {
469 if (variant[pos_start] != msa[i][pos_start_msa])
470 ++tmp_dist[i];
471 }
472
473 find_center_sequence_exhaustive(msa, consensus, variant, isAmbig, len_variant,
474 pos_start+1, num_taxa, pos_start_msa+1, pos_end_msa,
475 tmp_dist, best_variant, p_best_maximum_distance);
476 }
477 if (consensus[pos_start]&4)
478 {
479 variant[pos_start] = 4;
480
481 // Determine new distances:
482 memcpy(tmp_dist, distances, sizeof(int)*num_taxa);
483 // Adjust distances for this new base:
484 for (i=0; i<num_taxa; ++i)
485 {
486 if (variant[pos_start] != msa[i][pos_start_msa])
487 ++tmp_dist[i];
488 }
489
490 find_center_sequence_exhaustive(msa, consensus, variant, isAmbig, len_variant,
491 pos_start+1, num_taxa, pos_start_msa+1, pos_end_msa,
492 tmp_dist, best_variant, p_best_maximum_distance);
493 }
494 if (consensus[pos_start]&8)
495 {
496 variant[pos_start] = 8;
497
498 // Determine new distances:
499 memcpy(tmp_dist, distances, sizeof(int)*num_taxa);
500 // Adjust distances for this new base:
501 for (i=0; i<num_taxa; ++i)
502 {
503 if (variant[pos_start] != msa[i][pos_start_msa])
504 ++tmp_dist[i];
505 }
506
507 find_center_sequence_exhaustive(msa, consensus, variant, isAmbig, len_variant,
508 pos_start+1, num_taxa, pos_start_msa+1, pos_end_msa,
509 tmp_dist, best_variant, p_best_maximum_distance);
510 }
511 delete [] tmp_dist;
512 } // END else of if (pos1 == pos2)
513 } // END void find_center_sequence_exhaustive
514
515 // distances must be initialised by caller.
516 void find_center_sequence_heuristic(char **msa, char *consensus,
517 char *center, char *isAmbig,
518 unsigned len_center,
519 unsigned pos_start, unsigned num_taxa,
520 unsigned pos_start_msa, unsigned pos_end_msa,
521 unsigned *distances,
522 unsigned *p_best_maximum_distance)
523 {
524 static char recode_A = recode_DNA('A');
525 static char recode_C = recode_DNA('C');
526 static char recode_G = recode_DNA('G');
527 static char recode_T = recode_DNA('T');
528
529 unsigned len_remaining = pos_end_msa - pos_start_msa;
530 unsigned pos_end = pos_start + len_remaining;
531
532 // pos_start walks through isAmbig and consensus.
533 // pos_start_msa walks through the msa.
534
535 // The following static variables are initialised only when calling this function for the first time.
536 static unsigned max_num_taxa = 20;
537 static unsigned *dist_A = new unsigned [max_num_taxa];
538 static unsigned *dist_C = new unsigned [max_num_taxa];
539 static unsigned *dist_G = new unsigned [max_num_taxa];
540 static unsigned *dist_T = new unsigned [max_num_taxa];
541
542 if (num_taxa > max_num_taxa)
543 {
544 max_num_taxa = num_taxa; // max_num_taxa takes on the new maximum value. It will be used as size when reallocating new arrays.
545
546 if (dist_A != NULL)
547 {
548 delete [] dist_A;
549 delete [] dist_C;
550 delete [] dist_G;
551 delete [] dist_T;
552
553 dist_A = new unsigned [max_num_taxa];
554 dist_C = new unsigned [max_num_taxa];
555 dist_G = new unsigned [max_num_taxa];
556 dist_T = new unsigned [max_num_taxa];
557 }
558 }
559
560 unsigned distances_sum_squares;
561 unsigned dist_A_sum_squares;
562 unsigned dist_C_sum_squares;
563 unsigned dist_G_sum_squares;
564 unsigned dist_T_sum_squares;
565
566 // unsigned dist_max_A;
567 // unsigned dist_max_C;
568 // unsigned dist_max_G;
569 // unsigned dist_max_T;
570 // unsigned dist_max;
571
572 unsigned j;
573
574 // Search for first non-invariant site:
575 while (pos_start < pos_end && !isAmbig[pos_start])
576 {
577 ++pos_start;
578 ++pos_start_msa;
579 }
580
581 if (pos_start == pos_end) // This is the case if all sites are invariant.
582 {
583 return;
584 }
585
586 // pos_start is first non-invariant site:
587 {
588 unsigned A=0, C=0, G=0, T=0;
589 char c;
590
591 for (j=0; j<num_taxa; ++j)
592 {
593 if (msa[j][pos_start_msa] == recode_A )
594 ++A;
595 else if (msa[j][pos_start_msa] == recode_C )
596 ++C;
597 else if (msa[j][pos_start_msa] == recode_G )
598 ++G;
599 else if (msa[j][pos_start_msa] == recode_T )
600 ++T;
601 }
602
603 if (A > C)
604 {
605 if (G > T)
606 {
607 if (A > G)
608 c = recode_A;
609 else
610 c = recode_G;
611 }
612 else // (G <= T)
613 {
614 if (A > T)
615 c = recode_A;
616 else
617 c = recode_T;
618 }
619 }
620 else // (A <= C)
621 {
622 if (G > T)
623 {
624 if (C > G)
625 c = recode_C;
626 else
627 c = recode_G;
628 }
629 else // (G <= T)
630 {
631 if (C > T)
632 c = recode_C;
633 else
634 c = recode_T;
635 }
636 }
637 center[pos_start] = c; // First position has been determined.
638 distances_sum_squares = 0;
639 // dist_max = 0;
640
641 for (j=0; j<num_taxa; ++j)
642 {
643 if (center[pos_start] != msa[j][pos_start_msa])
644 ++distances[j];
645 distances_sum_squares += distances[j]*distances[j];
646 // if (dist_max < distances[j])
647 // dist_max = distances[j];
648 }
649 } // pos_start is first non-invariant site:
650
651 ++pos_start;
652 ++pos_start_msa;
653
654 while (pos_start < pos_end)
655 {
656 if (isAmbig[pos_start]) // He now search for best nucleotide in center.
657 {
658 // Try 'A'
659 if (consensus[pos_start]&recode_A)
660 {
661 memcpy(dist_A, distances, sizeof(unsigned)*num_taxa);
662 center[pos_start] = recode_A;
663 dist_A_sum_squares = 0;
664 for (j=0; j<num_taxa; ++j)
665 {
666 if (center[pos_start] != msa[j][pos_start_msa])
667 ++dist_A[j];
668 dist_A_sum_squares += dist_A[j]*dist_A[j];
669 }
670 }
671 else
672 dist_A_sum_squares = -1u;
673 // END // Try 'A'
674 // Try 'C'
675 if (consensus[pos_start]&recode_C)
676 {
677 memcpy(dist_C, distances, sizeof(unsigned)*num_taxa);
678 center[pos_start] = recode_C;
679 dist_C_sum_squares = 0;
680 for (j=0; j<num_taxa; ++j)
681 {
682 if (center[pos_start] != msa[j][pos_start_msa])
683 ++dist_C[j];
684 dist_C_sum_squares += dist_C[j]*dist_C[j];
685 }
686 }
687 else
688 dist_C_sum_squares = -1u;
689 // END // Try 'C'
690 // Try 'G'
691 if (consensus[pos_start]&recode_G)
692 {
693 memcpy(dist_G, distances, sizeof(unsigned)*num_taxa);
694 center[pos_start] = recode_G;
695 dist_G_sum_squares = 0;
696 for (j=0; j<num_taxa; ++j)
697 {
698 if (center[pos_start] != msa[j][pos_start_msa])
699 ++dist_G[j];
700 dist_G_sum_squares += dist_G[j]*dist_G[j];
701 }
702 }
703 else
704 dist_G_sum_squares = -1u;
705 // END // Try 'G'
706 // Try 'T'
707 if (consensus[pos_start]&recode_T)
708 {
709 memcpy(dist_T, distances, sizeof(unsigned)*num_taxa);
710 center[pos_start] = recode_T;
711 dist_T_sum_squares = 0;
712 for (j=0; j<num_taxa; ++j)
713 {
714 if (center[pos_start] != msa[j][pos_start_msa])
715 ++dist_T[j];
716 dist_T_sum_squares += dist_T[j]*dist_T[j];
717 }
718 }
719 else
720 dist_T_sum_squares = -1u;
721 // END // Try 'T'
722
723 // Which "Try" is the best?
724 {
725 // Smallest dist_x_sum_squares is the best:
726 if (dist_A_sum_squares < dist_C_sum_squares) // A is better than C
727 {
728 if (dist_G_sum_squares < dist_T_sum_squares) // G is better than T
729 {
730 if (dist_A_sum_squares < dist_G_sum_squares) // A is better than G
731 {
732 // A is the best:
733 center[pos_start] = recode_A;
734 memcpy(distances, dist_A, sizeof(unsigned)*num_taxa);
735 }
736 else
737 {
738 // G is the best:
739 center[pos_start] = recode_G;
740 memcpy(distances, dist_G, sizeof(unsigned)*num_taxa);
741 }
742 }
743 else // T is better than or equal to G
744 {
745 if (dist_A_sum_squares < dist_T_sum_squares) // A is better than T
746 {
747 // A is the best
748 center[pos_start] = recode_A;
749 memcpy(distances, dist_A, sizeof(unsigned)*num_taxa);
750 }
751 else
752 {
753 // T is the best
754 center[pos_start] = recode_T;
755 memcpy(distances, dist_T, sizeof(unsigned)*num_taxa);
756 }
757 }
758 }
759 else // C is better than or equal to A
760 {
761 if (dist_G_sum_squares < dist_T_sum_squares) // G is better than T
762 {
763 if (dist_C_sum_squares < dist_G_sum_squares) // C is better than G
764 {
765 // C is the best:
766 center[pos_start] = recode_C;
767 memcpy(distances, dist_C, sizeof(unsigned)*num_taxa);
768 }
769 else
770 {
771 // G is the best:
772 center[pos_start] = recode_G;
773 memcpy(distances, dist_G, sizeof(unsigned)*num_taxa);
774 }
775 }
776 else // T is better than or equal to G
777 {
778 if (dist_C_sum_squares < dist_T_sum_squares) // C is better than T
779 {
780 // C is the best
781 center[pos_start] = recode_C;
782 memcpy(distances, dist_C, sizeof(unsigned)*num_taxa);
783 }
784 else
785 {
786 // T is the best
787 center[pos_start] = recode_T;
788 memcpy(distances, dist_T, sizeof(unsigned)*num_taxa);
789 }
790 }
791 } // END C is better than or equal to A
792 } // END Which "Try" is the best?
793 } // END ELSE (!isAmbig[pos_start])
794 ++pos_start;
795 ++pos_start_msa;
796 } // END while (pos_start < pos_end)
797 // We have the greedy center sequence.
798 *p_best_maximum_distance = maximum(distances, distances+num_taxa);
799 } // END find_center_sequence_heuristic
800
801
802
803
804 // TODO ///////////////////
805
806 // Requires:
807 // Multiple sequence alignment that is already recoded.
808 // References to (empty) faststrings for the center.
809 // Number of taxa
810 // Start and end indices of range for which the center sequence shall be computed.
811 // The center sequence is returned in recoded form.
812 void find_center_sequence_for_msa_exhaustive(char **msa, faststring &center_seq,
813 int num_taxa,
814 int pos_start_msa, int pos_end_msa,
815 double &mdist)
816 {
817 faststring cons;
818 faststring isAmbig;
819 faststring variant;
820 faststring best_variant;
821 int best_maximum_distance = INT_MAX;
822 // The equality len_variant = pos_end - pos_start is only valid before ever incrementing
823 // pos_start, which is always true in this function.
824 int len_variant = pos_end_msa - pos_start_msa;
825 int pos_start = 0;
826 // int pos_end = len_variant;
827
828
829 cons.assign(len_variant, ' ');
830 isAmbig.assign(len_variant, ' ');
831
832 // Here we can pass .data() since we do not assign it
833 find_consensus(msa, num_taxa, pos_start_msa, pos_end_msa, cons.begin(), isAmbig.begin() );
834 variant = cons;
835
836 int *dist_array = new int [num_taxa];
837 memset(dist_array, 0, num_taxa*sizeof(int));
838 // for (i=0; i< num_taxa; ++i)
839 // {
840 // dist_array[i] = 0;
841 // }
842
843 // print_all_variants(cons.data(), variant.data(), isAmbig.data(), 0, len);
844
845 // if (global_VERBOSITY > 5)
846 // {
847 // cout << "Start time: " << time(NULL) << endl;
848 // }
849
850 find_center_sequence_exhaustive(msa, cons.data(), variant.data(), isAmbig.data(),
851 len_variant,
852 pos_start, num_taxa,
853 pos_start_msa, pos_end_msa,
854 dist_array, best_variant,
855 &best_maximum_distance);
856
857 // if (global_VERBOSITY > 5)
858 // {
859 // cout << "End time: " << time(NULL) << endl;
860 // }
861
862 center_seq = best_variant;
863 // TODO remove if is clear this cannot happen
864 if (len_variant == 0)
865 {
866 cerr << "ERROR: len_variant == 0 in find_center_sequence_for_msa_exhaustive. Please report this bug." << endl;
867 exit(-54);
868 }
869 mdist = (double)best_maximum_distance/len_variant;
870
871 delete [] dist_array;
872 //
873 // back_recode_range(center_seq.begin(), center_seq.end() );
874 } // END find_center_sequence_for_msa_exhaustive
875
876 // Requires:
877 // Multiple sequence alignment that is already recoded.
878 // References to (empty) faststrings for the center.
879 // Number of taxa
880 // Start and end indices of range for which the center sequence shall be computed.
881 // The center sequence is returned in recoded form.
882 void find_center_sequence_for_msa_heuristic(char **msa, faststring &center_seq,
883 int num_taxa,
884 int pos_start_msa, int pos_end_msa,
885 double &mdist)
886 {
887 faststring cons;
888 faststring isAmbig;
889 faststring variant;
890 unsigned best_maximum_distance = 0;
891 // The equality len_variant = pos_end - pos_start is only valid before ever incrementing
892 // pos_start, which is always true in this function.
893 unsigned len_variant = pos_end_msa - pos_start_msa;
894 unsigned pos_start = 0;
895 // unsigned pos_end = len_variant;
896
897
898 cons.assign(len_variant, ' ');
899 isAmbig.assign(len_variant, ' ');
900
901 // Here we can pass .data() since we do not assign it
902 find_consensus(msa, num_taxa, pos_start_msa, pos_end_msa, cons.begin(), isAmbig.begin() );
903 variant = cons;
904
905 unsigned *dist_array = new unsigned [num_taxa];
906 memset(dist_array, 0, num_taxa*sizeof(int));
907 // for (i=0; i< num_taxa; ++i)
908 // {
909 // dist_array[i] = 0;
910 // }
911
912 // print_all_variants(cons.data(), variant.data(), isAmbig.data(), 0, len);
913
914 // if (global_VERBOSITY > 5)
915 // {
916 // cout << "Start time: " << time(NULL) << endl;
917 // }
918
919 find_center_sequence_heuristic(msa, cons.data(), variant.data(), isAmbig.data(),
920 len_variant,
921 pos_start, num_taxa,
922 pos_start_msa, pos_end_msa,
923 dist_array, &best_maximum_distance);
924
925 // if (global_VERBOSITY > 5)
926 // {
927 // cout << "End time: " << time(NULL) << endl;
928 // }
929
930 // for (i=0; i< num_taxa; ++i)
931 // {
932 // if (dist_array[i] > best_maximum_distance)
933 // best_maximum_distance = dist_array[i];
934 // }
935 // best_maximum_distance = maximum(distances, distances+num_taxa);
936
937 center_seq = variant;
938
939 // TODO remove is clear this cannot happen
940 if (len_variant == 0)
941 {
942 cerr << "ERROR: len_variant == 0 in find_center_sequence_for_msa_heuristic. Please report this bug." << endl;
943 exit(-55);
944 }
945
946 mdist = (double)best_maximum_distance/len_variant;
947
948 if (global_VERBOSITY > 100)
949 {
950 cout << "Reporting mdist for a center sequence with starting position: " << pos_start << " " << mdist << endl;
951 }
952 //
953 // back_recode_range(center_seq.begin(), center_seq.end() );
954 delete [] dist_array;
955 } // END find_center_sequence_for_msa_heuristic
956
957
958 void Csequence_cluster_and_center_sequence::compute_center(char center_computation_mode)
959 {
960 // The msa is prepared for the center algorithm:
961 // We still need: the "consensus" and the "ambig" strings.
962
963 int num_sequences = taxon_set.size();
964
965 // if (global_VERBOSITY > 5)
966 // {
967 // cout << "Computing center sequence: " << endl << flush;
968 // }
969
970 if (num_sequences == 1)
971 {
972 center_sequence.assign(msa[0]+pos_start, msa[0]+pos_end);
973 max_dist_bait_to_msa = 0;
974 }
975 else // We have to compute a center sequence:
976 {
977 if (center_computation_mode == 0) // exhaustive
978 {
979 find_center_sequence_for_msa_exhaustive(msa, center_sequence, num_sequences, pos_start, pos_end, max_dist_bait_to_msa);
980 }
981 else if (center_computation_mode == 1) // heuristic
982 {
983 find_center_sequence_for_msa_heuristic(msa, center_sequence, num_sequences, pos_start, pos_end, max_dist_bait_to_msa);
984 }
985 else // Comparison mode
986 {
987 std::set<short>::iterator it;
988 it = taxon_set.begin();
989
990 {
991 unsigned i;
992 cout << "The MSA for the result below:" << endl;
993 cout << "Time: " << time(NULL) << endl;
994
995 for (i=0; i<taxon_set.size(); ++i, ++it)
996 {
997 faststring tmp( msa[i]+pos_start, msa[i]+pos_end);
998 back_recode_range(tmp.begin(), tmp.end());
999 cout.width(4);
1000 cout << *it << ":" << tmp << std::endl;
1001 }
1002 }
1003
1004 unsigned t1, t2, t3;
1005 faststring c1, c2;
1006 double md1, md2;
1007 t1 = time(NULL);
1008 find_center_sequence_for_msa_exhaustive(msa, c1, num_sequences, pos_start, pos_end, md1);
1009 t2 = time(NULL);
1010 find_center_sequence_for_msa_heuristic(msa, c2, num_sequences, pos_start, pos_end, md2);
1011 t3 = time(NULL);
1012
1013 // This assignment must come before back recoding c1.
1014 // Otherwise we back recode twice, which is not correct.
1015 center_sequence = c1;
1016
1017 back_recode_range(c1.begin(), c1.end());
1018 back_recode_range(c2.begin(), c2.end());
1019
1020 cout << "Cent1: " << c1 << endl;
1021 cout << "max_dist1: " << md1 << endl;
1022 cout << "Tdiff1: " << t2-t1 << endl;
1023
1024 cout << "Cent2: " << c2 << endl;
1025 cout << "max_dist2: " << md2 << endl;
1026 cout << "Tdiff2: " << t3-t2 << endl;
1027
1028
1029 max_dist_bait_to_msa = md1;
1030
1031 if (md1 != md2)
1032 {
1033 cout << "Deviating distances found: " << md2-md1 << " " << (md2-md1)*120 << endl;
1034 }
1035 else
1036 {
1037 cout << "Same distance." << endl;
1038 }
1039 } // END else // Comparison mode
1040 } // END else // We have to compute a center sequence:
1041
1042 // cout << "LOG: pos: " << pos_start << " mis " << max_dist_bait_to_msa*120 << endl;
1043
1044 // We have to back recode the center sequence:
1045 back_recode_range(center_sequence.begin(), center_sequence.end() );
1046
1047 if (!center_sequence.empty())
1048 {
1049 unsigned CG, AT;
1050
1051 CG_AT_content_in_region(center_sequence.begin_str(), center_sequence.end_str(), AT, CG);
1052 double dCG=CG, dAT=AT;
1053 CG_content = (dCG / (dCG+dAT));
1054 }
1055 }
1056
1057
1058 void Csequence_loci_cluster_collection::compute_center_for_all_clusters(char center_computation_mode)
1059 {
1060 std::list<Csequence_cluster_and_center_sequence>::iterator it_list = list_of_clusters.begin();
1061 std::list<Csequence_cluster_and_center_sequence>::iterator it_list_end = list_of_clusters.end();
1062
1063 // unsigned t1, t2;
1064
1065 while (it_list != it_list_end)
1066 {
1067 // t1 = time(NULL);
1068 // cout << "T1: " << t1 << endl;
1069 it_list->compute_center(center_computation_mode);
1070 // t2 = time(NULL);
1071 // cout << "T2: " << t2 << endl;
1072 // cout << "Tdiff: " << t2-t1 << endl;
1073
1074
1075 if (!it_list->center_computed() )
1076 {
1077 cerr << "ERROR: Internal error: Center sequence not computed even though it was requested! Number of sequences in cluster: " << it_list->get_number_of_elements_in_cluster() << endl;
1078 }
1079
1080 ++it_list;
1081 }
1082
1083 }