Debian Codegraph @

CSequences2.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 // TODO: Check all new whether they have a corresponding delete
28
29 //////////////////////////////////////////////////////////////////////
30 // CSequences.h: interface for the CSequences class.
31 //
32 //////////////////////////////////////////////////////////////////////
33
34 #ifndef CSEQUENCES2_H
35 #define CSEQUENCES2_H
36
37 #include <vector>
38 #include <map>
39 #include "faststring2.h"
40 #include "fast-realloc-vector.h"
41 #include "CSplit2.h"
42 #include "CSequence_Mol2_1.h"
43 #include <cassert>
44 #include <cmath>
45 #include <utility>
46 #include "basic-DNA-RNA-AA-routines.h"
47 #include <climits>
48
49 #include <algorithm>
50
51 //#include "basic-DNA-RNA-AA-routines.h"
52
53 #define PrintMessage_cerr(s1) fputs(s1, stderr)
54 #define ErrorMessage(s1) fputs(s1, stderr)
55 #define flush_cerr() fflush(stderr)
56
57 ////////////////////////////////////////////////////////////////////
58 // Head file for a DNA or PROTEIN sequence collection.
59 //
60 // Characteristics:
61 // - most member functions assume that sequences have identical lengths, though this is not true for all.
62 // If sequences are not of equal length, it is recommended to revise the code in this head file first.
63 //
64 ////////////////////////////////////////////////////////////////////
65
66 // Global Functions
67 //////////////////////////////////
68
69 // Criteria for reference taxa:
70 // - Original reference taxa have 2 pipes (3 sections), other sequences have 3 pipes (4 sections) in sequence names.
71 // - Hamstered reference taxa are those for which section 2 and 3 are identical in the first 4 characters.
72
73
74 /* inline bool is_1kite_hamstered_core_seq_id(faststring seq_id) */
75 /* { */
76 /* #ifdef DEBUG */
77 /* std::cerr << "Called: CSequences2.h:is_1kite_hamstered_core_seq_id with parameter " << seq_id << std::endl; */
78 /* #endif */
79
80 /* // std::cerr << "Calling outdated function: is_1kite_hamstered_core_seq_id " << std::endl; */
81 /* // exit(-1); */
82
83 /* std::vector<faststring> l; */
84
85 /* split(l, seq_id, "|"); */
86
87 /* unsigned num_sections = l.size(); */
88
89 /* if (num_sections > 4 || num_sections < 3) */
90 /* { */
91 /* std::cerr << "Error: Non standard 1kite seq_id encountered: " << seq_id << std::endl; */
92 /* exit(0); */
93 /* } */
94
95 /* #ifdef DEBUG */
96 /* std::cerr << "num_sections: " << num_sections << std::endl; */
97 /* #endif */
98
99 /* if (num_sections == 3) */
100 /* return true; */
101 /* else */
102 /* return false; */
103 /* } */
104
105
106
107 inline bool is_1kite_original_reference_taxon_seq_id(faststring seq_id)
108 {
109 #ifdef DEBUG
110 std::cerr << "Called: CSequences2.h:is_1kite_original_reference_taxon_seq_id with parameter " << seq_id << std::endl;
111 #endif
112
113 std::vector<faststring> l;
114
115 split(l, seq_id, "|");
116
117 unsigned num_sections = l.size();
118
119 if (num_sections > 4 || num_sections < 3)
120 {
121 std::cerr << "Error: Non standard 1kite seq_id encountered: " << seq_id << std::endl;
122 exit(0);
123 }
124
125 #ifdef DEBUG
126 std::cerr << "num_sections: " << num_sections << std::endl;
127 #endif
128
129 if (num_sections == 3)
130 return true;
131 else
132 return false;
133 }
134
135
136 inline bool is_1kite_hamstered_reference_seq_id(faststring seq_id)
137 {
138 std::vector<faststring> l;
139
140 split(l, seq_id, "|");
141
142 #ifdef DEBUG
143 std::cerr << "Called: CPfamScanParser.h:is_1kite_hamstered_reference_seq_id with parameter " << seq_id << std::endl;
144 #endif
145
146 if (l.size() != 4)
147 {
148 std::cerr << "Error: Non standard 1kite seq_id encountered: " << seq_id << std::endl;
149 exit(0);
150 }
151 faststring part2 = l[1];
152
153 part2.shorten_to_first_occurrence_of('_');
154 faststring part3 = l[2];
155
156 part2.shorten(4);
157 part3.shorten(4);
158
159 #ifdef DEBUG
160 std::cerr << "num_sections: " << l.size() << " " << part2 << " " << part3 << std::endl;
161 #endif
162
163 return (part2 == part3);
164 }
165
166
167
168
169 //template<class T>
170 inline void add_or_count(std::map<faststring, unsigned> &m, faststring &x)
171 {
172 std::map<faststring,unsigned>::iterator it;
173
174 it = m.find(x);
175 if (it == m.end() )
176 {
177 m[x] = 1;
178 }
179 else
180 {
181 ++it->second;
182 }
183 }
184
185 inline unsigned add_or_count_return(std::map<faststring, unsigned> &m, faststring &x)
186 {
187 std::map<faststring,unsigned>::iterator it;
188
189 it = m.find(x);
190 if (it == m.end() )
191 {
192 return m[x] = 1;
193 }
194 else
195 {
196 return (++it->second);
197 }
198 }
199
200
201 inline void vector_of_faststring_shorten_all(std::vector<faststring> &v, unsigned len)
202 {
203 unsigned N = v.size();
204 for (unsigned i=0; i< N; ++i)
205 {
206 v[i].shorten(len);
207 }
208 }
209
210 inline void vector_of_faststring_replace_characters(std::vector<faststring> &v, faststring &string_of_replacement_symbols, char skip_char)
211 {
212 unsigned char all_symbols_lookup[256];
213 faststring::size_t i;
214 unsigned j;
215
216 for (j=0; j<256; ++j)
217 {
218 all_symbols_lookup[j] = (unsigned char)j;
219 }
220
221 faststring::size_t n = string_of_replacement_symbols.size();
222 for (i=0; i<n; i+=2)
223 {
224 all_symbols_lookup[(unsigned char)string_of_replacement_symbols[i]] = string_of_replacement_symbols[i+1];
225 }
226
227 for (i=0; i < v.size(); ++i)
228 {
229 char *pos = v[i].begin();
230 char *pos_end = v[i].end();
231 char *pos_write;
232 char c;
233 unsigned removed = 0;
234 faststring::size_t N = v[i].length();
235
236 pos_write = pos;
237
238 while (pos < pos_end)
239 {
240 c = all_symbols_lookup[(unsigned char)*pos];
241 if (c != skip_char)
242 {
243 *pos_write = c;
244 ++pos_write;
245 }
246 else
247 {
248 ++removed;
249 }
250 ++pos;
251 }
252 v[i].shorten(N-removed);
253 }
254 }
255
256
257 inline void vector_of_faststring_unique(std::vector<faststring> &v, faststring::size_t len)
258 {
259 faststring::size_t digits = (unsigned)log10(v.size()) + 1;
260 faststring::size_t mlen;
261
262 if (digits+1 >= len)
263 mlen = 0;
264 else
265 mlen = len-digits-1;
266
267 std::map<faststring, unsigned> m_names, m_names_short;
268 std::map<faststring, unsigned>::iterator f_it, f_it2;
269
270 faststring tmp;
271
272 for (unsigned i=0; i < v.size(); ++i)
273 {
274 add_or_count(m_names, v[i]);
275 }
276
277 for (unsigned i=0; i < v.size(); ++i)
278 {
279 if (m_names[v[i]] > 1)
280 {
281 v[i].shorten(mlen);
282 }
283 add_or_count(m_names_short, v[i]);
284 }
285 m_names.clear();
286
287 char s = '_';
288 if (mlen == 0)
289 s = 'S';
290
291 unsigned n;
292 for (unsigned i=0; i < v.size(); ++i)
293 {
294 if (m_names_short[v[i]] > 1)
295 {
296 n = add_or_count_return(m_names, v[i]);
297 v[i] += s + faststring(n, '0', digits);
298 }
299 }
300 }
301
302
303 inline void vector_of_faststring_trimSpaces_front_back(std::vector<faststring> &v)
304 {
305 unsigned N = v.size();
306 for (unsigned i=0; i< N; ++i)
307 {
308 v[i].removeSpacesFront();
309 v[i].removeSpacesBack();
310 }
311 }
312
313
314 //////////////////////////////////
315 // Data types
316 //////////////////////////////////
317
318 //////////////////////////////////
319 // Class CSequences
320 //////////////////////////////////
321
322 // Class for aligned sequences
323
324 class CSequences2
325 {
326 public:
327 typedef char chartype;
328
329 private:
330 CSequence_Mol::DataTypesEnum datatype; // DNA, Protein, or other
331 unsigned taxaNum;
332 char ambig_char;
333 bool originalPosNumbers_supplied;
334
335 unsigned posNum;
336
337 std::vector<unsigned> originalPosNumbers; // In case we excluded positions from the alignment, we want to remember the original positions.
338 std::vector<CSequence_Mol*> seqData; // The vector of pointers to sequences
339
340
341 std::map<faststring, CSequence_Mol*> sn_map; // Obtain pointer to the sequence by sequence name.
342
343 void add_seq(CSequence_Mol* seq)
344 {
345 // std::cerr << "Adding: " << seq->getName() << std::endl;
346
347 seqData.push_back(seq);
348 sn_map[seq->getName()] = seq;
349 }
350
351 bool equal_length_of_all_sequences()
352 {
353 size_t len;
354 unsigned i;
355
356 if (taxaNum==0)
357 return true;
358
359 len = seqData[0]->length();
360
361 for (i=1; i<taxaNum; ++i)
362 {
363 if (len != seqData[i]->length())
364 return false;
365 }
366 return true;
367 }
368
369 void determine_map_of_sequence_names()
370 {
371 if (sn_map.size() == 0)
372 {
373 int i, N=seqData.size();
374 for(i=0; i<N; ++i)
375 {
376 sn_map[seqData[i]->getName()] = seqData[i];
377 }
378 }
379 }
380
381
382 public:
383 // Minimal constructor: Empty sequences object
384 CSequences2(CSequence_Mol::DataTypesEnum Dt, char set_ambig_char='?'):
385 datatype(Dt), taxaNum(0), ambig_char(set_ambig_char), originalPosNumbers_supplied(false),posNum(0)
386
387 {}
388
389 // Constructor for a set of empty sequences with names and length.
390 CSequences2(CSequence_Mol::DataTypesEnum Dt, std::vector<faststring> names, unsigned len):
391 datatype(Dt), taxaNum(names.size()), ambig_char('?'), originalPosNumbers_supplied(false),posNum(0)
392
393 {
394 seqData.reserve(taxaNum);
395 unsigned i;
396 CSequence_Mol *seq;
397
398 for (i=0; i<taxaNum; ++i)
399 {
400 seq = new CSequence_Mol (CSequence_Mol::dna, names[i], len, ambig_char);
401 add_seq(seq);
402 }
403 }
404
405
406 ~CSequences2()
407 {
408 int i, n=taxaNum;
409
410 for (i=0; i<n; ++i)
411 {
412 delete seqData[i];
413 }
414
415 }
416
417
418 // This constructor can be used to
419 // - general copy constructor
420 // - extract a range of sites
421 // Coordinates:
422 // pos1 must be the first column starting with 0.
423 // pos2 must be the index after the last column.
424 // pos2-pos1 must be the number of bases that are copied to this sequence.
425
426 CSequences2(const CSequences2 &s, faststring::size_t pos1 = 0, faststring::size_t pos2 = faststring::npos):
427 datatype(s.datatype), taxaNum(s.taxaNum), ambig_char(s.ambig_char),
428 originalPosNumbers_supplied(false), posNum(0)
429 {
430 unsigned i, n=taxaNum;
431 CSequence_Mol *seq;
432
433 for (i=0; i<n; ++i)
434 {
435 seq = new CSequence_Mol ( *(s.seqData[i]), pos1, pos2);
436 add_seq(seq);
437 }
438 if (i != n)
439 {
440 std::cerr << "Critical error in CSequences2 constructor: taxaNum and number of sequences found disagree." << std::endl;
441 }
442
443 if (n > 0)
444 posNum = seq->length();
445 }
446
447 CSequence_Mol* get_seq_by_name(faststring name)
448 {
449 // Test code:
450 {
451 // print_DEBUG(cerr, 0);
452 }
453
454 std::map<faststring, CSequence_Mol*>::iterator find_it = sn_map.find(name);
455 if (find_it != sn_map.end() )
456 return find_it->second;
457 else
458 return NULL;
459 }
460
461 CSequence_Mol* get_seq_by_index(unsigned id)
462 {
463 if (id >= seqData.size())
464 {
465 return NULL;
466 }
467 else
468 {
469 return seqData[id];
470 }
471 }
472
473 // Depreciated:
474 CSequence_Mol* get_seq(unsigned id)
475 {
476 return get_seq_by_index(id);
477 }
478
479 const char* get_Seq_Data(unsigned id)
480 {
481 if (id >= seqData.size())
482 {
483 return NULL;
484 }
485 else
486 {
487 return seqData[id]->getSeqStr();
488 }
489 }
490
491 const char* get_Seq_Name(unsigned id)
492 {
493 if (id >= seqData.size())
494 {
495 return NULL;
496 }
497 else
498 {
499 return seqData[id]->getName();
500 }
501 }
502
503 unsigned GetTaxaNum() { return taxaNum;}
504 unsigned GetPosNum() { return posNum;}
505
506 CSequence_Mol::DataTypesEnum get_datatype()
507 {
508 return datatype;
509 }
510
511 chartype GetChar(unsigned TaxaIndex,
512 unsigned PosIndex) const
513 {
514 assert(TaxaIndex < taxaNum);
515 assert(PosIndex < posNum);
516 return seqData[TaxaIndex]->get_pos(PosIndex);
517 }
518
519 void print_DEBUG(std::ostream &os, unsigned flag=1)
520 {
521 if (flag & 1) // scalars:
522 {
523 os << "Debug output CSequences2 object, flag==0" << std::endl;
524 os << "Data type: " << (int)datatype<< std::endl;
525 os << "taxaNum: " << taxaNum << std::endl;
526 os << "posNum: " << posNum << std::endl;
527 os << "ambig_char: " << ambig_char << std::endl;
528 os << "originalPosNumbers_supplied " << (int)originalPosNumbers_supplied << std::endl;
529
530 os << "size of originalPosNumbers vector: " << originalPosNumbers.size() << std::endl;
531 os << "size of seqData : " << seqData.size() << std::endl;
532 os << "size of sn_map : " << sn_map.size() << std::endl;
533 }
534
535 if (flag & 2)
536 {
537 int i, n=seqData.size();
538
539 os << "Data types of sequences:\n";
540 for (i=0; i<n; ++i)
541 {
542 os << i << ": " << seqData[i]->get_datatype() << " " << seqData[i]->type_as_string() << std::endl;
543 }
544 }
545 }
546
547
548
549 /* void SetChar(unsigned TaxaIndex, unsigned PosIndex, chartype mychar) */
550 /* { */
551 /* assert(TaxaIndex < taxaNum); */
552 /* assert(PosIndex < posNum); */
553 /* seqData[TaxaIndex]->set_pos(PosIndex, mychar); */
554 /* } */
555
556 void SetOriginalPosNumber(unsigned index, unsigned theOriginalPosNumber)
557 {
558 originalPosNumbers_supplied = true;
559 assert(index < posNum);
560 originalPosNumbers[index] = theOriginalPosNumber;
561 }
562
563 unsigned GetOriginalPosNumber(unsigned index) const
564 {
565 assert(index < posNum);
566 if (originalPosNumbers_supplied)
567 return originalPosNumbers[index];
568 else
569 return UINT_MAX;
570 }
571
572 // Moves taxon with index index to top, preserving the order of all other taxa.
573 // Of course this changes all indices with the only exception that this taxon is
574 // already at the top of the vector.
575 // The index is of course 0 based.
576 void reorder_move_seq_to_top(unsigned index)
577 {
578 if (index < taxaNum && index > 0)
579 {
580 seqData.insert(seqData.begin(), seqData[index]);
581 seqData.erase(seqData.begin()+index+1); // We have to add 1 since we have one additional entry at the beginning
582 }
583 }
584
585 // TODO: Not very efficient!!
586 // Return true if taxon_name has been found, false otherwise
587 bool reorder_move_seq_to_top(faststring &taxon_name)
588 {
589 unsigned i;
590 for (i=0; i< taxaNum; ++i)
591 {
592 faststring iname = seqData[i]->getFullName();
593 if (seqData[i]->getFullName() == taxon_name)
594 {
595 std::cerr << "Move to top: " << i << std::endl;
596 reorder_move_seq_to_top(i);
597 return true;
598 }
599 }
600 return false;
601 }
602
603 // Reorder the sequences such the those in the given vector are at the top
604 // in the order given by the vector.
605 // TODO: Not very efficient! - Very simple and thus secure implementation.
606 bool reorder_sort_by(std::vector<faststring> &names)
607 {
608 int i,n=names.size();
609 bool success = true;
610
611 for (i=n-1; i>=0; --i)
612 {
613 success = success & reorder_move_seq_to_top(names[i]);
614 }
615 return success;
616 }
617
618 bool get_Originalposnumbers_Supplied()
619 {
620 return originalPosNumbers_supplied;
621 }
622
623 char get_ambiguity_character()
624 {
625 return ambig_char;
626 }
627
628
629 // Returns the maximum sequence, length
630 void get_sequence_names(std::vector<faststring> &snames)
631 {
632 snames.clear();
633 unsigned i;
634 // unsigned max=0;
635
636 for (i=0; i < taxaNum; ++i)
637 {
638 snames.push_back(seqData[i]->getFullName());
639 /* if (snames[i].size() > max) */
640 /* { */
641 /* max = snames[i].size(); */
642 /* } */
643 }
644 // return max;
645 }
646
647 // Not yet implemented
648 /* void unique_full_names(std::vector<faststring> &snames) */
649 /* { */
650
651 /* } */
652
653 // Not yet implemented
654 /* void unique_short_names(std::vector<faststring> &snames) */
655 /* { */
656
657 /* } */
658
659
660 /*
661 void unique_maxlen_names(std::vector<faststring> &snames, int ulen=10)
662 {
663 snames.clear();
664 std::map<faststring, unsigned> m_snames;
665 std::map<faststring, unsigned> m_shortend_names;
666 std::map<faststring, unsigned>::iterator f_it, f_it2;
667
668 unsigned digits = (unsigned)log10(taxaNum) + 1;
669 unsigned i;
670 faststring tmp;
671 faststring tmp_short;
672
673 if (ulen - 1 < digits)
674 {
675 std::cerr << "Internal library error: Attempt to shorten sequence names to negative length. Usage of the function: unique_maxlen_names should be revised." << std::endl;
676 exit(-1);
677 }
678
679 for (i=0; i < taxaNum; ++i)
680 {
681 tmp = seqData[i]->getPhylipName(ulen);
682 f_it = m_snames.find(tmp);
683 // If we find it it is not unique
684 if (f_it != m_snames.end() ) // This name is not unique
685 {
686 ++f_it->second; // We count this occurrence
687 }
688 }
689
690 for (i=0; i < taxaNum; ++i)
691 {
692 tmp = seqData[i]->getPhylipName(ulen);
693 // snames.push_back(seqData[i]->getPhylipName());
694 f_it = m_snames.find(tmp);
695 if (f_it->second > 0 ) // This name is not unique
696 {
697 tmp_short = tmp;
698 tmp_short.resize(ulen-digits-1, ' ');
699 // We know that we will have multiple entries in the end.
700 f_it2 = m_shortend_names.find(tmp_short);
701 // It could be that this will the first entry
702 if (f_it2 != m_shortend_names.end() )
703 {}
704 }
705 else // Otherwise we will have only one entry.
706 {
707 snames.push_back(tmp);
708 }
709
710
711
712
713 }
714
715 ///
716
717
718
719 for (i=0; i < taxaNum; ++i)
720 {
721 // push_back first sequence phylip sequence name. This is already trimmed to 10 characters.
722 snames.push_back(seqData[i]->getPhylipName(ulen));
723 // Search for this name in m_snames map.
724 f_it = m_snames.find(snames[i]);
725
726 // If we find it it is not unique
727 if (f_it != m_snames.end() ) // This name is not unique
728 {
729 ++f_it->second; // We count this occurrence
730 }
731 else // If we do not find it, we insert it and set the counter to 1
732 {
733 m_snames.insert(std::make_pair(snames[i], 1));
734 }
735 }
736 // We have build the map that count the number of occurrences - now we need to create unique names:
737
738 // We will shorten the names to add a number.
739 // When shortening names, previously unique names might become non-unique so we have to take care of this first:
740
741 f_it = m_snames.begin();
742 while (f_it != m_snames.end() )
743 {
744 // std::cout << f_it->first << " " << f_it->second << std::endl;
745
746 if (f_it->second > 1) // If the 10 character sequence name occurs more than one, we have to number them:
747 {
748 faststring temp = f_it->first;
749 temp.shorten(9-digits);
750
751 f_it2 = m_shortend_names.find(temp);
752 if (f_it2 == m_shortend_names.end() ) // We already have this name in the map:
753 {
754 m_shortend_names[temp] += f_it->second;
755 }
756 else // Create this entry:
757 {
758 m_shortend_names[temp] = f_it->second;
759 }
760 }
761 ++f_it;
762 }
763
764 // Now we have two maps:
765 // The first has entries for all names
766 // The second has entries for all names that need to be shortened.
767
768 // For all names that need to be shortened:
769 f_it = m_shortend_names.begin();
770 while (f_it != m_shortend_names.end() )
771 {
772 unsigned internal_counter = 1;
773 unsigned j;
774 faststring temp;
775 for (j=0; j<taxaNum; ++j)
776 {
777 temp = snames[j];
778 if ( m_snames[temp] != 1 )
779 {
780 temp.shorten(10-digits);
781 }
782 if (temp == f_it->first)
783 {
784 faststring nn = faststring(internal_counter, '0', digits);
785 // nn.replace_char(' ', '0');
786
787 snames[j] = temp;
788 snames[j].append('_');
789
790 snames[j].append(nn);
791 ++internal_counter;
792 }
793 }
794 ++f_it;
795 }
796 }
797 */
798
799 unsigned PairwiseSequenceSymbolMatches(unsigned taxon1, unsigned taxon2,
800 char numDistCharacters,
801 const signed char* pos_vec,
802 signed char* match_vec) const
803 {
804 unsigned count = 0;
805 unsigned pos;
806
807 for (pos = 0; pos < posNum; ++pos)
808 {
809 if (pos_vec[pos] &&
810 seqData[taxon1]->get_pos(pos) == seqData[taxon2]->get_pos(pos) &&
811 seqData[taxon1]->get_pos(pos) < numDistCharacters)
812 {
813 ++count;
814 match_vec[pos] = 1;
815 }
816 else
817 match_vec[pos] = 0;
818 }
819 return count;
820 }
821
822
823 unsigned PairwiseSequenceSymbolMatches(
824 unsigned taxon1,
825 const faststring & ref_seq,
826 char numDistCharacters,
827 const signed char* pos_vec,
828 signed char* match_vec) const
829
830
831 // Ist hier alles OK?????????????????????????????????????????
832 {
833 unsigned count = 0;
834 unsigned pos;
835
836 for (pos = 0; pos < posNum; ++pos)
837 {
838 if (pos_vec[pos] && seqData[taxon1]->get_pos(pos) == ref_seq[pos]
839 && ref_seq[pos] < numDistCharacters)
840 {
841 ++count;
842 match_vec[pos] = 1;
843 }
844 else
845 match_vec[pos] = 0;
846 }
847 return count;
848 }
849
850
851 void ConsensusSequence(faststring& conSeq,
852 const CSplit& setOfTaxa,
853 char numDistCharacters,
854 unsigned numSymbols,
855 double consensusThreshold )
856 {
857 unsigned pos;
858 unsigned taxon, maxindex, equalindex;
859 unsigned taxaCount = 0;
860 unsigned consensusSymMinimum;
861 char i;
862
863
864 std::vector<unsigned> counterSymbolsVec(numSymbols,0);
865
866 for (pos=0; pos < posNum; ++pos)
867 {
868 // Initialise variable
869 taxaCount = 0;
870 for (i=0; i < numDistCharacters; ++i)
871 counterSymbolsVec[i] = 0;
872
873 // Count number of occuring symbols for this position over all taxa
874 for (taxon = 0; taxon < taxaNum; ++taxon)
875 {
876 if (setOfTaxa.test(taxon))
877 {
878 ++taxaCount;
879 ++counterSymbolsVec[seqData[taxon]->get_pos(pos)];
880 }
881 }
882
883 consensusSymMinimum = (unsigned) std::ceil(consensusThreshold * taxaCount);
884
885 maxindex = 0;
886 equalindex = numDistCharacters;
887 for (i = 1; i < numDistCharacters; ++i)
888 {
889 if (counterSymbolsVec[i] >= counterSymbolsVec[maxindex])
890 {
891 if (counterSymbolsVec[i] == counterSymbolsVec[maxindex])
892 equalindex = i;
893 maxindex = i;
894 }
895 }
896 if (counterSymbolsVec[maxindex] >= consensusSymMinimum &&
897 maxindex != equalindex)
898 conSeq[pos] = maxindex;
899 else // Default value, in case consensus cannot be determined
900 conSeq[pos] = numDistCharacters;
901 }
902 }
903
904
905 void GetSymbolFrequenciesAtPosition(unsigned pos, const CSplit &taxaSet,
906 unsigned numSymbols,
907 std::vector<unsigned>& frequencies)
908 {
909 unsigned i;
910 // chartype sym;
911
912 // assert(frequencies.size() <= numDistCharacters);
913
914 for (i=0; i<numSymbols; ++i)
915 frequencies[i]=0;
916
917 for (i=0; i<taxaNum; ++i)
918 {
919 if (taxaSet.test(i))
920 {
921 ++frequencies[seqData[i]->get_pos(pos)];
922 }
923 }
924 }
925
926 int read_from_Fasta_File(CFile& infile,
927 CSequence_Mol::processing_flag pflag,
928 unsigned first_seq,
929 unsigned last_seq,
930 bool report_status_to_cerr=true
931 )
932 {
933 CSequence_Mol *seq;
934 unsigned count_seq = 0;
935 unsigned count_seqs_stored = 0;
936
937
938 // TODO
939 (void) report_status_to_cerr;
940
941 // Remove all sequences from this object - we want to read a new data set.
942 clear(datatype);
943
944 while (!infile.eof())
945 {
946 seq = new CSequence_Mol (datatype);
947 ++count_seq;
948
949 seq->readFastaSequence_generic(infile, pflag);
950
951 // PrintMessage_cerr(seq.getName());PrintMessage_cerr("-\n");PrintMessage_cerr(seq.getFullName());PrintMessage_cerr("-\n");PrintMessage_cerr(seq.getDescription());PrintMessage_cerr("-\n");
952 if ( infile.fail() && !infile.eof() )
953 {
954 if (infile.fail_reason1() )
955 {
956 PrintMessage_cerr("\n\n");
957 faststring errormsg;
958 errormsg = "An error occurred while reading the input file. The data type of the sequence is DNA, but the sequence that is read contains non-DNA symbols.\n";
959 errormsg += "File position: line ";
960 errormsg += faststring(infile.line());
961 ErrorMessage(errormsg.c_str());
962 PrintMessage_cerr("\n");
963 flush_cerr();
964 return -24;
965 } else
966 if (infile.fail_reason2() )
967 {
968 PrintMessage_cerr("\n\n");
969 faststring errormsg;
970 errormsg = "An error occurred while reading the input file. The data type of the sequence is protein, but the sequence that is read from the file contains non valid amino acid symbols.\n";
971 errormsg += "File position: line ";
972 errormsg += faststring(infile.line());
973 ErrorMessage(errormsg.c_str());
974 PrintMessage_cerr("\n");
975 flush_cerr();
976 return -24;
977 }
978 else
979 {
980 PrintMessage_cerr("\n\n");
981 faststring errormsg;
982 errormsg = "An error occurred while reading the input file. It might not be a valid fasta file.\n";
983 errormsg += "File position: line ";
984 errormsg += faststring(infile.line());
985 ErrorMessage(errormsg.c_str());
986 PrintMessage_cerr("\n");
987 flush_cerr();
988 return -25;
989 }
990 }
991
992 if ( count_seq < first_seq || count_seq > last_seq )
993 {
994 if (report_status_to_cerr)
995 {
996 PrintMessage_cerr("Skipping sequence ");
997 PrintMessage_cerr(faststring(count_seq).c_str());
998 PrintMessage_cerr(": ");
999 PrintMessage_cerr(seq->getName());
1000 PrintMessage_cerr("\n");
1001 flush_cerr();
1002 }
1003 continue;
1004 }
1005
1006 if (report_status_to_cerr)
1007 {
1008 PrintMessage_cerr("Processing sequence ");
1009 PrintMessage_cerr(faststring(count_seq).c_str());
1010 PrintMessage_cerr(": ");
1011 PrintMessage_cerr(seq->getName());
1012 PrintMessage_cerr("\n");
1013 flush_cerr();
1014 }
1015
1016 add_seq(seq);
1017 ++count_seqs_stored;
1018 } // End while
1019
1020 // Check that all sequences have the same length - we require that they have the same length
1021 if (!equal_length_of_all_sequences() )
1022 return -1;
1023
1024 // Check equal data type and ambig character:
1025
1026 taxaNum = count_seqs_stored;
1027
1028 if (taxaNum > 0)
1029 {
1030 posNum = seqData[0]->length();
1031 ambig_char = seqData[0]->get_ambiguity_character();
1032 }
1033
1034 return 0;
1035 } // End this element function.
1036
1037
1038 // Can read the following format variants:
1039 // Can read sequential and interleaved phylip files
1040 // Can read strict and relaxed, i.e. 4 combinations.
1041
1042 // Cannot read multi phylip files.
1043
1044 // format_flag: 0 strict phylip standard. Sequence names are exactly 10 characters long.
1045 // 1 relaxed sequence name length. Sequence names end with first space and can have any length.
1046 // Spaces are not allowed in sequence names.
1047
1048
1049 int read_from_Phylip_File(CFile& infile, unsigned format_flag = 1)
1050 {
1051 CSequence_Mol *seq;
1052 // unsigned count_seq;
1053 // unsigned global_sequence_from=0, global_sequence_to=UINT_MAX;
1054 // bool global_gaps_to_Ns=false;
1055 unsigned all_lines_N;
1056 unsigned curr_taxon;
1057
1058 char read_mode;
1059
1060 // The allowed symbols from the phylip manual:
1061
1062
1063 char ch;
1064 faststring line;
1065 std::vector<faststring> fsvec;
1066 faststring *p;
1067
1068 // Clear the oject and initialize it with the supplied data type
1069 clear(datatype); // XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1070
1071 ch = infile.peek();
1072
1073 // If the first char is a white space or a digit, we expect this
1074 // is the line with the number of taxa and seq. positions.
1075 if ( isspace(ch) || isdigit(ch) )
1076 {
1077 infile.getline(line);
1078 split(fsvec, line);
1079
1080 if (fsvec.size()==2 && fsvec[0].isAnUnsigned() && fsvec[1].isAnUnsigned() )
1081 {
1082 taxaNum = fsvec[0].ToUnsigned();
1083 posNum = fsvec[1].ToUnsigned();
1084
1085 /* std::cout << "Number of taxa " << taxaNum << std::endl; */
1086 /* std::cout << "Number of residues " << posNum << std::endl; */
1087 }
1088 }
1089
1090 // std::vector<faststring*> sqs;
1091 std::vector<faststring*> all_lines;
1092
1093 /* if (taxaNum == 0 && posNum == 0) */
1094 /* { */
1095 /* faststring *pp = new faststring; */
1096 /* *pp = line; */
1097 /* all_lines.push_back(pp); */
1098 /* } */
1099
1100 // We read the complete file into a vector of strings.
1101 p = new faststring();
1102 infile.getline(*p);
1103 p->removeSpacesFront();
1104 p->removeSpacesBack();
1105
1106 while (!infile.fail() )
1107 {
1108 all_lines.push_back(p);
1109 p = new faststring();
1110 infile.getline(*p);
1111 p->removeSpacesFront();
1112 p->removeSpacesBack();
1113 }
1114
1115 // The problem is: The phylip format is very difficult
1116 // to parse. Main problem is to distinguish between
1117 // sequential and interleaved format.
1118 // The interleaved format is distinguished as follows:
1119 // After each block there must be a blank line.
1120 // So if we find blank lines which are not the last line
1121 // the format is interleaved. Otherwise it is sequential.
1122
1123 // Another problem is relaxed versus strict format.
1124 // In the related format the sequence name and the sequence are separated by white spaces.
1125 // In the strict format the sequence name is less or equal to 10 character.
1126 // Example: Name123456A MILLV
1127 // Can be interpreted as sequence AMILLV or as sequence MILLV with the two different names.
1128 // In the strit format the following would be legal:
1129 // NAME123456MILLVWSAL LADDPKHIMV
1130 // The sequence name would be NAME123456 the rest is the sequence.
1131 // Note that the format allows spaces in the sequence.
1132 // The two versions cannot be distinguished unambiguously!!
1133 // Pragmatic approach: In the presence of one white space island, we assume the relaxed format.
1134 // Otherwise the strict format.
1135
1136 // Since empty lines are allowed at the end of the file in all formats we remove them.
1137 // They cannot be indicative of the interleaved format.
1138
1139 unsigned i;
1140 all_lines_N = all_lines.size();
1141
1142 // std::cerr << all_lines[all_lines_N-1]->length() << std::endl;
1143
1144 while (all_lines[all_lines_N-1]->length() == 0)
1145 {
1146 --all_lines_N;
1147 delete all_lines[all_lines_N];
1148 std::vector<faststring*>::iterator it = all_lines.end();
1149 --it;
1150 all_lines.erase(it);
1151 }
1152
1153 unsigned number_blank_lines=0;
1154
1155 for (i=0; i<all_lines_N; ++i)
1156 {
1157 if (all_lines[i]->length() == 0)
1158 {
1159 ++number_blank_lines;
1160 }
1161 }
1162
1163 if (all_lines_N == 0 || number_blank_lines == all_lines_N) // Nothing to do???
1164 return 0;
1165
1166 if (number_blank_lines == 0) // sequential format
1167 {
1168 read_mode = 's';
1169 // Example:
1170 //a ATGATTCAAC CTCAGACCCT TTTAAATGTA GCAGATAACA GTGGAGCTCG
1171 // AAAATTGATG
1172 //b ATGATTCAAC CTCAGACCCA TTTAAATGTA GCGGATAACA GCGGGGCTCG
1173 // AGAATTGATG
1174
1175 // This can only be interpreted, if the number
1176 // of taxa and positions has been specified in
1177 // the first line.
1178 // What makes it more complicated
1179 // is the fact, that the phylip format tolerates
1180 // numbers and other stuff at the beginning of pure sequence lines.
1181
1182 faststring seq_taxon_name;
1183 faststring seq_in_one_line;
1184 // unsigned current_length = 0;
1185 unsigned curr_line_num=0;
1186
1187 faststring *currLine;
1188
1189
1190 if (taxaNum == 0 || posNum == 0)
1191 {
1192 // delete all faststrings in all_lines
1193 for (unsigned ind=0; ind < all_lines.size(); ++ind)
1194 delete all_lines[ind];
1195 return -3;
1196 }
1197
1198
1199 // For all taxa
1200 //
1201 for (curr_taxon = 0; curr_taxon < taxaNum; ++curr_taxon)
1202 {
1203 if (curr_line_num >= all_lines_N)
1204 {
1205 std::cerr << "Parse error while reading the input file:\nUnexpected end of file in line: " << curr_line_num << std::endl;
1206 std::cerr << "Trying to read " << taxaNum << " taxa but found only " << curr_taxon << "!" << std::endl;
1207
1208 exit(-45);
1209 }
1210
1211 currLine = all_lines[curr_line_num];
1212 const char* pos = currLine->c_str();
1213 // currLineLen = currLine->length();
1214 seq_taxon_name.clear();
1215 seq_in_one_line.clear();
1216
1217 // Copy the sequence name
1218 if (format_flag == 0)
1219 {
1220 for (i=0; i<10 && *pos != '\0'; ++i, ++pos)
1221 {
1222 seq_taxon_name.push_back(*pos);
1223 }
1224 if (i<10) // Fill name with spaces.
1225 seq_taxon_name.append(10-i, ' ');
1226 }
1227 else
1228 {
1229 for (; (*pos != '\0') && (*pos != ' ' && *pos != '\t') ; ++pos)
1230 {
1231 seq_taxon_name.push_back(*pos);
1232 }
1233 }
1234
1235 // Skip all spaces:
1236 while ( *pos != '\0' && (*pos == ' ' || *pos == '\t') )
1237 ++pos;
1238
1239 // Read data after sequence name:
1240 if (*pos)
1241 {
1242 // Copy the sequence data:
1243 {
1244 // Find first character that shall be copied.
1245 // pos should point to the first char of the sequence.
1246 char c;
1247
1248 // Skip all non-allowed symbols - since we skipped spaces, there should be none.
1249 c = *pos;
1250 while (!is_phylip_aa_dna_symbol(c) && !is_allowed_non_ABC(c) )
1251 {
1252 ++pos;
1253 c = *pos;
1254 }
1255 }
1256 // Now pos points to the first char that should be copied:
1257 while (*pos)
1258 {
1259 if (*pos != ' ' && *pos != '\t')
1260 {
1261 seq_in_one_line.push_back(*pos);
1262 }
1263 ++pos;
1264 }
1265 } // END if (*pos) AND read data after sequence name.
1266
1267 // Read lines until we have the required number of residues:
1268 // TODO: More error checking could be done here:
1269 // We could check that only allowed symbols are added.
1270 // By this we also might be able to detect an error earlier
1271 while (seq_in_one_line.length() < posNum)
1272 {
1273 ++curr_line_num;
1274 if (curr_line_num >= all_lines_N)
1275 {
1276 std::cerr << "Parse error while reading the input file. The file has been interpreted as being in sequential phylip format." << std::endl;
1277 std::cerr << "Several problems can trigger this error: (i) Wrong number of residues in sequences compared to the number specified " << std::endl;
1278 std::cerr << "in the file header. (ii) Wrong number of taxa (sequences) compared to the number specified in the file header." << std::endl;
1279 std::cerr << "(iii) Missing blank line between blocks of data if this file should be in interleaved format." << std::endl;
1280 exit(-44);
1281 }
1282 currLine = all_lines[curr_line_num];
1283 // const char* pos = currLine->c_str();
1284 {
1285 // Find first character that shall be copied.
1286 char c;
1287 pos = currLine->c_str();
1288 c = *pos;
1289 while (!is_phylip_aa_dna_symbol(c) && !is_allowed_non_ABC(c) )
1290 {
1291 ++pos;
1292 c = *pos;
1293 }
1294 }
1295 // Now pos points to the first char that should be copied:
1296 // Here we are in the sequential section, reading all residues until
1297 // we have filled our sequence.
1298 while (*pos)
1299 {
1300 if (*pos != ' ' && *pos != '\t')
1301 {
1302 seq_in_one_line.push_back(*pos);
1303 }
1304 ++pos;
1305 }
1306 }
1307 // If we are here, the sequence should have been copied to
1308 // seq_in_one_line
1309
1310 seq = new CSequence_Mol (datatype);
1311 seq->set_taxon_and_sequence(seq_taxon_name, seq_in_one_line, datatype);
1312 add_seq(seq);
1313
1314 // The next line should start with a new sequence:
1315 ++curr_line_num;
1316
1317 } // End for loop - for all taxa
1318
1319 if (curr_line_num != all_lines_N)
1320 {
1321 std::cerr << "Parse error while reading the input file: This can have several reasons:\n"
1322 "(i) The number of taxa found in the first block does not match the number specified in the file header.\n"
1323 "(ii) Since only one data block was found, this file is interpreted as sequential format. If this should be a file\n"
1324 "in interleaved format, blank line must be added between blocks of data.\n"
1325 "(iii) It could also be that the number of residues in the sequences is larger than specified in the header, so that additional\n"
1326 "lines of data are interpreted as additional taxa in the sequential format." << std::endl;
1327 exit(-67);
1328 }
1329
1330 } // End sequential format
1331 else // Interleaved format
1332 {
1333 read_mode = 'i';
1334 // In the first block, the first 10 characters are
1335 // the sequence name. Then the first base starts
1336 // the sequence.
1337 // After the first block, the sequence begins/continues at
1338 // the first base symbol in each line. Thus, numbers and spaces are ignored.
1339 // Sequence names are not allowed in interleaved blocks.
1340
1341 // With format_flag == 1 we may have a different number of sequence name characters.
1342 // But then, no spaces are allowed in the sequence name.
1343
1344 unsigned curr_line_num=0;
1345 faststring *currLine;
1346
1347 // unsigned current_length = 0;
1348 unsigned curr_taxon = 0;
1349
1350 faststring *pseq_taxon_name = NULL;
1351 faststring *pseq_in_one_line = NULL;
1352
1353 std::vector<faststring*> taxonnames;
1354 std::vector<faststring*> sequences;
1355
1356 currLine = all_lines[curr_line_num];
1357 const char* pos;
1358
1359 // read first block (interleaved) - until we find a blank line:
1360 while ( currLine->length() != 0 ) // We read all lines of the first block. Counter: curr_line_num
1361 {
1362 pos = currLine->c_str();
1363
1364 // We will store all pointer to sequences in the vectors defined above,
1365 // so we do not delete sequences here. We keep on creating new ones.
1366 pseq_taxon_name = new faststring;
1367 pseq_in_one_line = new faststring;
1368
1369 // Copy the sequence name
1370 if (format_flag == 0)
1371 {
1372 for (i=0; i<10 && *pos != '\0'; ++i, ++pos)
1373 {
1374 pseq_taxon_name->push_back(*pos);
1375 }
1376 if (i<10) // Fill name with spaces.
1377 pseq_taxon_name->append(10-i, ' ');
1378 }
1379 else
1380 {
1381 for (;*pos != '\0' && *pos != ' ' && *pos != '\t'; ++pos)
1382 {
1383 pseq_taxon_name->push_back(*pos);
1384 }
1385 }
1386
1387 // Skip all spaces:
1388 while (*pos == ' ' && *pos != '\0' && *pos != '\t')
1389 ++pos;
1390
1391 // Read data after sequence name:
1392 if (*pos) // we need to read the rest of the line
1393 {
1394 // Copy the sequence data:
1395 {
1396 char c;
1397
1398 c = *pos;
1399 while (!is_phylip_aa_dna_symbol(c) && !is_allowed_non_ABC(c) )
1400 {
1401 ++pos;
1402 c = *pos;
1403 }
1404 }
1405 // Now pos points to the first char that should be copied:
1406 while (*pos)
1407 {
1408 if (*pos != ' ' && *pos != '\t')
1409 pseq_in_one_line->push_back(*pos);
1410 ++pos;
1411 }
1412 } // if (*pos) AND read data after sequence name.
1413
1414 // Another taxon has been read: Let us store it:
1415
1416 taxonnames.push_back(pseq_taxon_name);
1417 sequences.push_back(pseq_in_one_line);
1418
1419 // std::cerr << "Read partial sequence" << std::endl;
1420 // std::cerr << pseq_taxon_name->c_str() << std::endl;
1421 // std::cerr << pseq_in_one_line->c_str() << std::endl;
1422
1423
1424 // Read next line with next taxon name
1425 ++curr_taxon;
1426 ++curr_line_num;
1427 if (curr_line_num >= all_lines_N)
1428 break;
1429 // If we break, currLine will be set to its new value further down
1430 currLine = all_lines[curr_line_num];
1431 } // End while loop over all non blank lines in first block (interleaved)
1432
1433 // All remaining blocks still need to be read.
1434
1435 if (taxaNum == 0 && posNum == 0)
1436 taxaNum = curr_taxon;
1437
1438 // Check that the number of taxa that might had been specified agrees with the
1439 // number of taxa we found now.
1440 if (taxaNum != 0 && taxaNum != curr_taxon) // do we have a problem?
1441 {
1442 std::cerr << "Parse error while reading the input file:\nThe number of taxa in the first block of the input file ("
1443 << curr_taxon << ") does not match the number of taxa specified in the header of the phylip file (" << taxaNum << ") "
1444 << std::endl;
1445 exit(-55);
1446 }
1447
1448 // This line should be blank: Skip blank lines between the blocks
1449 while (curr_line_num < all_lines_N && all_lines[curr_line_num]->length()==0)
1450 {
1451 ++curr_line_num;
1452 }
1453
1454 // Now we need to read all remaining blocks:
1455 while (true) // (curr_line_num < all_lines_N)
1456 {
1457 // Read the next block:
1458 for (curr_taxon=0; curr_taxon < taxaNum; ++curr_taxon)
1459 {
1460 // The current line should be the first line of this block
1461 if (curr_line_num >= all_lines_N)
1462 {
1463 // We are within a block and ran out of lines:
1464 std::cerr << "Parse error while reading the input file:\nUnexpected end of file. More data has been expected." << std::endl;
1465 exit(-46);
1466 }
1467
1468 currLine = all_lines[curr_line_num];
1469
1470 // Find first character that shall be copied.
1471 char c;
1472 pos = currLine->c_str();
1473 c = *pos;
1474 while (!is_phylip_aa_dna_symbol(c) && !is_allowed_non_ABC(c) )
1475 {
1476 ++pos;
1477 c = *pos;
1478 }
1479
1480 // Copy the sequence on this line to our data.
1481 while (*pos)
1482 {
1483 if (*pos != ' ' && *pos != '\t')
1484 sequences[curr_taxon]->push_back(*pos);
1485 ++pos;
1486 }
1487 ++curr_line_num;
1488 } // End of for loop which reads the next block
1489
1490 // The next line(s) should be blank or we should be at the end of the list of lines
1491 if (curr_line_num < all_lines_N && all_lines[curr_line_num]->length()!=0)
1492 {
1493 std::cerr << "Parse error while reading the input file:\nThe phylip file was interpreted to be in the phylip format."
1494 "Either the number of lines of data in one of the data blocks is not identical to the number of taxa\n"
1495 "or a blank line might be missing between different data blocks in the interleaved format." << std::endl;
1496 std::cerr << "This problem was detected in line " << curr_line_num+1 << " of the file, but it could have occurred earlier." << std::endl;
1497 exit(-77);
1498 }
1499
1500 while (curr_line_num < all_lines_N && all_lines[curr_line_num]->length()==0)
1501 {
1502 ++curr_line_num;
1503 }
1504 if (curr_line_num >= all_lines_N) // we parsed all lines of the data set.
1505 {
1506 break;
1507 }
1508 // This should be the first line of the next block
1509 currLine = all_lines[curr_line_num];
1510 // XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1511 } // End while loop read all blocks
1512
1513 if (taxaNum > 0 && posNum == 0)
1514 posNum = sequences[0]->length();
1515
1516 // Now we should have read the sequences
1517 // and we can delete the data we reserved.
1518 for (curr_taxon=0; curr_taxon < taxaNum; ++curr_taxon)
1519 {
1520 seq = new CSequence_Mol (datatype);
1521 seq->set_taxon_and_sequence(*taxonnames[curr_taxon], *sequences[curr_taxon], datatype);
1522 add_seq(seq);
1523 delete taxonnames[curr_taxon];
1524 delete sequences[curr_taxon];
1525 }
1526 } // End interleaved format
1527
1528
1529 // Do some final error checking
1530
1531 if (taxaNum == 0)
1532 {
1533 // delete all faststrings in all_lines
1534 for (unsigned ind=0; ind < all_lines.size(); ++ind)
1535 delete all_lines[ind];
1536 return 0;
1537 }
1538
1539 unsigned len1 = seqData[0]->length();
1540
1541 if (len1 != posNum)
1542 {
1543 std::cerr << "Parse error while reading the input file:\n"
1544 << "The file was interpreted in the " << (read_mode == 's'? "sequential":"interleaved") << " format.\n"
1545 "The number of positions specified in the file header is not identical to the number of positons\n"
1546 "in the first sequence.\n"
1547 "This can have multiple reasons:\n"
1548 "In the interleaved format, make sure, taxon names only occur in the first block of sequences.\n"
1549 "In the interleaved format a blank line must be found between all blocks of data." << std::endl;
1550 std::cerr << "The number of positions in the first sequence is: " << len1
1551 << ", while the number specified in the header is " << posNum << "."<< std::endl;
1552
1553 // std::cerr << seqData[0]->getSeqStr() << std::endl;
1554
1555 exit(-66);
1556 }
1557
1558 unsigned len2;
1559 // Check that the number of positions is correct and equal for all sequences:
1560 for (curr_taxon=1; curr_taxon < taxaNum; ++curr_taxon)
1561 {
1562 seq = seqData[curr_taxon];
1563 len2 = seq->length();
1564
1565 if (len1 != len2)
1566 {
1567 std::cerr << "Parse error while reading the input file:\nThe number of residues in sequence " << curr_taxon+1 << " differs from the number of residues in sequence 1. The sequence lengths for sequence 1 and sequence " << curr_taxon+1
1568 << " are respectively " << len1 << " and " << len2 << "." << std::endl;
1569 exit(-67);
1570 }
1571 }
1572
1573 // Check that the data type is equal for all sequences and that
1574 CSequence_Mol::DataTypesEnum dt_tmp;
1575
1576 datatype = seqData[0]->get_datatype();
1577 for (curr_taxon=1; curr_taxon < taxaNum; ++curr_taxon)
1578 {
1579 dt_tmp = seqData[curr_taxon]->get_datatype();
1580
1581 if (datatype != dt_tmp)
1582 {
1583 std::cerr << "Warning: Not all sequences seem to have the same data type.\n";
1584 datatype = CSequence_Mol::mixed;
1585 }
1586 }
1587
1588 char ambig0, ambig_tmp;
1589 ambig0 = seqData[0]->get_ambiguity_character();
1590 for (curr_taxon=1; curr_taxon < taxaNum; ++curr_taxon)
1591 {
1592 ambig_tmp = seqData[curr_taxon]->get_ambiguity_character();
1593
1594 if (ambig0 != ambig_tmp)
1595 {
1596 std::cerr << "Warning: Not all sequences seem to have the same ambiguity character.\n";
1597 }
1598 }
1599
1600
1601
1602
1603 /* // PrintMessage_cerr(seq.getName());PrintMessage_cerr("-\n");PrintMessage_cerr(seq.getFullName());PrintMessage_cerr("-\n");PrintMessage_cerr(seq.getDescription());PrintMessage_cerr("-\n"); */
1604 /* if ( infile.fail() && !infile.eof() ) */
1605 /* { */
1606 /* PrintMessage_cerr("\n\n"); */
1607 /* faststring errormsg; */
1608 /* errormsg = "An error occurred while reading the input file. It might not be a valid fasta file.\n"; */
1609 /* errormsg += "File position: line "; */
1610 /* errormsg += faststring(infile.line()).c_str(); */
1611 /* ErrorMessage(errormsg.c_str()); */
1612 /* PrintMessage_cerr("\n"); */
1613 /* flush_cerr(); */
1614 /* return -25; */
1615 /* } */
1616
1617 /* if ( count_seq < global_sequence_from || count_seq > global_sequence_to ) */
1618 /* { */
1619 /* if (false) */
1620 /* { */
1621 /* PrintMessage_cerr("Skipping sequence "); */
1622 /* PrintMessage_cerr(faststring(count_seq).c_str()); */
1623 /* PrintMessage_cerr(": "); */
1624 /* PrintMessage_cerr(seq->getName()); */
1625 /* PrintMessage_cerr("\n"); */
1626 /* flush_cerr(); */
1627 /* } */
1628 /* continue; */
1629 /* } */
1630
1631 /* PrintMessage_cerr("Processing sequence "); */
1632 /* PrintMessage_cerr(faststring(count_seq).c_str()); */
1633 /* PrintMessage_cerr(": "); */
1634 /* PrintMessage_cerr(seq->getName()); */
1635 /* PrintMessage_cerr("\n"); */
1636 /* flush_cerr(); */
1637
1638 /* seqData.push_back(seq); */
1639 /* } // End while */
1640
1641 unsigned j;
1642
1643 for (j=0; j<all_lines.size(); ++j)
1644 delete all_lines[j];
1645
1646 return 0;
1647 } // End read_from_Phylip_File
1648
1649 // Backwards compatible and convenience function ExportSequences with fewer parameters.
1650 void ExportSequences(std::ostream &os, char format, unsigned interleaved_len)
1651 {
1652 faststring tmp;
1653 ExportSequences(os, format, interleaved_len, tmp, UINT_MAX, true);
1654 }
1655
1656 // Normal export to different formats:
1657 void ExportSequences(std::ostream &os, char format, unsigned interleaved_len, faststring &replace_symbols_in_sequence_names, unsigned trim_seq_names_length, bool unique_names)
1658 {
1659 if (taxaNum == 0)
1660 return;
1661
1662 // vector of sequences with gaps and stars.
1663 // Why do we need a vector here?? 9.9.2012
1664 std::vector<faststring> vofs;
1665
1666 unsigned i;
1667
1668 std::vector<faststring> sequence_names;
1669
1670 for (i=0; i< taxaNum; ++i)
1671 {
1672 vofs.push_back(faststring('\0', (size_t)100));
1673 seqData[i]->getSequence_fill_in_gaps_and_stars(vofs[i]);
1674 sequence_names.push_back(seqData[i]->getFullName());
1675 }
1676
1677 // if format is strict phylip, set trim_seq_names_length to 10.
1678 if (format == 'p')
1679 {
1680 unique_names = true;
1681 trim_seq_names_length = 10;
1682 }
1683
1684 if (format == 'r')
1685 {
1686 bool space_in_query = false;;
1687 faststring::size_t j;
1688
1689 for (j=0; j<replace_symbols_in_sequence_names.size(); j+=2)
1690 {
1691 if (replace_symbols_in_sequence_names[j] == ' ')
1692 space_in_query = true;
1693 if (replace_symbols_in_sequence_names[j+1] == ' ') // This target is not allowed.
1694 replace_symbols_in_sequence_names[j+1] = '_';
1695 }
1696 if (!space_in_query) // We append a replacement for ' '.
1697 replace_symbols_in_sequence_names += " _";
1698 }
1699
1700 if ( !replace_symbols_in_sequence_names.empty() )
1701 {
1702 vector_of_faststring_replace_characters(sequence_names, replace_symbols_in_sequence_names, '>');
1703 }
1704
1705 if (trim_seq_names_length < UINT_MAX)
1706 {
1707 vector_of_faststring_shorten_all(sequence_names, trim_seq_names_length);
1708 }
1709
1710 vector_of_faststring_trimSpaces_front_back(sequence_names);
1711
1712 if (unique_names)
1713 {
1714 vector_of_faststring_unique(sequence_names, trim_seq_names_length);
1715 }
1716
1717 if (format=='r') // relaxed phylip
1718 {
1719 unsigned pos=0;
1720 unsigned i;
1721
1722 os << "\t" << taxaNum << "\t" << posNum << std::endl;
1723
1724 // write first block with sequence names:
1725 if (pos < posNum)
1726 {
1727 for (i=0; i<taxaNum; ++i)
1728 {
1729 os << sequence_names[i] << " ";
1730 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1731 }
1732 os << std::endl; // Separate blocks
1733 pos += interleaved_len;
1734 }
1735
1736 while (pos < posNum)
1737 {
1738 for (i=0; i<taxaNum; ++i)
1739 {
1740 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1741 }
1742 os << std::endl; // Separate blocks
1743 pos += interleaved_len;
1744 }
1745 }
1746 else
1747 if (format=='p') // Phylip
1748 {
1749 unsigned pos=0;
1750 unsigned i;
1751
1752 for (i=0; i<taxaNum; ++i)
1753 {
1754 sequence_names[i].fill_if_shorter(10, ' ');
1755 }
1756
1757 os << "\t" << taxaNum << "\t" << posNum << std::endl;
1758
1759 // write first block with sequence names:
1760 if (pos < posNum)
1761 {
1762 for (i=0; i<taxaNum; ++i)
1763 {
1764 os << sequence_names[i] << " ";
1765 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1766 }
1767 os << std::endl; // Separate blocks
1768 pos += interleaved_len;
1769 }
1770
1771 while (pos < posNum)
1772 {
1773 for (i=0; i<taxaNum; ++i)
1774 {
1775 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1776 }
1777 os << std::endl; // Separate blocks
1778 pos += interleaved_len;
1779 }
1780 }
1781 else if (format=='f')
1782 {
1783 unsigned pos=0;
1784 unsigned i;
1785
1786 for (i=0; i<taxaNum; ++i)
1787 {
1788 os << ">" << sequence_names[i] << std::endl;
1789 pos = 0;
1790 while (pos < posNum)
1791 {
1792 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1793 pos += interleaved_len;
1794 }
1795 }
1796 }
1797 else if (format=='n')
1798 {
1799 /* Begin data; */
1800 /* Dimensions ntax=4 nchar=15; */
1801 /* Format datatype=dna symbols="ACTG" missing=? gap=-; */
1802 /* Matrix */
1803 /* Species1 atgctagctagctcg */
1804 /* Species2 atgcta??tag-tag */
1805 /* Species3 atgttagctag-tgg */
1806 /* Species4 atgttagctag-tag */
1807 /* ; */
1808 /* End; */
1809
1810 os << "Begin data;" << std::endl;
1811 os << "Dimensions ntax="<< taxaNum << " nchar="<< posNum << ";" << std::endl;
1812 os << "Format datatype="<< seqData[0]->type_as_string()
1813 // << " symbols=\" "<< << "\""
1814 << " missing=" << ambig_char << " gap=-;" << std::endl;
1815 os << "matrix" << std::endl;
1816
1817 unsigned pos=0;
1818 unsigned i;
1819
1820 while (pos < posNum)
1821 {
1822 for (i=0; i<taxaNum; ++i)
1823 {
1824 os << "'" << sequence_names[i] << "'" << " ";
1825 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1826 }
1827 pos += interleaved_len;
1828 }
1829 os << ";" << std::endl << "end;" << std::endl;
1830
1831 }
1832 else if (format == 'N') // Nexus format with taxa and characters block:
1833 {
1834 unsigned pos;
1835 unsigned i;
1836
1837 os << "Begin taxa;" << std::endl;
1838 os << "Dimensions ntax="<< taxaNum << ";" << std::endl;
1839 os << "TAXLABELS ";
1840
1841 for (i=0; i<taxaNum-1; ++i)
1842 {
1843 os << "'" << sequence_names[i] << "'" << " ";
1844 }
1845 os << "'" << sequence_names[i] << "'" << ";" << std::endl << "end;" << std::endl;
1846 os << std::endl;
1847
1848 os << "Begin characters;" << std::endl;
1849 os << "Dimensions ntax="<< taxaNum << " nchar="<< posNum << ";" << std::endl;
1850 os << "Format datatype="<< seqData[0]->type_as_string()
1851 // << " symbols=\" "<< << "\""
1852 << " missing=" << ambig_char << " gap=-;" << std::endl;
1853 os << "matrix" << std::endl;
1854
1855 pos=0;
1856 while (pos < posNum)
1857 {
1858 for (i=0; i<taxaNum; ++i)
1859 {
1860 os << "'" << sequence_names[i] << "'" << " ";
1861 os << vofs[i].substr(pos, interleaved_len) << std::endl;
1862 }
1863 pos += interleaved_len;
1864 }
1865 os << ";" << std::endl << "end;" << std::endl;
1866 } // END format == 'N'
1867 else
1868 {
1869 std::cerr << "Internal error in ExportSequences(std::ostream, char, unsigned):\n"
1870 "Unknown value for format parameter. No output has been generated."
1871 << std::endl;
1872 }
1873 }
1874
1875 // Export do different formats with site-filter
1876 // Commented out since not finished and not tested.
1877 /* void ExportSequences(std::ostream &os, char format, unsigned interleaved_len, */
1878 /* std::vector<unsigned> site_filter) */
1879 /* { */
1880 /* // TODO: Currently only supports fasta without interleaved_len */
1881
1882 /* if (taxaNum == 0) */
1883 /* return; */
1884
1885 /* // vector of sequences with gaps and stars. */
1886 /* // Why do we need a vector here?? 9.9.2912 */
1887 /* std::vector<faststring> vofs; */
1888
1889 /* unsigned i; */
1890
1891 /* for (i=0; i< taxaNum; ++i) */
1892 /* { */
1893 /* vofs.push_back(faststring('\0', (size_t)10000)); */
1894 /* seqData[i]->getSequence_fill_in_gaps_and_stars(vofs[i]); */
1895 /* } */
1896
1897 /* if (format=='p') // Phylip */
1898 /* { */
1899 /* /\* std::vector<faststring> uphynames; *\/ */
1900 /* /\* unique_maxlen_names(uphynames); *\/ */
1901
1902 /* /\* unsigned pos=0; *\/ */
1903 /* /\* unsigned i; *\/ */
1904
1905 /* /\* os << "\t" << taxaNum << "\t" << posNum << std::endl; *\/ */
1906
1907 /* /\* while (pos < posNum) *\/ */
1908 /* /\* { *\/ */
1909 /* /\* for (i=0; i<taxaNum; ++i) *\/ */
1910 /* /\* { *\/ */
1911 /* /\* os << uphynames[i] << " "; *\/ */
1912 /* /\* os << vofs[i].substr(pos, interleaved_len) << std::endl; *\/ */
1913 /* /\* } *\/ */
1914 /* /\* os << std::endl; *\/ */
1915 /* /\* pos += interleaved_len; *\/ */
1916 /* /\* } *\/ */
1917 /* } */
1918 /* else if (format=='f') */
1919 /* { */
1920 /* unsigned pos=0; */
1921 /* unsigned i; */
1922
1923 /* for (i=0; i<taxaNum; ++i) */
1924 /* { */
1925 /* os << ">" << seqData[i]->getFullName() << std::endl; */
1926 /* pos = 0; */
1927 /* faststring &seq_ref = vofs[i]; */
1928 /* while (pos < posNum) */
1929 /* { */
1930 /* if (site_filter[pos] != 0) */
1931 /* os << seq_ref[pos] << std::endl; */
1932 /* ++pos; */
1933 /* } */
1934 /* } */
1935 /* } */
1936 /* else if (format=='n') */
1937 /* { */
1938 /* /\* Begin data; *\/ */
1939 /* /\* Dimensions ntax=4 nchar=15; *\/ */
1940 /* /\* Format datatype=dna symbols="ACTG" missing=? gap=-; *\/ */
1941 /* /\* Matrix *\/ */
1942 /* /\* Species1 atgctagctagctcg *\/ */
1943 /* /\* Species2 atgcta??tag-tag *\/ */
1944 /* /\* Species3 atgttagctag-tgg *\/ */
1945 /* /\* Species4 atgttagctag-tag *\/ */
1946 /* /\* ; *\/ */
1947 /* /\* End; *\/ */
1948
1949 /* /\* os << "Begin data;" << std::endl; *\/ */
1950 /* /\* os << "Dimensions ntax="<< taxaNum << " nchar="<< posNum << ";" << std::endl; *\/ */
1951 /* /\* os << "Format datatype="<< seqData[0]->type_as_string() *\/ */
1952 /* /\* // << " symbols=\" "<< << "\"" *\/ */
1953 /* /\* << " missing=" << ambig_char << " gap=-;" << std::endl; *\/ */
1954 /* /\* os << "matrix" << std::endl; *\/ */
1955
1956 /* /\* unsigned pos=0; *\/ */
1957 /* /\* unsigned i; *\/ */
1958
1959 /* /\* while (pos < posNum) *\/ */
1960 /* /\* { *\/ */
1961 /* /\* for (i=0; i<taxaNum; ++i) *\/ */
1962 /* /\* { *\/ */
1963 /* /\* os << "'" << seqData[i]->getName() << "'" << " "; *\/ */
1964 /* /\* os << vofs[i].substr(pos, interleaved_len) << std::endl; *\/ */
1965 /* /\* } *\/ */
1966 /* /\* pos += interleaved_len; *\/ */
1967 /* /\* } *\/ */
1968 /* /\* os << ";" << std::endl << "end;" << std::endl; *\/ */
1969
1970 /* } */
1971
1972 /* } */
1973
1974
1975 void ExportSequences_no_fill_in_ext_phylip_range(std::ostream &os, unsigned begin_exp, unsigned end_exp)
1976 {
1977 if (taxaNum == 0)
1978 return;
1979
1980 unsigned i;
1981 unsigned len;
1982
1983 os << "\t" << taxaNum << "\t" << end_exp-begin_exp << std::endl;
1984
1985 for (i=0; i<taxaNum; ++i)
1986 {
1987 len = end_exp-begin_exp;
1988 if (len > seqData[i]->length() )
1989 len = seqData[i]->length();
1990 os.write(seqData[i]->getName(), seqData[i]->getName_faststring().length());
1991 os.put(' ');
1992 os.write(seqData[i]->getSeqBegin()+begin_exp, len);
1993 os.put('\n');
1994 }
1995 }
1996
1997 // Needs to be revised:
1998 /*
1999 void ExportSequences_no_fill_in_ext_phylip_range(std::ostream &os, unsigned *coords, unsigned num_coord_pairs)
2000 {
2001 if (taxaNum == 0)
2002 return;
2003
2004 // if (end_exp > posNum || end_exp <= begin_exp)
2005 // return;
2006
2007 unsigned i,j, N=0;
2008 unsigned begin_exp;
2009 unsigned end_exp;
2010
2011
2012 for (j=0; j<num_coord_pairs; ++j)
2013 {
2014 begin_exp = coords[2*j];
2015 end_exp = coords[2*j+1];
2016 if (end_exp > posNum)
2017 end_exp = posNum;
2018 if (begin_exp < end_exp)
2019 N += end_exp-begin_exp;
2020 }
2021
2022 os << "\t" << taxaNum << "\t" << N << std::endl;
2023
2024 for (i=0; i<taxaNum; ++i)
2025 {
2026 os.write(seqData[i]->getName(), seqData[i]->getName_faststring().length());
2027 os.put(' ');
2028 for (j=0; j<num_coord_pairs; ++j)
2029 {
2030 begin_exp = coords[2*j];
2031 end_exp = coords[2*j+1];
2032 if (end_exp > posNum)
2033 end_exp = posNum;
2034 if (begin_exp < end_exp)
2035 os.write(seqData[i]->getSeqBegin()+begin_exp, end_exp-begin_exp);
2036 }
2037 os.put('\n');
2038 }
2039 }
2040 */
2041
2042
2043 // Not yet well tested!!!!!
2044 /*
2045 void Export_Single_Sequence(std::ostream &os, const faststring& fullname,
2046 char format, unsigned interleaved_len)
2047 {
2048 if (taxaNum == 0)
2049 return;
2050
2051 vector of sequences with gaps and stars.
2052 Why do we need a vector here?? 9.9.2912
2053 std::vector<faststring> vofs;
2054
2055 unsigned i;
2056
2057 for (i=0; i< taxaNum; ++i)
2058 {
2059 vofs.push_back(faststring());
2060 if ( seqData[i]->getFullName() == fullname)
2061 seqData[i]->getSequence_fill_in_gaps_and_stars(vofs[i]);
2062 }
2063
2064 if (format=='p') Phylip
2065 {
2066 std::vector<faststring> uphynames;
2067 unique_maxlen_names(uphynames);
2068
2069 unsigned pos=0;
2070 unsigned i;
2071
2072 for (i=0; i<taxaNum; ++i)
2073 uphynames[i].fill_if_shorter(10, ' ');
2074
2075 os << "\t" << taxaNum << "\t" << posNum << std::endl;
2076
2077 while (pos < posNum)
2078 {
2079 for (i=0; i<taxaNum; ++i)
2080 {
2081 if (!vofs[i].empty())
2082 {
2083 os << uphynames[i] << " ";
2084 os << vofs[i].substr(pos, interleaved_len) << std::endl;
2085 }
2086 }
2087 os << std::endl;
2088 pos += interleaved_len;
2089 }
2090 }
2091 else if (format=='f')
2092 {
2093 unsigned pos=0;
2094 unsigned i;
2095
2096 for (i=0; i<taxaNum; ++i)
2097 {
2098 if (!vofs[i].empty())
2099 {
2100 os << ">" << seqData[i]->getFullName() << std::endl;
2101 pos = 0;
2102 while (pos < posNum)
2103 {
2104 os << vofs[i].substr(pos, interleaved_len) << std::endl;
2105 pos += interleaved_len;
2106 }
2107 }
2108 }
2109 }
2110 else if (format=='n')
2111 {
2112 Begin data;
2113 Dimensions ntax=4 nchar=15;
2114 Format datatype=dna symbols="ACTG" missing=? gap=-;
2115 Matrix
2116 Species1 atgctagctagctcg
2117 Species2 atgcta??tag-tag
2118 Species3 atgttagctag-tgg
2119 Species4 atgttagctag-tag
2120 ;
2121 End;
2122
2123 os << "Begin data;" << std::endl;
2124 os << "Dimensions ntax="<< 1 << " nchar="<< posNum << ";" << std::endl;
2125 os << "Format datatype="<< seqData[0]->type_as_string()
2126 << " symbols=\" "<< << "\""
2127 << " missing=" << ambig_char << " gap=-;" << std::endl;
2128 os << "matrix" << std::endl;
2129
2130 unsigned pos=0;
2131 unsigned i;
2132
2133 while (pos < posNum)
2134 {
2135 for (i=0; i<taxaNum; ++i)
2136 {
2137 if (!vofs[i].empty())
2138 {
2139 os << seqData[i]->getName() << " ";
2140 os << vofs[i].substr(pos, interleaved_len) << std::endl;
2141 }
2142 }
2143 pos += interleaved_len;
2144 }
2145 os << ";" << std::endl << "end;" << std::endl;
2146
2147 }
2148
2149
2150 }
2151
2152 */
2153
2154
2155
2156 // void GetBaseFrequencies(unsigned, std::vector<unsigned>);
2157
2158 // void initSplits();
2159 // void computeSplits();
2160 // CSplits *splits;
2161 // CBasefreq *basefreq;
2162
2163 double compute_site_pattern_stat(bool filter_gap_abmig_symbols=true)
2164 {
2165 unsigned i, j;
2166
2167 // Here we will store pointers to all sequences for fast access:
2168 const char **tax = new const char* [taxaNum];
2169
2170 if (taxaNum == 0 || posNum == 0)
2171 return 0;
2172
2173 // Store pointers to all sequences in the tax array - this will be faster
2174 for (j=0; j < taxaNum; ++j)
2175 {
2176 tax[j] = seqData[j]->getSeqStr();
2177 }
2178
2179 faststring tmp;
2180 std::map<faststring, unsigned> m;
2181
2182 bool contains_gap_ambig;
2183 char c;
2184
2185 // For all positions in alignment
2186 for (i=0; i<posNum; ++i)
2187 {
2188 tmp.clear();
2189 contains_gap_ambig = false;
2190
2191 // Old and slow version:
2192 // Copy all symbols to site pattern vector
2193 /* for (j=0; j < taxaNum; ++j) */
2194 /* { */
2195 /* c = tax[j][i]; */
2196 /* if (filter_gap_abmig_symbols) */
2197 /* { */
2198 /* // Check whether this is a position we do not want to consider. */
2199 /* if (datatype == CSequence_Mol::dna && (is_DNA_ambig(c) || c == '-') ) */
2200 /* { */
2201 /* contains_gap_ambig = true; */
2202 /* } */
2203 /* else */
2204 /* { */
2205 /* if (datatype == CSequence_Mol::protein && (is_aa_ambig(c) || c == '-') ) */
2206 /* { */
2207 /* contains_gap_ambig = true; */
2208 /* } */
2209 /* } */
2210 /* } // END if (filter_gap_abmig_symbols) */
2211 /* tmp.push_back(c); */
2212 /* } // END: For all taxa */
2213
2214 // Faster version:
2215 if (filter_gap_abmig_symbols && datatype == CSequence_Mol::dna)
2216 {
2217 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2218 {
2219 c = tax[j][i];
2220 if (is_DNA_ambig(c) || c == '-')
2221 {
2222 contains_gap_ambig = true;
2223 }
2224 tmp.push_back(c);
2225 }
2226 }
2227 else if (filter_gap_abmig_symbols && datatype == CSequence_Mol::protein)
2228 {
2229 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2230 {
2231 c = tax[j][i];
2232 if (is_aa_ambig(c) || c == '-')
2233 {
2234 contains_gap_ambig = true;
2235 }
2236 tmp.push_back(c);
2237 }
2238 }
2239 else
2240 {
2241 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2242 {
2243 c = tax[j][i];
2244 tmp.push_back(c);
2245 }
2246 }
2247 if (!contains_gap_ambig)
2248 add_or_count(m, tmp);
2249 } // END: for all positions in alignment
2250
2251 std::map<faststring, unsigned>::iterator it, it_end;
2252 it = m.begin();
2253 it_end = m.end();
2254
2255 double res=0;
2256 double x;
2257
2258 // Formula from "Statistical Tests of Models of DNA Substitution", Journal of Molecular Evolution, Springer-Verlag NewYork Inc. 1993
2259 // Nick Goldman
2260 // Formula: \sum N_i*ln(N_i) - N*ln(N), where N_i are the pattern frequencies and N is the total number of sites.
2261
2262 while (it != it_end)
2263 {
2264 x = it->second;
2265 if (x > 0)
2266 res += x*log(x);
2267 // std::cout << x << " " << res << std::endl;
2268 ++it;
2269 }
2270 delete [] tax;
2271
2272 x = posNum;
2273 res -= x*log(x);
2274 // std::cout << x << " " << res << std::endl;
2275
2276 return res;
2277 } // END compute_site_pattern_stat(bool filter_gap_abmig_symbols=true)
2278
2279
2280 double compute_site_pattern_stat(std::map<faststring, unsigned> &m, bool filter_gap_abmig_symbols=true)
2281 {
2282 unsigned i, j;
2283 m.clear();
2284
2285 // Here we will store pointers to all sequences for fast access:
2286 const char **tax = new const char* [taxaNum];
2287
2288 if (taxaNum == 0 || posNum == 0)
2289 return 0;
2290
2291 // Store pointers to all sequences in the tax array - this will be faster
2292 for (j=0; j < taxaNum; ++j)
2293 {
2294 tax[j] = seqData[j]->getSeqStr();
2295 }
2296
2297 faststring tmp;
2298
2299 bool contains_gap_ambig;
2300 char c;
2301
2302 // For all positions in alignment
2303 for (i=0; i<posNum; ++i)
2304 {
2305 tmp.clear();
2306 contains_gap_ambig = false;
2307
2308 // Old and slow version:
2309 // Copy all symbols to site pattern vector
2310 /* for (j=0; j < taxaNum; ++j) */
2311 /* { */
2312 /* c = tax[j][i]; */
2313 /* if (filter_gap_abmig_symbols) */
2314 /* { */
2315 /* // Check whether this is a position we do not want to consider. */
2316 /* if (datatype == CSequence_Mol::dna && (is_DNA_ambig(c) || c == '-') ) */
2317 /* { */
2318 /* contains_gap_ambig = true; */
2319 /* } */
2320 /* else */
2321 /* { */
2322 /* if (datatype == CSequence_Mol::protein && (is_aa_ambig(c) || c == '-') ) */
2323 /* { */
2324 /* contains_gap_ambig = true; */
2325 /* } */
2326 /* } */
2327 /* } // END if (filter_gap_abmig_symbols) */
2328 /* tmp.push_back(c); */
2329 /* } // END: For all taxa */
2330
2331 // Faster version:
2332 if (filter_gap_abmig_symbols && datatype == CSequence_Mol::dna)
2333 {
2334 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2335 {
2336 c = tax[j][i];
2337 if (is_DNA_ambig(c) || c == '-')
2338 {
2339 contains_gap_ambig = true;
2340 }
2341 tmp.push_back(c);
2342 }
2343 }
2344 else if (filter_gap_abmig_symbols && datatype == CSequence_Mol::protein)
2345 {
2346 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2347 {
2348 c = tax[j][i];
2349 if (is_aa_ambig(c) || c == '-')
2350 {
2351 contains_gap_ambig = true;
2352 }
2353 tmp.push_back(c);
2354 }
2355 }
2356 else
2357 {
2358 for (j=0; j < taxaNum; ++j) // Copy all symbols to site pattern vector
2359 {
2360 c = tax[j][i];
2361 tmp.push_back(c);
2362 }
2363 }
2364 if (!contains_gap_ambig)
2365 add_or_count(m, tmp);
2366 } // END: for all positions in alignment
2367
2368 std::map<faststring, unsigned>::iterator it, it_end;
2369 it = m.begin();
2370 it_end = m.end();
2371
2372 double res=0;
2373 double x;
2374
2375 while (it != it_end)
2376 {
2377 x = it->second;
2378 if (x > 0)
2379 res += x*log(x);
2380 // std::cout << x << " " << res << std::endl;
2381 ++it;
2382 }
2383 delete [] tax;
2384
2385 x = posNum;
2386 res -= x*log(x);
2387 // std::cout << x << " " << res << std::endl;
2388
2389 return res;
2390 }
2391
2392
2393
2394 void get_partial_pattern(unsigned pos, unsigned n, faststring &pat)
2395 {
2396 unsigned i;
2397
2398 if (n > taxaNum)
2399 n = taxaNum;
2400
2401 pat.clear();
2402 for(i=0; i<n; ++i)
2403 pat.push_back((seqData[i]->getSeqStr())[pos]);
2404 }
2405
2406
2407
2408 // Does not yet provide the possibility to remove amig positions.
2409 void get_vector_of_site_pattern_frequencies(fastvector<unsigned> &spf)
2410 {
2411 unsigned i, j;
2412
2413 const char **tax = new const char* [taxaNum];
2414
2415 for (j=0; j < taxaNum; ++j)
2416 {
2417 tax[j] = seqData[j]->getSeqStr();
2418 }
2419
2420 faststring tmp;
2421 std::map<faststring, unsigned> m;
2422
2423 for (i=0; i<posNum; ++i)
2424 {
2425 tmp.clear();
2426
2427 for (j=0; j < taxaNum; ++j)
2428 {
2429 tmp.push_back(tax[j][i]);
2430 }
2431 add_or_count(m, tmp);
2432 }
2433 std::map<faststring, unsigned>::iterator it, it_end;
2434 it = m.begin();
2435 it_end = m.end();
2436
2437 while (it != it_end)
2438 {
2439 spf.push_back(it->second);
2440 ++it;
2441 }
2442 delete [] tax;
2443 }
2444
2445 void clear(CSequence_Mol::DataTypesEnum datatype_param = CSequence_Mol::unknown,
2446 char ambig_char_param = '?')
2447 {
2448 taxaNum = 0;
2449 posNum = 0;
2450 ambig_char = ambig_char_param;
2451 datatype = datatype_param;
2452
2453 originalPosNumbers.clear();
2454 originalPosNumbers_supplied = false;
2455
2456 int i, n=seqData.size();
2457
2458 for (i=0; i<n; ++i)
2459 delete seqData[i];
2460
2461 seqData.clear();
2462 sn_map.clear();
2463 }
2464
2465 void remove_gap_only_sequences()
2466 {
2467 int i, n=seqData.size();
2468
2469 // We do this in reversed order, since this avoids adapting i and n after
2470 // an element has been removed.
2471 for (i=n-1; i>=0; --i)
2472 {
2473 if (seqData[i]->has_only_gaps() )
2474 {
2475 remove_del(i);
2476 }
2477 }
2478 }
2479
2480 void remove_ambig_only_sequences()
2481 {
2482 int i, n = seqData.size();
2483
2484 // We do this in reversed order, since this avoids adapting i and n after
2485 // an element has been removed.
2486 for (i=n-1; i>=0; --i)
2487 {
2488 if (seqData[i]->has_only_ambigs() )
2489 {
2490 remove_del(i);
2491 }
2492 }
2493 }
2494
2495 void remove_gap_or_ambig_only_sequences()
2496 {
2497 int i, n = seqData.size();
2498
2499 // We do this in reversed order, since this avoids adapting i and n after
2500 // an element has been removed.
2501 for (i=n-1; i>=0; --i)
2502 {
2503 // std::cout << "Checking sequence: " << i+1 << std::endl;
2504 if (seqData[i]->has_only_ambigs_or_gap() )
2505 {
2506 remove_del(i);
2507 }
2508 }
2509 }
2510
2511 void steal_sequence(CSequences2 &seqs, unsigned i)
2512 {
2513 if (i < seqs.taxaNum)
2514 {
2515 ++taxaNum;
2516 add_seq(seqs.seqData[i]);
2517 seqs.remove(i);
2518 }
2519 }
2520
2521 void remove_del(unsigned seq_num)
2522 {
2523 CSequence_Mol *p = seqData[seq_num];
2524 faststring sname = p->getName();
2525
2526 --taxaNum;
2527 seqData.erase(seqData.begin()+seq_num);
2528 std::map<faststring, CSequence_Mol*>::iterator find_it = sn_map.find(sname);
2529 if (find_it != sn_map.end() )
2530 sn_map.erase(find_it);
2531 delete p;
2532 }
2533
2534 CSequence_Mol* remove(unsigned seq_num)
2535 {
2536 CSequence_Mol *p = seqData[seq_num];
2537 faststring sname = p->getName();
2538
2539 --taxaNum;
2540 seqData.erase(seqData.begin()+seq_num);
2541 std::map<faststring, CSequence_Mol*>::iterator find_it = sn_map.find(sname);
2542 if (find_it != sn_map.end() )
2543 sn_map.erase(find_it);
2544 return p;
2545 }
2546
2547 void add_seq_to_alignment(CSequence_Mol::DataTypesEnum datatype_param,
2548 const faststring &fullname_param,
2549 const faststring &seq_data_param,
2550 char ambig_param='\0' // default auto
2551 )
2552 {
2553 if (datatype != datatype_param)
2554 {
2555 std::cerr << "Warning: Not all sequences seem to have the same data type.\n";
2556 datatype = CSequence_Mol::mixed;
2557 }
2558
2559 // std::cout << "datatype_param: " << datatype_param << std::endl;
2560
2561 // Handle general ambig TODO XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
2562 // if (general_ambig == CSequence_Mol::unknown)
2563
2564 CSequence_Mol *seq;
2565 seq = new CSequence_Mol (datatype_param, ambig_param);
2566 // std::cout << "Datatype after constructor: " << seq->get_datatype() << std::endl;
2567 seq->set_taxon_and_sequence(fullname_param, seq_data_param, datatype_param);
2568 // std::cout << "Datatype after constructor+set_taxon_and_sequence: " << seq->get_datatype() << std::endl;
2569
2570
2571
2572
2573 ++taxaNum;
2574 if (posNum == 0)
2575 posNum = seq->length();
2576 else if (posNum != seq->length())
2577 {
2578 std::cerr << "Error: Sequence added has different length than existing sequences." << std::endl;
2579 delete seq;
2580 return;
2581 }
2582
2583 add_seq(seq);
2584
2585 // Further auto detect stuff???????
2586 }
2587
2588 void vectors_of_site_coverages_and_site_entropies_DNA(std::vector<float> &coverage, std::vector<float> &entropies)
2589 {
2590 int symbols[256];
2591
2592 coverage.clear();
2593 entropies.clear();
2594
2595 unsigned site_index, seq_index;
2596 const char **seq_strs;
2597
2598 seq_strs = new const char* [taxaNum];
2599
2600 for (seq_index=0; seq_index<taxaNum; ++seq_index)
2601 {
2602 seq_strs[seq_index] = get_Seq_Data(seq_index);
2603 }
2604
2605 for (site_index = 0; site_index < posNum; ++site_index)
2606 {
2607 std::memset(symbols, 0, 256*sizeof(int));
2608
2609 for (seq_index = 0; seq_index < taxaNum; ++seq_index)
2610 {
2611 unsigned char c = seq_strs[seq_index][site_index];
2612 c = toupper_lookup[c];
2613 ++symbols[c];
2614 }
2615
2616 int A = symbols[(unsigned char)'A'];
2617 int C = symbols[(unsigned char)'C'];
2618 int G = symbols[(unsigned char)'G'];
2619 int T = symbols[(unsigned char)'T']+symbols[(unsigned char)'U'];
2620 // int gaps = symbols[(int)'-'];
2621 int amb = symbols[(unsigned char)'R']+symbols[(unsigned char)'Y']+symbols[(unsigned char)'S']+symbols[(unsigned char)'W']+symbols[(unsigned char)'K']
2622 +symbols[(unsigned char)'M']+symbols[(unsigned char)'B']+symbols[(unsigned char)'D']+symbols[(unsigned char)'H']+symbols[(unsigned char)'V']+symbols[(unsigned char)'N']+symbols[(unsigned char)'?'];
2623
2624 float all = A+C+G+T;
2625 float a = (float)A/all;
2626 float c = (float)C/all;
2627 float g = (float)G/all;
2628 float t = (float)T/all;
2629
2630 float cov = (all+amb)/taxaNum;
2631 float ent = 0;
2632 if (a>0)
2633 ent -= a*log(a);
2634 if (c>0)
2635 ent -= c*log(c);
2636 if (g>0)
2637 ent -= g*log(g);
2638 if (t>0)
2639 ent -= t*log(t);
2640
2641 coverage.push_back(cov);
2642 entropies.push_back(ent);
2643 }
2644
2645 delete [] seq_strs;
2646 }
2647
2648
2649 void alignment_without_gap_N_positions(CSequences2 &seqs)
2650 {
2651 seqs.clear(datatype, seqs.ambig_char);
2652
2653 std::vector<bool> gap_N_positions(posNum, false);
2654
2655 size_t i, j;
2656 const char *the_seq;
2657 char c;
2658
2659 if (datatype == CSequence_Mol::dna)
2660 {
2661 for (i=0; i< taxaNum; ++i)
2662 {
2663 the_seq = seqData[i]->getSeqStr();
2664 for(j=0; j<posNum; ++j)
2665 {
2666 c = the_seq[j];
2667 if (is_DNA_ambig(c) || c == '-')
2668 {
2669 gap_N_positions[j] = true;
2670 }
2671 }
2672 }
2673 }
2674
2675 if (datatype == CSequence_Mol::protein)
2676 {
2677 for (i=0; i< taxaNum; ++i)
2678 {
2679 the_seq = seqData[i]->getSeqStr();
2680 for(j=0; j<posNum; ++j)
2681 {
2682 c = the_seq[j];
2683 if (is_aa_ambig(c) || c == '-')
2684 {
2685 gap_N_positions[j] = true;
2686 }
2687 }
2688 }
2689 }
2690
2691 faststring new_seq;
2692
2693 for (i=0; i< taxaNum; ++i)
2694 {
2695 new_seq.clear();
2696 the_seq = seqData[i]->getSeqStr();
2697
2698 for(j=0; j<posNum; ++j)
2699 {
2700 if (!gap_N_positions[j])
2701 new_seq.push_back(the_seq[j]);
2702 }
2703 seqs.add_seq_to_alignment(datatype, seqData[i]->getFullName(), new_seq, seqData[i]->get_ambiguity_character() );
2704 }
2705 }
2706
2707
2708 void alignment_without_gap_only_positions(CSequences2 &seqs)
2709 {
2710 // std::cout << "Entering alignment_without_gap_only_positions" << std::endl;
2711
2712 seqs.clear(datatype, ambig_char);
2713
2714 // Count the number of gaps at all positions.
2715 // Gap only positions are those that have taxaNum gaps.
2716 std::vector<unsigned> gap_positions(posNum, 0);
2717
2718 size_t i, j;
2719 const char *the_seq;
2720 char c;
2721
2722 for (i=0; i< taxaNum; ++i)
2723 {
2724 the_seq = seqData[i]->getSeqStr();
2725 for(j=0; j<posNum; ++j)
2726 {
2727 c = the_seq[j];
2728 if (c == '-')
2729 {
2730 ++gap_positions[j];
2731 }
2732 }
2733 }
2734
2735 faststring new_seq_str;
2736
2737 for (i=0; i< taxaNum; ++i)
2738 {
2739 new_seq_str.clear();
2740 the_seq = seqData[i]->getSeqStr();
2741
2742 for(j=0; j<posNum; ++j)
2743 {
2744 if (gap_positions[j] != taxaNum) // only gaps
2745 new_seq_str.push_back(the_seq[j]);
2746 }
2747 seqs.add_seq_to_alignment(datatype,seqData[i]->getFullName(),new_seq_str,
2748 seqData[i]->get_ambiguity_character());
2749 }
2750 /* std::cout << "DEBUGOUT-alignment_without_gap_only_positions" << std::endl; */
2751 /* seqs.print_DEBUG(std::cout,3); */
2752 }
2753
2754
2755 void replace_sequence_interval(const CSequences2 &s, faststring::size_t pos1=0, faststring::size_t pos2=faststring::npos)
2756 {
2757 determine_map_of_sequence_names();
2758
2759 faststring name;
2760 unsigned i, N = s.seqData.size();
2761 std::map<faststring, CSequence_Mol*>::iterator find_it;
2762
2763 if (taxaNum != s.taxaNum)
2764 {
2765 std::cerr << "Critical error in replace_sequence_interval: Number of taxa are not equal"
2766 << std::endl;
2767 exit(-1);
2768 }
2769
2770 for (i=0; i<N; ++i)
2771 {
2772 name = s.seqData[i]->getName();
2773 find_it = sn_map.find(name);
2774 if (find_it == sn_map.end())
2775 {
2776 std::cerr << "Critical error in replace_sequence_interval: Sequence "
2777 << name << " does not exist." << std::endl;
2778 exit(-1);
2779 }
2780 find_it->second->replace_part_of_sequence(*(s.seqData[i]), pos1, pos2);
2781 }
2782 if (seqData.size() > 0)
2783 posNum = seqData[0]->length();
2784 }
2785
2786 void append_to_sequences(const CSequences2 &s)
2787 {
2788 determine_map_of_sequence_names();
2789
2790 faststring name;
2791 unsigned i,N=s.seqData.size();
2792 std::map<faststring, CSequence_Mol*>::iterator find_it;
2793
2794 if (taxaNum != s.taxaNum)
2795 {
2796 std::cerr << "Critical error in append_sequences: Number of taxa are not equal"
2797 << std::endl;
2798 exit(-1);
2799 }
2800
2801 for (i=0; i<N; ++i)
2802 {
2803 name = s.seqData[i]->getName();
2804 find_it = sn_map.find(name);
2805 if (find_it == sn_map.end())
2806 {
2807 std::cerr << "Critical error in append_sequences: Sequence "
2808 << name << " does not exist." << std::endl;
2809 exit(-1);
2810 }
2811 find_it->second->append_sequence(*(s.seqData[i]));
2812 }
2813 if (seqData.size() > 0)
2814 posNum = seqData[0]->length();
2815 }
2816
2817 void append_to_sequences(const faststring &site_pattern)
2818 {
2819 unsigned i;
2820
2821 if ( taxaNum != site_pattern.size() )
2822 {
2823 std::cerr << "Error when calling the append_to_sequences method:\n"
2824 "the number of sites in the pattern that shall be\n"
2825 "appended the sequences ofject differs from the\n"
2826 "number of sequences. This pattern will not be appended." << std::endl;
2827 exit(-22);
2828 }
2829 for (i=0; i<taxaNum; ++i)
2830 {
2831 seqData[i]->append_residue_unchecked(site_pattern[i]);
2832 }
2833 ++posNum;
2834 }
2835
2836
2837 bool is_insertion_column(unsigned col_pos)
2838 {
2839 unsigned i_tax;
2840 char c;
2841
2842 for (i_tax=0; i_tax<taxaNum; ++i_tax)
2843 {
2844 c = seqData[i_tax]->get_pos(col_pos);
2845 if (c == '.' || (c >='a' && c <= 'z') )
2846 return true;
2847 }
2848 return false;
2849 }
2850
2851
2852 bool is_mainly_gap_pos(unsigned col_pos, double min_prop)
2853 {
2854 unsigned i_tax;
2855 char c;
2856 unsigned count_gap= 0;
2857
2858 for (i_tax=0; i_tax<taxaNum; ++i_tax)
2859 {
2860 c = seqData[i_tax]->get_pos(col_pos);
2861 if (c == '-' || c == '.')
2862 ++count_gap;
2863 }
2864 if ((float)count_gap/taxaNum >= min_prop)
2865 return true;
2866 else
2867 return false;
2868 }
2869
2870
2871 // Assumes that insertion positions have lower case characters
2872 // and they could have dots '.' instead of gaps.
2873 // The letter is not necessary, since insertion positions should
2874 // at least have one lower case character.
2875 // So dots could have been replaced by gaps already.
2876 unsigned get_next_insertion_column(unsigned col_pos)
2877 {
2878 for (; col_pos < posNum; ++col_pos)
2879 if (is_insertion_column(col_pos))
2880 return col_pos;
2881 return col_pos;
2882 }
2883
2884 unsigned get_next_insertion_or_mainly_gap_column(unsigned col_pos, float min_gap_prop)
2885 {
2886 for (; col_pos < posNum; ++col_pos)
2887 if (is_insertion_column(col_pos) || is_mainly_gap_pos(col_pos, min_gap_prop))
2888 return col_pos;
2889 return col_pos;
2890 }
2891
2892 // Assumes that non insertion positions have upper case characters.
2893 // If dots have already been converted to gaps, they are not
2894 // indicative of non insertion positions!!
2895 unsigned get_next_non_insertion_column(unsigned col_pos)
2896 {
2897 for (; col_pos < posNum; ++col_pos)
2898 if (!is_insertion_column(col_pos))
2899 return col_pos;
2900 // if (c == '.' || c >='a' && c <= 'z') // Not a non-insertion column
2901 return col_pos;
2902 }
2903
2904 unsigned get_next_non_insertion_and_non_mainly_gap_column(unsigned col_pos, float min_gap_prop)
2905 {
2906 for (; col_pos < posNum; ++col_pos)
2907 if (!(is_insertion_column(col_pos) || is_mainly_gap_pos(col_pos, min_gap_prop)) )
2908 return col_pos;
2909 // if (c == '.' || c >='a' && c <= 'z') // Not a non-insertion column
2910 return col_pos;
2911 }
2912
2913 // RETURN VALUE NEEDS TO BE SET. DO NOT USE IN THIS FORM.
2914 /* void get_bp_entropies_nucleotide(double *ent) */
2915 /* { */
2916 /* const char **tax = new const char* [taxaNum]; */
2917 /* unsigned j; */
2918
2919 /* if (taxaNum == 0 || posNum == 0) */
2920 /* return; */
2921
2922 /* // Store pointers to all sequences in the tax array - this will be faster */
2923 /* for (j=0; j < taxaNum; ++j) */
2924 /* { */
2925 /* tax[j] = seqData[j]->getSeqStr(); */
2926 /* } */
2927 /* } */
2928
2929 // Computes relative amount of residues that are non gap and non ambig in this range:
2930 double get_non_ambig_non_gap_coverage_in_range(unsigned pos, unsigned pos_end, int flag=0)
2931 {
2932 const char **tax = new const char* [taxaNum];
2933 unsigned i, j;
2934 unsigned N = 0;
2935
2936
2937 if (taxaNum == 0 || posNum == 0)
2938 return -1; // Indicates an error
2939
2940 // Store pointers to all sequences in the tax array - this will be faster
2941 if (flag == 0 || flag == 1) // 1kite all or general mode
2942 {
2943 N = taxaNum;
2944 for (j=0; j < taxaNum; ++j)
2945 {
2946 tax[j] = seqData[j]->getSeqStr();
2947 }
2948 }
2949 else if (flag == 13) // Special 1kite flag: Filter hamstered reference taxa:
2950 {
2951 #ifdef DEBUG
2952 std::cerr << "Called: CSequences2.h:get_non_ambig_non_gap_coverage_in_range with flag==1" << std::endl;
2953 #endif
2954
2955 unsigned jj=0;
2956
2957 for (j=0; j < taxaNum; ++j)
2958 {
2959 // In case we compute coverage values, we only have hamstered reference taxa left in 1kite:
2960 if (is_1kite_hamstered_reference_seq_id(seqData[j]->getFullName() ) )
2961 {
2962 tax[jj] = seqData[j]->getSeqStr();
2963 ++jj;
2964 }
2965 }
2966 N = jj;
2967 }
2968 else
2969 {
2970 return -1; // Indicates an error
2971 }
2972
2973
2974 unsigned count_all=0;
2975 unsigned count_non_ambig_non_gap=0;
2976 double res;
2977 char c;
2978
2979 if (datatype == CSequence_Mol::protein)
2980 {
2981 for (i =pos; i< pos_end && i < posNum; ++i)
2982 {
2983 for (j=0; j< N; ++j)
2984 {
2985 c = tax[j][i];
2986 ++count_all;
2987 if ( !(is_aa_ambig(c) || c == '-') )
2988 ++count_non_ambig_non_gap;
2989 }
2990 }
2991 }
2992 else if (datatype == CSequence_Mol::dna)
2993 {
2994 for (i =pos; i< pos_end && i < posNum; ++i)
2995 {
2996 for (j=0; j< taxaNum; ++j)
2997 {
2998 c = tax[j][i];
2999 ++count_all;
3000 if ( !(is_DNA_ambig(c) || c == '-' ) )
3001 ++count_non_ambig_non_gap;
3002 }
3003 }
3004 }
3005 res = count_non_ambig_non_gap;
3006 res /= count_all;
3007
3008 // std::cerr << count_non_ambig_non_gap << std::endl;
3009 // std::cerr << count_all << std::endl;
3010
3011 return res;
3012 }
3013
3014
3015
3016 void get_1kite_original_reference_taxa_vec(std::vector<faststring> &vec) const
3017 {
3018 #ifdef DEBUG
3019 std::cerr << "Called: CSequences2.h:get_1kite_original_reference_taxa_vec" << std::endl;
3020 #endif
3021 unsigned i;
3022
3023 for (i=0; i < taxaNum; ++i)
3024 {
3025 if ( is_1kite_hamstered_reference_seq_id( seqData[i]->getFullName() ) )
3026 {
3027 vec.push_back(seqData[i]->getFullName() );
3028 }
3029 }
3030 }
3031
3032 // Determines all 1kite original reference taxa, sorts them and moves them to the top of the alignment.
3033 int move_1kite_original_reference_taxa_sorted_to_top()
3034 {
3035 #ifdef DEBUG
3036 std::cerr << "Called: CSequences2.h:move_1kite_original_reference_taxa_sorted_to_top" << std::endl;
3037 #endif
3038
3039 std::vector<faststring> vec;
3040 get_1kite_original_reference_taxa_vec(vec);
3041 std::sort(vec.begin(), vec.end());
3042
3043 int i;
3044
3045 for (i=vec.size()-1; i>= 0; --i)
3046 {
3047 reorder_move_seq_to_top(vec[i]);
3048 }
3049 return vec.size();
3050 }
3051
3052
3053 /* int move_1kite_core_of_other_seqs_to_top(const CSequences2 &other_seqs) */
3054 /* { */
3055 /* #ifdef DEBUG */
3056 /* std::cerr << "Called: CSequences2.h:move_1kite_core_of_other_seqs_to_top" << std::endl; */
3057 /* #endif */
3058
3059 /* std::vector<faststring> vec; */
3060
3061 /* other_seqs.get_1kite_cores_vec(vec); */
3062
3063 /* int i; */
3064
3065 /* for (i=vec.size()-1; i>= 0; --i) */
3066 /* { */
3067 /* reorder_move_seq_to_top(vec[i]); */
3068 /* } */
3069 /* return vec.size(); */
3070 /* } */
3071
3072
3073
3074 // Currently only implemented for datatype DNA
3075 // Allowed flag values:
3076 // 0: normal mode
3077 // 1: Gap regions always get a distance of -3
3078 // 2: Compute gap distance, i.e. count gap versus non-gap nucleotides.
3079 // The result is in the range from 0..1.
3080 // Ns are treated as mismatch. If this is not desired, use the other overwrite of this function below.
3081
3082
3083 double sequence_distance(unsigned s1, unsigned s2, unsigned begin_range, unsigned end_range, unsigned flag=0)
3084 {
3085 if (s1 >= taxaNum || s2 >= taxaNum)
3086 return -1;
3087
3088 CSequence_Mol* seq1 = seqData[s1];
3089 CSequence_Mol* seq2 = seqData[s2];
3090
3091 return sequence_distance(seq1, seq2, begin_range, end_range, flag=0);
3092 }
3093
3094
3095
3096 double sequence_distance(CSequence_Mol* seq1, CSequence_Mol* seq2, unsigned begin_range, unsigned end_range, unsigned flag=0)
3097 {
3098 char c1, c2;
3099
3100 // Do some range checks:
3101 if (end_range < begin_range) // This is considered a major error and the caller should correct this problem.
3102 {
3103 std::cerr << "Error in sequence_distance: end_range < begin_range" << std::endl;
3104 exit(-33);
3105 }
3106
3107 // Out of range checks are corrected silently.
3108 // It is not clear this is always the best method to deal with this.
3109 if ((end_range > seq1->length()))
3110 {
3111 end_range = seq1->length();
3112 if (begin_range > seq1->length())
3113 begin_range = seq1->length();
3114 }
3115 if ((end_range > seq2->length()))
3116 {
3117 end_range = seq2->length();
3118 if (begin_range > seq2->length())
3119 begin_range = seq2->length();
3120 }
3121
3122 unsigned i = begin_range;
3123
3124 unsigned len = 0;
3125 unsigned diff = 0;
3126
3127 if (flag < 2)
3128 {
3129 if (seq1->get_datatype() != CSequence_Mol::dna)
3130 return -2;
3131
3132 while (i != end_range)
3133 {
3134 // TODO: DO WE NEED TOUPPER??
3135 c1 = toupper(seq1->get_pos(i));
3136 c2 = toupper(seq2->get_pos(i));
3137
3138 if (c1 != '-' && c2 != '-')
3139 {
3140 ++len;
3141 if (c1 != c2 || c1 == 'N') // If they differ or if both are Ns we count this as a difference.
3142 {
3143 ++diff;
3144 }
3145 }
3146 else
3147 {
3148 if (flag == 1)
3149 return -3.0;
3150 }
3151 ++i;
3152 }
3153 if (len == 0)
3154 {
3155 diff = 2;
3156 len = 1;
3157 }
3158 return (double)diff / (double)len;
3159 }
3160 else if (flag == 2)
3161 {
3162 // len = end_range - begin_range;
3163
3164 while (i != end_range)
3165 {
3166 // TODO: DO WE NEED TOUPPER??
3167 c1 = toupper(seq1->get_pos(i));
3168 c2 = toupper(seq2->get_pos(i));
3169
3170 // We only count differences in the gap structur: Non-gap versus gap.
3171 if ( (c1 == '-' && c2 != '-') || (c1 != '-' && c2 == '-') )
3172 {
3173 ++diff;
3174 }
3175 ++i;
3176 }
3177 return diff;
3178 }
3179 else
3180 {
3181 std::cerr << "Flag value undefined in CSequences2:sequence_distance(..);" << std::endl;
3182 exit(-127);
3183 }
3184 }
3185
3186
3187
3188
3189 // Currently only implemented for datatype DNA
3190 // Note: N positions are not counted if the other sequence contains a gap.
3191 // In this case only the gap and not the N is counted, since the sequence positions
3192 // are not comparable.
3193 // The function does to compute the distance but the length, differences, gaps
3194 // and Ns positions.
3195 // Note: length_comparable_nucleotieds + gaps_extensions + Ns must add up to
3196 // the length of the range.
3197 void sequence_distance(unsigned s1, unsigned s2, unsigned begin_range, unsigned end_range,
3198 unsigned &differences, unsigned &length_comparable_nucleotieds,
3199 unsigned &gap_openings, unsigned &gaps_extensions, unsigned &Ns)
3200 {
3201 unsigned i = begin_range;
3202 char c1, c2;
3203
3204 if (s1 >= taxaNum || s2 >= taxaNum)
3205 {
3206 differences = UINT_MAX;
3207 return;
3208 }
3209
3210 CSequence_Mol* seq1 = seqData[s1];
3211 CSequence_Mol* seq2 = seqData[s2];
3212
3213 if (end_range < begin_range)
3214 {
3215 std::cerr << "Error in sequence_distance: end_range < begin_range" << std::endl;
3216 exit(-33);
3217 }
3218
3219 if ((end_range - begin_range > seq1->length()) || (end_range - begin_range > seq2->length()) )
3220 {
3221 end_range = begin_range + seq1->length();
3222 if (end_range - begin_range > seq2->length())
3223 end_range = begin_range + seq2->length();
3224 }
3225
3226 unsigned local_len = 0;
3227 unsigned local_numgapsopen = 0;
3228 unsigned local_numgapext = 0;
3229 unsigned local_differences = 0;
3230 unsigned local_numNs = 0;
3231 bool in_gap = false;
3232
3233 if (seq1->get_datatype() != CSequence_Mol::dna)
3234 {
3235 differences = -2;
3236 return;
3237 }
3238
3239
3240 while (i != end_range)
3241 {
3242 // TODO: DO WE NEED TOUPPER??
3243 c1 = toupper(seq1->get_pos(i));
3244 c2 = toupper(seq2->get_pos(i));
3245
3246 if (c1 == '-' || c2 == '-')
3247 {
3248 if (!in_gap)
3249 {
3250 ++local_numgapsopen;
3251 in_gap = true;
3252 }
3253 ++local_numgapext;
3254 }
3255 else
3256 {
3257 in_gap = false;
3258 if (c1 == 'N' || c2 == 'N')
3259 ++local_numNs;
3260 else
3261 {
3262 ++local_len;
3263 if (c1 != c2)
3264 ++local_differences;
3265 }
3266 }
3267 ++i;
3268 }
3269
3270 differences = local_differences;
3271 length_comparable_nucleotieds = local_len;
3272 gap_openings = local_numgapsopen;
3273 gaps_extensions = local_numgapext;
3274 Ns = local_numNs;
3275 }
3276
3277
3278 // Currently only implemented for datatype DNA
3279 // Allowed flag values:
3280 // 0: normal mode.
3281 // 1: Gap regions always get a distance of -3.
3282 void get_sequences_distances(unsigned begin_range, unsigned end_range, void (*call_back_distance)(short, short, double), unsigned flag=0)
3283 {
3284 // Compute all pairwise distances:
3285 short N = taxaNum;
3286 short i, j;
3287 double dist;
3288
3289 for (i=0; i<N; ++i)
3290 {
3291 for (j=i+1; j<N; ++j)
3292 {
3293 dist = sequence_distance(i, j, begin_range, end_range, flag);
3294 call_back_distance(i,j,dist);
3295 }
3296 }
3297 }
3298
3299 // Same as above, but for some distances, those that have a false value in vector
3300 // we assign an invalidly large value to the distance.
3301 // Here a value of 100 is assigned to those distances
3302 void get_sequences_distances(unsigned begin_range, unsigned end_range, void (*call_back_distance)(short, short, double), const std::vector<bool> &sequences_valid, unsigned flag=0)
3303 {
3304 // Compute all pairwise distances:
3305 unsigned N = taxaNum;
3306 unsigned i, j;
3307 double dist;
3308
3309 if (sequences_valid.size() != N)
3310 {
3311 std::cerr << "Critical internal error: In function get_sequences_distances the size of the vector sequences_valid must be equal to the number of sequences in the sequences object." << std::endl;
3312 exit(-3);
3313 }
3314
3315 for (i=0; i<N; ++i)
3316 {
3317 for (j=i+1; j<N; ++j)
3318 {
3319 if (!sequences_valid[i] || !sequences_valid[j])
3320 {
3321 dist = 100;
3322 }
3323 else
3324 {
3325 dist = sequence_distance(i, j, begin_range, end_range, flag);
3326 }
3327 call_back_distance(i,j,dist);
3328 }
3329 }
3330 }
3331
3332
3333 CSequence_Mol* get_sequence_with_sequence_name_match(faststring &partial_name)
3334 {
3335 unsigned i;
3336
3337 for (i=0; i < taxaNum; ++i)
3338 {
3339 if ( seqData[i]->getFullName_faststring().find(partial_name) != faststring::npos )
3340 {
3341 return seqData[i];
3342 }
3343 }
3344 return NULL;
3345 }
3346
3347 void get_alignment_as_copy(std::vector<faststring> &v)
3348 {
3349 v.clear();
3350 v.reserve(taxaNum+1);
3351
3352 unsigned i;
3353 for (i=0; i<taxaNum; ++i)
3354 {
3355 v.push_back(seqData[i]->getSeq_faststring());
3356 v[i].c_str(); // Make buffer 0-terminated.
3357 }
3358 }
3359
3360 };
3361
3362
3363
3364 // inline CSequences::CSequences():posNum(0),datatype(0),splits(NULL){}
3365
3366
3367 //inline string CSequences::GetTaxonLabel(unsigned i)
3368 // {return taxa.GetTaxonLabel(i);}
3369 //inline void CSequences::SetTaxonLabel(unsigned i, string s)
3370 // {taxa.SetTaxonLabel(i,s);}
3371
3372
3373
3374
3375
3376
3377 /* inline void PrintSpecial_TaxaSeq(ostream& os, */
3378 /* const std::vector<unsigned>& taxa_vec, */
3379 /* const std::vector<unsigned>& pos_vec, */
3380 /* const CTaxa *ptaxa, */
3381 /* const CSequences2 *pseq, */
3382 /* const char* symbolsList, */
3383 /* bool printTaxonLabels, */
3384 /* unsigned taxonLabelPrintWidth, */
3385 /* unsigned maxTaxonLabelLength) */
3386 /* { */
3387 /* std::vector<unsigned>::const_iterator taxa_vec_it; */
3388 /* std::vector<unsigned>::const_iterator taxa_vec_end = taxa_vec.end(); */
3389
3390 /* std::vector<unsigned>::const_iterator pos_vec_it; */
3391 /* std::vector<unsigned>::const_iterator pos_vec_end = pos_vec.end(); */
3392
3393 /* unsigned theTaxonNumber; */
3394
3395 /* std::ios_base::fmtflags orig_ios_flag = os.flags(); */
3396 /* os.flags(orig_ios_flag | ios::left); */
3397
3398 /* for (taxa_vec_it=taxa_vec.begin(); taxa_vec_it!=taxa_vec_end; ++taxa_vec_it) */
3399 /* { */
3400 /* theTaxonNumber = *taxa_vec_it; */
3401
3402 /* if (printTaxonLabels) */
3403 /* { */
3404 /* os.width(maxTaxonLabelLength); */
3405 /* faststring tl = ptaxa->GetTaxonLabel(theTaxonNumber); */
3406 /* tl.shorten(maxTaxonLabelLength); */
3407 /* os << tl; */
3408 /* int morespaces = (int)taxonLabelPrintWidth-(int)maxTaxonLabelLength; */
3409
3410 /* if ( morespaces > 0 ) */
3411 /* { */
3412 /* os.width(morespaces); */
3413 /* os << " "; */
3414 /* } */
3415 /* } */
3416
3417 /* for (pos_vec_it = pos_vec.begin(); pos_vec_it != pos_vec_end; ++pos_vec_it) */
3418 /* { */
3419 /* os << symbolsList[pseq->GetChar(theTaxonNumber,*pos_vec_it)]; */
3420 /* } */
3421 /* os << std::endl; */
3422 /* } */
3423 /* os.flags(orig_ios_flag); */
3424 /* } */
3425
3426 /* inline */
3427 /* void PrintSpecial_PosNumbers(ostream& os, */
3428 /* std::vector<unsigned> pos_vec, // we get a real copy */
3429 /* const CSequences2 *pseq, */
3430 /* unsigned taxonLabelPrintWidth, */
3431 /* bool UseNexusComments) */
3432 /* { */
3433 /* unsigned i; */
3434 /* unsigned numPos = pos_vec.size(); */
3435 /* unsigned printNoZerosTill = numPos; */
3436 /* bool printNoZero_set = false; */
3437
3438 /* // We determine the original position numbers: */
3439 /* for (i=0; i<numPos; ++i) */
3440 /* pos_vec[i] = pseq->GetOriginalPosNumber(pos_vec[i]); */
3441
3442 /* unsigned maxDigits = ((unsigned)log10((double)pos_vec[numPos-1]))+1; */
3443 /* unsigned factor = 1; */
3444 /* unsigned digit; */
3445
3446 /* for (i=1; i<maxDigits; ++i) */
3447 /* factor *= 10; */
3448
3449 /* for (; factor; factor /= 10, printNoZero_set = false) */
3450 /* { */
3451 /* if (UseNexusComments) */
3452 /* { */
3453 /* os.width(taxonLabelPrintWidth); */
3454 /* os << "[ "; */
3455 /* } */
3456 /* else */
3457 /* { */
3458 /* os.width(taxonLabelPrintWidth); */
3459 /* os << ' '; */
3460 /* } */
3461 /* for (i=0; i < numPos; ++i) */
3462 /* { */
3463 /* digit = pos_vec[i]/factor; */
3464
3465 /* if ( i >= printNoZerosTill || digit > 0) */
3466 /* { */
3467 /* if (!printNoZero_set) */
3468 /* { */
3469 /* printNoZerosTill = i; */
3470 /* printNoZero_set = true; */
3471 /* } */
3472 /* os << (char)(digit+'0'); */
3473 /* pos_vec[i] -= factor*digit; */
3474 /* } */
3475 /* else */
3476 /* { */
3477 /* os << ' '; */
3478 /* } */
3479 /* } */
3480 /* if (UseNexusComments) */
3481 /* { */
3482 /* os << "]" << std::endl; */
3483 /* } */
3484 /* else */
3485 /* { */
3486 /* os << std::endl; */
3487 /* } */
3488 /* } */
3489 /* } */
3490
3491
3492 /* inline void CSequences::GetBaseFrequencies(unsigned ti, */
3493 /* std::vector<unsigned> bf) */
3494 /* { */
3495 /* unsigned pos; */
3496 /* for (pos = 0; pos < posNum; ++pos) */
3497 /* ++bf[seqData[ti][pos]] */
3498 /* } */
3499
3500
3501 #endif