Debian Codegraph @

Csequence_cluster_and_center_sequence.h

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 #ifndef CSEQUENCE_CLUSTER_AND_CENTER_SEQUENCE
28 #define CSEQUENCE_CLUSTER_AND_CENTER_SEQUENCE
29
30 #include "DEBUG_STUFF.h"
31 #include <set>
32 #include <list>
33 //#include "CTaxonNamesDictionary.h" // Has been used in earlier version, in which clusters where reported with unique sequence number. This intermediate step was not convenient for the user and is not used any more.
34 #include <iostream>
35 #include <fstream>
36 #include "faststring2.h"
37 #include "basic-DNA-RNA-AA-routines.h"
38 #include <climits>
39 #include "statistic_functions.h"
40 #include "print_container.h"
41 //#include "csv-toolbox.h"
42 //#include "mydir.h"
43 //#include "sequence-cluster-result-parser.h"
44 #include "CSequences2.h"
45 #include "CSequence_Mol2_1.h"
46 #include "CDistance_matrix.h"
47 #include "CSeqNameList.h"
48 #include <vector>
49 #include <ctime>
50
51
52 // Prototypes of global functions implemented in csequence_cluster_and_center_sequence.cpp
53 void recode_range(char * b, char *e);
54 void back_recode_range(char * b, char *e);
55 void recode_MSA(char **sequences, int num_taxa, int num_pos);
56 void find_center_sequence(char **msa, char *consensus,
57 char *variant, char *isAmbig,
58 int len_variant,
59 int pos_start, int num_taxa,
60 int pos_start_msa, int pos_end_msa,
61 int *distances, faststring &best_variant,
62 int *p_best_maximum_distance);
63 void find_center_sequence_for_msa_exhaustive(char **msa, faststring &center_seq,
64 int num_taxa,
65 int pos_start_msa, int pos_end_msa,
66 double &mdist);
67
68 void find_center_sequence_for_msa_heuristic(char **msa, faststring &center_seq,
69 int num_taxa,
70 int pos_start_msa, int pos_end_msa,
71 double &mdist);
72
73
74 class Csequence_loci_cluster_collection;
75
76 class Csequence_cluster_and_center_sequence
77 {
78 unsigned pos_start; // 0 based
79 unsigned pos_end; // 0 based, after last element of range
80
81 double max_dist_in_cluster; // Maximum distance within this cluster
82 double max_dist_bait_to_msa;
83 // This is not the threshold but the true maximum distance.
84
85 std::set<short> taxon_set; // This is the set of sequence numbers in the cluster.
86 // Sequence numbers are the numbers that can be used to access the sequences in the CSequences2 object
87 // The sequences can be accessed from this class by following the *loci variable.
88 faststring center_sequence;
89 char **msa; // MSA of this cluster. In the assign function, the filter the sequences that belong to the cluster.
90
91 Csequence_loci_cluster_collection *loci; // Via the loci we have access to the CSequnces2 object and the CTaxonNamesDictionary object.
92 double CG_content;
93
94
95 public:
96 Csequence_cluster_and_center_sequence():pos_start(-1u-1), pos_end(-1u), max_dist_in_cluster(-1), msa(NULL), loci(NULL), CG_content(0)
97 {}
98
99 // Constructor: Never used, never tested.
100 /* Csequence_cluster_and_center_sequence(unsigned P_pos_start, */
101 /* unsigned P_pos_end, */
102 /* double P_max_dist_in_cluster, */
103 /* std::set<short> P_taxon_set, */
104 /* Csequence_loci_cluster_collection *P_loci): */
105 /* pos_start(P_pos_start), pos_end(P_pos_end), max_dist_in_cluster(P_max_dist_in_cluster), max_dist_bait_to_msa(-1), */
106 /* taxon_set(P_taxon_set), msa(NULL), loci(P_loci), CG_content(0) */
107 /* {} */
108
109 ~Csequence_cluster_and_center_sequence()
110 {
111 if (msa)
112 delete [] msa;
113 else
114 {
115 // We can get here if we destroy a default constructed object
116 // that has not been assigned any data. That can happen.
117 }
118 }
119
120 // The only function that is allowed to assign data to objects of this class.
121 // The msa that is passed to this member function is not the msa that is being stored
122 // in the object, since not all sequences belong to the cluster we deal with.
123 void assign(unsigned P_pos_start,
124 unsigned P_pos_end,
125 double P_max_dist_in_cluster,
126 std::set<short> &P_taxon_set, // Contains the indices of the sequences in P_msa that are copied to the msa array.
127 Csequence_loci_cluster_collection *P_loci,
128 char **P_msa)
129 {
130 pos_start = P_pos_start;
131 pos_end = P_pos_end;
132 max_dist_in_cluster = P_max_dist_in_cluster;
133 // We could swap the content of the two sets. This might be faster.
134 taxon_set = P_taxon_set;
135 loci = P_loci;
136
137 std::set<short>::iterator it, it_end;
138
139 it = taxon_set.begin();
140 it_end = taxon_set.end();
141 short i;
142
143 if (msa)
144 {
145 std::cerr << "WARNING: An existing msa is overwritten. This behaviour is not expected. " << std::endl;
146 delete msa;
147 }
148
149 msa = new char * [taxon_set.size()];
150
151 i=0;
152 while (it != it_end)
153 {
154 msa[i] = P_msa[*it];
155 ++i;
156 ++it;
157 }
158 }
159
160
161 unsigned get_number_of_elements_in_cluster()
162 {
163 return taxon_set.size();
164 }
165
166 bool center_computed()
167 {
168 return !center_sequence.empty();
169 }
170
171 const faststring& get_center_sequence()
172 {
173 return center_sequence;
174 }
175
176 double get_CG()
177 {
178 return CG_content;
179 }
180
181 double get_max_dist_in_cluster()
182 {
183 return max_dist_in_cluster;
184 }
185
186 double get_max_dist_bait_to_msa()
187 {
188 return max_dist_bait_to_msa;
189 }
190
191 unsigned window_size()
192 {
193 return pos_end - pos_start;
194 }
195
196 // Implemented in Csequence_cluster_and_center_sequence.cpp
197 void compute_center(char);
198
199 void print(std::ostream &os)
200 {
201 os << "Cluster: " << pos_start+1 << " " << pos_end << " "
202 << max_dist_in_cluster << " ";
203 print_container(os, taxon_set, "{", ",", "}\n");
204
205 if (msa != NULL)
206 {
207 print_msa_backrecoded(os);
208 }
209
210 if (center_sequence.empty())
211 {
212 os << " ## Center sequenuence has not been computed yet." << std::endl;
213 }
214 else
215 {
216 os << center_sequence << std::endl;
217 }
218 }
219
220 void print_msa_backrecoded(std::ostream &os, int flag = 0)
221 {
222 std::set<short>::iterator it;
223
224 it = taxon_set.begin();
225
226 unsigned i;
227 os << "Cluster MSA: " << pos_start+1 << " " << pos_end << std::endl;
228 for (i=0; i<taxon_set.size(); ++i, ++it)
229 {
230 faststring tmp( msa[i]+pos_start, msa[i]+pos_end);
231 back_recode_range(tmp.begin(), tmp.end());
232 os.width(4);
233 os << *it << " " << tmp << std::endl;
234 }
235 if (flag == 1)
236 {
237 if (center_computed() )
238 {
239 os << "Cent " << center_sequence << std::endl;
240 os << "Max dist: " << max_dist_bait_to_msa << std::endl;
241 }
242 else
243 os << "Center sequence not computed." << std::endl;
244 }
245 }
246
247 };
248
249
250 // Stores and handles all clusters for a specific bait window:
251
252 class Csequence_loci_cluster_collection
253 {
254 CSequences2 *seqs;
255 unsigned pos_start; // 0 based
256 unsigned pos_end; // 0 based, after last element of range
257 double dist_threshold; //
258 // CTaxonNamesDictionary &taxon_names_dict;
259 std::vector<bool> valid_sequences; // Does the sequence with given index have Ns or gaps in this range?
260 // Indices are the indices in the CSequences2 object.
261
262 char** msa; // Pointer to a recoded copy of the data
263 // pos_start and pos_end are the coordinates
264 // in these sequences.
265
266 std::list<Csequence_cluster_and_center_sequence> list_of_clusters;
267 unsigned number_of_valid_sequences;
268
269
270
271 public:
272 CSequences2 *get_pointer_to_sequences()
273 {
274 return seqs;
275 }
276
277 // CTaxonNamesDictionary& get_taxonNamesDictionary()
278 // {
279 // return taxon_names_dict;
280 // }
281
282 // Constructor:
283 Csequence_loci_cluster_collection(unsigned P_pos_start, unsigned P_pos_end, CSequences2 *P_seqs,
284 // CTaxonNamesDictionary &P_taxon_names_dict,
285 double P_dist_threshold,
286 char** P_msa):
287 seqs(P_seqs), pos_start(P_pos_start), pos_end(P_pos_end), dist_threshold(P_dist_threshold),
288 //taxon_names_dict(P_taxon_names_dict),
289 valid_sequences(P_seqs->GetTaxaNum()), msa(P_msa)
290 {
291 // std::cerr << "Call to constructor: Csequence_loci_cluster_collection "
292 // << pos_start+1 << " " << pos_end << " " << dist_threshold << std::endl;
293
294 unsigned i, N=seqs->GetTaxaNum();
295 CSequence_Mol* seq;
296
297 number_of_valid_sequences = 0;
298
299 // IMPORTANT: If this code should be uncommented, code further down needs to be uncommented as well.
300 /* if (global_VERBOSITY > 200) */
301 /* { */
302 /* std::cerr << "#1 " << "Constructor: Csequence_loci_cluster_collection, range: " << pos_start+1 << " " << pos_end << std::endl; */
303 /* std::cerr << "#1 " << "Valid: "; */
304 /* } */
305
306 for (i=0; i<N; ++i)
307 {
308 seq = seqs->get_seq_by_index(i);
309
310 // Has no gaps, Ns in range?
311 // In principle we have already conducted this check in check_full_coverage_and_required_taxa_in_range.
312 // This information is not shared a global scope, so it is not available any more.
313 valid_sequences[i] = !seq->range_contains_gaps_or_Ns(pos_start, pos_end);
314 if (valid_sequences[i])
315 {
316 // std::cerr << i << ", ";
317 ++ number_of_valid_sequences;
318 }
319 }
320 // std::cerr << std::endl;
321
322 // DEBUG code: Check output of back translation
323 if (global_VERBOSITY > 100)
324 {
325 std::cout << "#1 MSA:" << std::endl;
326 print_msa_backrecoded(std::cout);
327 }
328
329 // Valid distances among sequences are in the range 0..1.
330 // With a larger value we indicate a problem, e.g. Ns or gaps in the sequences.
331 // In order not to cluster sequences that contain Ns or gaps, we
332 // set the dist_threshold to a maximum value of 10.
333 // Distances with a value >10 will not be clustered.
334 // A good value for distances of sequences that contain gaps or Ns is 100.
335 if (dist_threshold > 1)
336 dist_threshold = 10;
337 }
338
339 void print_msa_backrecoded(std::ostream &os)
340 {
341 unsigned i, N=seqs->GetTaxaNum();
342
343 os << "Exon-locus MSA:" << pos_start+1 << " " << pos_end << std::endl;
344 for (i=0; i < N; ++i)
345 {
346 faststring tmp( msa[i]+pos_start, msa[i]+pos_end);
347 back_recode_range(tmp.begin(), tmp.end());
348 os.width(4);
349 if (valid_sequences[i])
350 {
351 // std::cerr.setf(ios::right);
352 os << i << "+ " << tmp << std::endl;
353 }
354 else
355 {
356 os << i << "- " << tmp << std::endl;
357 }
358 }
359 }
360
361
362 void print_msa_backrecoded_all(std::ostream &os, int flag = 0)
363 {
364 print_msa_backrecoded(os);
365
366 std::list<Csequence_cluster_and_center_sequence>::iterator it, it_end;
367 it = list_of_clusters.begin();
368 it_end = list_of_clusters.end();
369 while (it != it_end)
370 {
371 it->print_msa_backrecoded(os, flag);
372 ++it;
373 }
374 }
375
376
377 ~Csequence_loci_cluster_collection()
378 {
379 }
380
381 // Implemented in Csequence_cluster_and_center_sequence.cpp
382 void cluster_locus(faststring &, const faststring &);
383
384 // Implemented in Csequence_cluster_and_center_sequence.cpp
385
386 void compute_center_for_all_clusters(char);
387
388 void print(std::ostream &os)
389 {
390 std::list<Csequence_cluster_and_center_sequence>::iterator it, it_end;
391
392 os << "Collection of clusters and their center sequences: "
393 << pos_start+1 << " " << pos_end
394 << " dist_threshold " << dist_threshold
395 << std::endl;
396
397 it = list_of_clusters.begin();
398 it_end = list_of_clusters.end();
399
400 while (it != it_end)
401 {
402 it->print(os);
403 ++it;
404 }
405 }
406
407 void get_numbers_of_valid_sequences_number_of_clusters(unsigned short &valid_sequences, unsigned short &number_of_clusters)
408 {
409 valid_sequences = number_of_valid_sequences;
410 number_of_clusters = list_of_clusters.size();
411 }
412
413 unsigned append_center_sequences(std::vector<faststring> &v, std::vector<double> &vCG, std::vector<double> &vMaxDist)
414 {
415 unsigned count = 0;
416 std::list<Csequence_cluster_and_center_sequence>::iterator it, it_end;
417
418 it = list_of_clusters.begin();
419 it_end = list_of_clusters.end();
420
421 while (it != it_end)
422 {
423 v.push_back( it->get_center_sequence() );
424 vCG.push_back(it->get_CG() );
425
426 // std::cerr << "Getting max_dist_bait_to_msa: " << it->get_max_dist_bait_to_msa() << std::endl;
427
428 vMaxDist.push_back(it->get_max_dist_bait_to_msa() );
429 ++it;
430 ++count;
431 }
432 return count;
433 }
434
435
436 };
437
438
439
440 class CBait_region_information
441 {
442 faststring gene_name;
443 short exon_number;
444 short number_of_exons;
445 unsigned start_pos;
446 // unsigned short bait_length;
447 // unsigned short offset;
448 unsigned short number_of_baits_in_region;
449
450 std::vector<Csequence_loci_cluster_collection *> loci_this_bait_region;
451
452 // The total_number_of_valid_bait_windows_over_all_sequences_this_bait_region is effectively,
453 // the size of the evidence, or the number of sequences the baits are based on, after adding all contributions in a bait region.
454 unsigned short total_number_of_valid_bait_windows_over_all_sequences_this_bait_region;
455 unsigned short total_number_of_clusters_this_region;
456
457
458 public:
459 CBait_region_information(faststring &P_gene_name, short P_exon_number, short P_number_of_exons, unsigned P_start_pos, // unsigned short P_bait_length, unsigned short P_offset,
460 unsigned short P_number_of_baits_in_region):
461 gene_name(P_gene_name), exon_number(P_exon_number), number_of_exons(P_number_of_exons),
462 start_pos(P_start_pos), //bait_length(P_bait_length), offset(P_offset),
463 number_of_baits_in_region(P_number_of_baits_in_region),
464 total_number_of_valid_bait_windows_over_all_sequences_this_bait_region(0),
465 total_number_of_clusters_this_region(0)
466 {}
467
468 void add_info__cluster_locus(Csequence_loci_cluster_collection *p,
469 unsigned short add_to_number_of_sequences,
470 unsigned short add_to_number_of_baits)
471 {
472 loci_this_bait_region.push_back(p);
473 total_number_of_valid_bait_windows_over_all_sequences_this_bait_region += add_to_number_of_sequences;
474 total_number_of_clusters_this_region += add_to_number_of_baits;
475 }
476
477
478 void get_vector_of_bait_sequences(std::vector<faststring> &v, std::vector<unsigned> &bait_counts, std::vector<double> &vCG, std::vector<double> &vMaxDist)
479 {
480 v.clear();
481 vCG.clear();
482 vMaxDist.clear();
483
484 if (total_number_of_clusters_this_region != 0)
485 {
486 v.reserve(total_number_of_clusters_this_region);
487 vCG.reserve(total_number_of_clusters_this_region);
488 vMaxDist.reserve(total_number_of_clusters_this_region);
489 }
490 else
491 {
492 v.reserve(10*number_of_baits_in_region);
493 vCG.reserve(10*number_of_baits_in_region);
494 vMaxDist.reserve(10*number_of_baits_in_region);
495 }
496
497 int i, N=loci_this_bait_region.size();
498 unsigned count;
499 for (i=0; i<N; ++i)
500 {
501 count = loci_this_bait_region[i]->append_center_sequences(v, vCG, vMaxDist);
502 bait_counts.push_back(count);
503 }
504 }
505
506
507 void print_baits_result(std::ostream &os, const faststring &filename)
508 {
509 std::vector<faststring> v;
510 std::vector<double> vCG;
511 std::vector<double> vMaxDist;
512 std::vector<unsigned> bait_counts;
513
514 get_vector_of_bait_sequences(v, bait_counts, vCG, vMaxDist);
515
516 os.setf(std::ios::fixed);
517 os.precision(3);
518
519 os << filename << "\t"
520 << gene_name << "\t"
521 << exon_number << "\t"
522 << number_of_exons << "\t"
523 << start_pos+1 << "\t"
524 << total_number_of_valid_bait_windows_over_all_sequences_this_bait_region << "\t"
525 << total_number_of_clusters_this_region
526 << "\t";
527
528 // print_container(os, bait_counts, "(",",",")\t");
529
530 unsigned i, N;
531 N = v.size();
532
533 if (v.size() != vCG.size())
534 {
535 std::cerr << "Internal error: v and vCG have different sizes. Sizes are " << v.size() << " and " << vCG.size() << std::endl;
536 exit(-1);
537 }
538
539 if (N == 0)
540 {
541 std::cerr << "ERROR: NUMBER OF BAITS IS 0 for this locus. NEEDS TO BE VERIFIED." << std::endl;
542 exit(-11);
543 }
544
545 int index_bait_counts=0;
546 unsigned bait_sum=0;
547
548 bait_sum += bait_counts[index_bait_counts];
549 ++index_bait_counts;
550
551 for (i=0; i<N-1; ++i)
552 {
553 if (i == (bait_sum-1) )
554 {
555 os << index_bait_counts << " " << v[i] << " " << vCG[i] << " " << vMaxDist[i] << ",";
556
557 bait_sum += bait_counts[index_bait_counts];
558 ++index_bait_counts;
559 }
560 else
561 {
562 os << index_bait_counts << " " << v[i] << " " << vCG[i] << " " << vMaxDist[i] << ",";
563 }
564 }
565 os << index_bait_counts << " " << v[i] << " " << vCG[i] << " " << vMaxDist[i] << std::endl << std::flush;
566 } // END void print_baits_result(std::ostream &os, const faststring &filename)
567 }; // END class CBait_region_information
568
569
570 #endif