Debian Codegraph @

CBlastParser.h

raw
1 /* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits
2 * BaitFilter (version 1.0.6) a program for selecting optimal bait regions
3 * Copyright 2013-2017 by Christoph Mayer
4 *
5 * This source file is part of the BaitFisher-package.
6 *
7 * This program is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
19 *
20 *
21 * For any enquiries send an Email to Christoph Mayer
22 * [email protected]
23 *
24 * When publishing work that is based on the results please cite:
25 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
26 *
27 */
28 // Some parts of this header file could be made more efficient.
29 // Much of the functionality relies on a sorted list of Blast hits.
30 // The question arises whether a list is the best data structure for such
31 // a purpose. It could be more efficient to use a data structure such as
32 // a set, which is sorted automatically and which should in principle be
33 // more efficient.
34
35 // GI number will not be supported by NCBI in the future! So far we have not removed the code.
36 // This should be done soon.
37
38 #ifndef CBLASTPARSER_H
39 #define CBLASTPARSER_H
40
41 // The following two defines allow us to use fopen() in "CSeqNameList.h"
42 // without error message when using the Visual Studio 2015 compiler.
43 #define _CRT_SECURE_NO_DEPRECATE
44 #define _CRT_SECURE_NO_WARNINGS
45
46 #include <iostream>
47 #include "CFile/CFile2_1.h"
48 #include "faststring2.h"
49 #include <vector>
50 #include <set>
51 #include <list>
52 #include "CSeqNameList.h"
53
54 #include "range_functions.h"
55 #include "CHistogram.h"
56
57 #include "typedefs.h"
58 #include <climits>
59
60 class CTaxonomy;
61 class CBlastHit;
62
63 // Forward declaration of friend functions in order to make them globally visible (friend injection problem):
64 bool less_than_CBlastHit_query(const CBlastHit &a, const CBlastHit &b);
65 bool less_than_CBlastHit_query_quality(const CBlastHit &a, const CBlastHit &b);
66 bool less_than_CBlastHit_target(const CBlastHit &a, const CBlastHit &b);
67 bool operator<(const CBlastHit &a, const CBlastHit &b);
68 bool less_than_CBlastHit_pointer_query(const CBlastHit *a, const CBlastHit *b);
69 bool less_than_CBlastHit_pointer_query_quality(const CBlastHit *a, const CBlastHit *b);
70 bool less_than_CBlastHit_pointer_target(const CBlastHit *a, const CBlastHit *b);
71
72
73 signed char CB_is_gi_of_type(CTaxonomy *tax, unsigned gi, unsigned type);
74
75 struct struct_less_than_CBlastHit_pointer_query_quality
76 {
77 bool operator()(const CBlastHit *a, const CBlastHit *b)
78 {
79 return less_than_CBlastHit_pointer_query_quality(a,b);
80 }
81 };
82
83
84 static void __add_or_count(std::map<unsigned, unsigned> &m, unsigned x)
85 {
86 std::map<unsigned, unsigned>::iterator it;
87
88 it = m.find(x);
89 if (it == m.end() )
90 {
91 m[x] = 1;
92 }
93 else
94 {
95 ++it->second;
96 }
97 }
98
99 /* //Not used in most applications. Not tested yet. Needs to be tested before it is used.
100 static void majority_rule(std::vector<unsigned> v, int &val, double &prop)
101 {
102 CHistogram h(v, -10);
103
104 double value;
105
106 h.dominant_category(value, prop);
107
108 val = (int)(value+0.5); // Adding 0.5 ensures we are not returning a wrong int due to
109 // rounding errors.
110 }
111 */
112
113 class CBlastHit
114 {
115 private:
116 unsigned internal_number;
117
118 faststring target_seq_name;
119 faststring query_seq_name;
120
121 double perfection;
122 unsigned length;
123 unsigned mismatches;
124 unsigned gaps;
125
126 bool reverse_query;
127 bool reverse_target;
128
129 unsigned start_query;
130 unsigned end_query;
131 unsigned start_target;
132 unsigned end_target;
133
134 double e_value;
135 double score;
136
137 public:
138
139 CBlastHit(const faststring& line, unsigned in):internal_number(in)
140 {
141 std::vector<faststring> v;
142
143 split(v, line);
144
145 // std::cout << v.size() << std::endl;
146
147 if (v.size() == 12)
148 {
149
150 query_seq_name = v[0];
151 target_seq_name = v[1];
152
153 perfection = v[2].ToDouble();
154 length = v[3].ToUnsigned();
155 mismatches = v[4].ToUnsigned();
156 gaps = v[5].ToUnsigned();
157
158 start_query = v[6].ToUnsigned();
159 end_query = v[7].ToUnsigned();
160
161 // std::cerr << "Identfied start_query: " << start_query << std::endl;
162 // std::cerr << "Identfied end_query: " << end_query << std::endl;
163
164 start_target = v[8].ToUnsigned();
165 end_target = v[9].ToUnsigned();
166
167 e_value = v[10].ToDouble();
168 score = v[11].ToDouble();
169
170 if (start_query > end_query)
171 {
172 reverse_query= true;
173 unsigned tmp;
174 tmp = start_query;
175 start_query = end_query;
176 end_query = tmp;
177 }
178 else
179 reverse_query= false;
180
181 if (start_target > end_target)
182 {
183 reverse_target = true;
184 unsigned tmp;
185 tmp = start_target;
186 start_target = end_target;
187 end_target = tmp;
188 }
189 else
190 reverse_target= false;
191 }
192 else
193 {
194 std::cerr << "Unrecognised line of input passed to CBlastHit constructor: " << line << "\n";
195 }
196 }
197
198 double get_perfection()
199 {
200 return perfection;
201 }
202
203 unsigned get_length()
204 {
205 return length;
206 }
207
208 unsigned get_query_span()
209 {
210 if (end_query >= start_query)
211 return end_query - start_query+1;
212 else
213 return start_query - end_query+1;
214 }
215
216 // Searches for gi|xxxxxxxx| in the query sequence and returns the xxx string.
217 void extract_GI_number_query(faststring &gi)
218 {
219 faststring::size_t pos1 = query_seq_name.find("gi|");
220 faststring::size_t pos2;
221 if (pos1 != faststring::npos)
222 {
223 pos2 = query_seq_name.find("|", pos1+3);
224 if (pos2 == faststring::npos) // No proper gi number found so we return empty string;
225 {
226 gi.clear();
227 return;
228 }
229 gi = query_seq_name.substr(pos1+3, pos2-pos1-3);
230 return;
231 }
232 else // No proper gi number found so we return empty string;
233 {
234 gi.clear();
235 return;
236 }
237 }
238
239 void extract_GI_number_target(faststring &gi)
240 {
241 faststring::size_t pos1 = target_seq_name.find("gi|");
242 faststring::size_t pos2;
243 if (pos1 != faststring::npos)
244 {
245 pos2 = target_seq_name.find("|", pos1+3);
246 if (pos2 == faststring::npos) // No proper gi number found so we return empty string;
247 {
248 gi.clear();
249 return;
250 }
251 gi = target_seq_name.substr(pos1+3, pos2-pos1-3);
252 return;
253 }
254 else // No proper gi number found so we return empty string;
255 {
256 gi.clear();
257 return;
258 }
259 }
260
261
262 double get_evalue()
263 {
264 return e_value;
265 }
266
267 unsigned get_start_query()
268 {
269 return start_query;
270 }
271
272 unsigned get_end_query()
273 {
274 return end_query;
275 }
276
277 unsigned get_start_target()
278 {
279 return start_target;
280 }
281
282 unsigned get_end_target()
283 {
284 return end_target;
285 }
286
287 const faststring &get_query_seq_name()
288 {
289 return query_seq_name;
290 }
291
292 const faststring &get_target_seq_name()
293 {
294 return target_seq_name;
295 }
296
297
298 friend bool less_than_CBlastHit_query(const CBlastHit &a, const CBlastHit &b)
299 {
300 // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection
301
302 // a.print(std::cerr);
303 // b.print(cerr);
304
305 // Primary criterion: Query seq name:
306 if (a.query_seq_name != b.query_seq_name)
307 return a.query_seq_name < b.query_seq_name;
308
309 if (a.start_query != b.start_query)
310 return a.start_query < b.start_query;
311 if (a.end_query != b.end_query)
312 return a.end_query < b.end_query;
313
314 if (a.target_seq_name != b.target_seq_name)
315 return a.target_seq_name < b.target_seq_name;
316
317 if (a.start_target != b.start_target)
318 return a.start_target < b.start_target;
319
320 if (a.end_target != b.end_target)
321 return a.end_target < b.end_target;
322
323 // They should be irrelevant since we would have multiple identical hits
324 // if we come here.
325 if (a.length != b.length)
326 return a.length < b.length;
327
328 // if (a.perfection != b.perfection) // Including this line is a bug. This was a bug.
329 return a.perfection < b.perfection;
330 }
331
332 friend bool less_than_CBlastHit_query_quality(const CBlastHit &a, const CBlastHit &b)
333 {
334 // First criterion: name of query sequence: ascending (smaller is "better")
335 // Second criterion: e_value ascending (smaller is better)
336 // Third criterion: score descending (higher is better)
337 // Fourth criterion: perfection descending (higher is better)
338 // Fifth criterion: sequence positions
339 // Sixth criterion: target sequence name and positions
340
341 // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection
342
343 // a.print(std::cerr);
344 // b.print(cerr);
345
346 // Primary criterion: Query seq name:
347 if (a.query_seq_name != b.query_seq_name)
348 return a.query_seq_name < b.query_seq_name;
349
350 // Secondary criterion: e_value
351 if (a.e_value != b.e_value)
352 return a.e_value < b.e_value;
353
354 if (a.score != b.score)
355 return a.score > b.score;
356
357 if (a.perfection != b.perfection)
358 return a.perfection > b.perfection;
359
360 if (a.start_query != b.start_query)
361 return a.start_query < b.start_query;
362
363 if (a.end_query != b.end_query)
364 return a.end_query < b.end_query;
365
366 if (a.target_seq_name != b.target_seq_name)
367 return a.target_seq_name < b.target_seq_name;
368
369 if (a.start_target != b.start_target)
370 return a.start_target < b.start_target;
371
372 if (a.end_target != b.end_target)
373 return a.end_target < b.end_target;
374
375 // They should be irrelevant since we would have multiple identical hits
376 // if we come here.
377 // if (a.length != b.length) // Including this line is a bug. This was a bug.
378 return a.length < b.length;
379 }
380
381
382
383
384 friend bool less_than_CBlastHit_target(const CBlastHit &a, const CBlastHit &b)
385 {
386 // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection
387
388 // a.print(std::cerr);
389 // b.print(cerr);
390
391 // Primary criterion: Target seq name:
392
393
394 if (a.target_seq_name != b.target_seq_name)
395 return a.target_seq_name < b.target_seq_name;
396
397 if (a.start_target != b.start_target)
398 return a.start_target < b.start_target;
399
400 if (a.end_target != b.end_target)
401 return a.end_target < b.end_target;
402
403 if (a.query_seq_name != b.query_seq_name)
404 return a.query_seq_name < b.query_seq_name;
405
406 if (a.start_query != b.start_query)
407 return a.start_query < b.start_query;
408
409 if (a.end_query != b.end_query)
410 return a.end_query < b.end_query;
411
412 // They should be irrelevant since we would have multiple identical hits
413 // if we come here.
414 if (a.length != b.length)
415 return a.length < b.length;
416
417 // if (a.perfection != b.perfection) // Including this line is a bug. This was a bug.
418 return a.perfection < b.perfection;
419 }
420
421 friend bool operator<(const CBlastHit &a, const CBlastHit &b)
422 {
423 // std::cout << "---------------" << std::endl;
424 return less_than_CBlastHit_query(a,b);
425 }
426
427 friend bool less_than_CBlastHit_pointer_query(const CBlastHit *a, const CBlastHit *b)
428 {
429 return (*a < *b);
430 }
431
432 friend bool less_than_CBlastHit_pointer_query_quality(const CBlastHit *a, const CBlastHit *b)
433 {
434 return (less_than_CBlastHit_query_quality(*a, *b));
435 }
436
437 friend bool less_than_CBlastHit_pointer_target(const CBlastHit *a, const CBlastHit *b)
438 {
439 return (less_than_CBlastHit_target(*a, *b));
440 }
441
442 void print(std::ostream &os, char delim = '\t') const
443 {
444 os << internal_number << delim;
445 os << query_seq_name << delim;
446 os << target_seq_name << delim;
447
448 os << perfection << delim;
449 os << length << delim;
450 os << mismatches << delim;
451 os << gaps << delim;
452
453 os << start_query << delim;
454 os << end_query << delim;
455 os << start_target << delim;
456 os << end_target << delim;
457
458 os << e_value << delim;
459 os << score;
460 os << '\n';
461 }
462
463 void print(std::ostream &os,
464 bool pinternal_number,
465 bool pqueryname,
466 bool ptargetname,
467 bool pperfection,
468 bool plength,
469 bool pmismatches,
470 bool pgaps,
471 bool pstart_query,
472 bool pend_query,
473 bool pstart_target,
474 bool pend_target,
475 bool pe_value,
476 bool pscore,
477 char delim = '\t') const
478 {
479 if (pinternal_number)
480 os << internal_number << delim;
481
482 if (pqueryname)
483 os << query_seq_name << delim;
484
485 if (ptargetname)
486 os << target_seq_name << delim;
487
488 if (pperfection)
489 os << perfection << delim;
490
491 if (plength)
492 os << length << delim;
493
494 if (pmismatches)
495 os << mismatches << delim;
496
497 if (pgaps)
498 os << gaps << delim;
499
500 if (pstart_query)
501 os << start_query << delim;
502
503 if (pend_query)
504 os << end_query << delim;
505
506 if (pstart_target)
507 os << start_target << delim;
508
509 if (pend_target)
510 os << end_target << delim;
511
512 if (pe_value)
513 os << e_value << delim;
514
515 if (pscore)
516 os << score;
517
518 os << '\n';
519 }
520
521 void print_essential_1(std::ostream &os, char delim = '\t') const
522 {
523 os << query_seq_name << delim;
524 os << "E: " << e_value << delim;
525 os << "len: " << length << delim;
526 os << "%: " << perfection << delim;
527 os << '\n';
528 }
529
530
531
532 };
533
534
535 class CBlast_parser
536 {
537 std::list<CBlastHit*> lbh;
538 // Previous versions of this header file used a map in the declaration of bh_map.
539 // This map is/was only used in the get_max_hit_query_span__matching_beginning2 function.
540 // In a map in which elements are inserted with the insert function we only inserted the first (and best entry) for
541 // each query. This was fine for all cases for which we used this map so far.
542 // However, a multimap has the same functionality and is more secure, since it will store all entries.
543
544 std::multimap<faststring, CBlastHit*> bh_map;
545
546 // Stores coverage in bp. If query seq. length is known it can be used to determine the relative sequence length.
547 std::map<faststring, unsigned> total_coverage_map;
548
549 bool query_name_quality_sorted;
550 //TODO: add delete in destructor concept to improve performance in some constructors by avoiding to copy the data.
551
552 void add(CBlastHit* p)
553 {
554 lbh.push_back(p);
555 faststring tmp = p->get_query_seq_name();
556 bh_map.insert(bh_map.end(), std::make_pair(tmp, p));
557 }
558
559 public:
560 CBlast_parser(const char *filename):query_name_quality_sorted(false)
561 {
562 CFile f;
563 faststring line;
564 unsigned counter=0;
565
566 f.ffopen(filename);
567
568 #ifdef FINANA
569 std::cerr << "We are in the FINANA mode.\n";
570 #endif
571
572 f.getline(line);
573 while (!f.fail() )
574 {
575 line.removeSpacesFront();
576 line.removeSpacesBack();
577
578 if (!line.empty() && line[0] != '#') // if not a comment - allows us to read the -m 9 in addition to the -m 8 output format
579 {
580 CBlastHit* p = new CBlastHit(line, counter);
581
582 // Debugging code:
583 // if (counter > 1)
584 // break;
585
586 ++counter;
587 add(p);
588 }
589 f.getline(line);
590 }
591 }
592
593 // Default constructor - rarely used.
594 CBlast_parser():query_name_quality_sorted(false)
595 {}
596
597
598 ~CBlast_parser()
599 {
600 std::list<CBlastHit*>::iterator it, it_end;
601 it = lbh.begin();
602 it_end = lbh.end();
603
604 while (it != it_end)
605 {
606 // (**it).print(std::cout);
607 delete *it;
608 ++it;
609 }
610 }
611
612 // See also keep_only_n_top_hits
613 // Copy constructor that can be used to filter the n first blast hits for a query.
614 // Will be sorted by query name, since the source will be sorted.
615 CBlast_parser(CBlast_parser &b, unsigned n=UINT_MAX):query_name_quality_sorted(true)
616 {
617 b.sort_by_query_name_quality();
618
619 std::list<CBlastHit*>::iterator it, it_end;
620 it = b.lbh.begin();
621 it_end = b.lbh.end();
622
623 faststring last_qname;
624 unsigned count = 0;
625
626 while (it != it_end)
627 {
628 if ((**it).get_query_seq_name() == last_qname)
629 {
630 ++count;
631 }
632 else
633 {
634 count = 1;
635 last_qname = (**it).get_query_seq_name();
636 }
637
638 CBlastHit* tmp_copy;
639 if (count <= n)
640 {
641 tmp_copy = new CBlastHit(**it);
642 add(tmp_copy);
643 }
644
645 ++it;
646 }
647 }
648
649 // Copy constructor which filters hits that have a specific taxonomy
650 // of the target.
651 CBlast_parser(CBlast_parser &b, CTaxonomy *tax, unsigned type,
652 signed char (*func)(CTaxonomy *, unsigned, unsigned)):query_name_quality_sorted(b.query_name_quality_sorted)
653 {
654 std::list<CBlastHit*>::iterator it, it_end;
655 it = b.lbh.begin();
656 it_end = b.lbh.end();
657
658 unsigned target_gi;
659 faststring tmp;
660 CBlastHit *tmp_copy;
661 signed char res;
662
663 while (it != it_end)
664 {
665 (**it).extract_GI_number_target(tmp);
666 target_gi = tmp.ToUnsigned();
667
668 res = func(tax,target_gi, type);
669 if (res < 0)
670 {
671 std::cerr << "Warning: In CBlast_parser. res < 0.\n";
672 std::cerr << "GI number seems to be unknown: String: " << tmp << " unsigned: " << target_gi << '\n';
673 // exit(0);
674 }
675
676 if (res > 0)
677 {
678 tmp_copy = new CBlastHit(**it);
679 add(tmp_copy);
680 }
681 ++it;
682 }
683 }
684
685 // Copy constructor which filters hits that have a match in the title field
686 CBlast_parser(CBlast_parser &b, CTaxonomy *tax, std::vector<faststring> &query_strings,
687 signed char (*func)(CTaxonomy *, unsigned, std::vector<faststring> &query_strings)):query_name_quality_sorted(b.query_name_quality_sorted)
688 {
689 std::list<CBlastHit*>::iterator it, it_end;
690 it = b.lbh.begin();
691 it_end = b.lbh.end();
692
693 unsigned target_gi;
694 faststring tmp;
695 CBlastHit *tmp_copy;
696 signed char res;
697
698 while (it != it_end)
699 {
700 (**it).extract_GI_number_target(tmp);
701 target_gi = tmp.ToUnsigned();
702
703 res = func(tax,target_gi, query_strings);
704 if (res < 0)
705 {
706 std::cerr << "Error in CBlast_parser. res < 0.\n\n";
707 exit(0);
708 }
709
710 if (res > 0)
711 {
712 tmp_copy = new CBlastHit(**it);
713 add(tmp_copy);
714 }
715 ++it;
716 }
717 }
718
719 void clear()
720 {
721 lbh.clear();
722 query_name_quality_sorted = false;
723 }
724
725
726 unsigned get_hit_count()
727 {
728 return lbh.size();
729 }
730
731
732 void keep_only_n_top_hits(unsigned n=1)
733 {
734 sort_by_query_name_quality();
735 // lbh.sort(less_than_CBlastHit_pointer_query_quality);
736
737 std::list<CBlastHit*>::iterator it, it2, it_end;
738 it = lbh.begin();
739 it_end = lbh.end();
740
741 faststring last_name;
742 unsigned i=1;
743
744 while (it != it_end)
745 {
746 if ( (**it).get_query_seq_name() == last_name )
747 {
748 ++i; // Count this hit
749 if (i>n)
750 {
751 // Remove *it:
752 delete *it;
753 it = lbh.erase(it);
754 } // it now points to the hit behind the hit that has been removed.
755 // it should not be incremented any more.
756 }
757 else
758 {
759 last_name = (**it).get_query_seq_name();
760 i=1;
761 ++it;
762 }
763 }
764 }
765
766 // Remove all hits for func does not return true when given gi:
767 void keep_only_hits_for_which_func_returns_true_for_parameter_gi(CTaxonomy *tax,
768 bool (*func)(CTaxonomy *, unsigned gi),
769 const char *s)
770 {
771 std::list<CBlastHit*>::iterator it, it2, it_end;
772 it = lbh.begin();
773 it_end = lbh.end();
774
775 unsigned gi;
776 faststring tmp;
777 unsigned count = 0;
778
779 while (it != it_end)
780 {
781 (**it).extract_GI_number_target(tmp);
782 gi = tmp.ToUnsigned();
783
784 if (!func(tax, gi))
785 {
786 std::cerr << s << (**it).get_target_seq_name() << " Gi: " << gi << ". Blast hit will be removed.\n";
787 ++count;
788
789 // Remove *it:
790 delete *it;
791 it = lbh.erase(it);
792 }
793 else
794 {
795 ++it;
796 }
797 }
798
799 std::cerr << "WARNING: Number of blast hits removed since no taxid could be found for gi: "
800 << count
801 << '\n';
802 }
803
804
805 void keep_only_e_select(double max_e, double factor_max_decrease)
806 {
807 // Sort by query name, then by e-value.
808 // Filter all those with e < max_e and e < best-hit-this-query * factor_max_decrease
809
810 sort_by_query_name_quality();
811 // lbh.sort(less_than_CBlastHit_pointer_query_quality);
812
813 std::list<CBlastHit*>::iterator it, it_end;
814 it = lbh.begin();
815 it_end = lbh.end();
816
817 faststring last_hit_query = "";
818 double best_e_value_this_query;
819 bool erase_this;
820
821
822 while (it != it_end)
823 {
824 faststring this_hit_query = (*it)->get_query_seq_name();
825 double this_hit_e = (*it)->get_evalue();
826 erase_this = false;
827
828 if (this_hit_e < max_e)
829 {
830 if (this_hit_query == last_hit_query) // Still the same query
831 {
832 //
833 if (this_hit_e > best_e_value_this_query*factor_max_decrease)
834 {
835 erase_this = true;
836 }
837 // else // if "<=" then keep
838
839 if (this_hit_e < best_e_value_this_query)
840 {
841 // Should never happen since this is sorted.
842 std::cerr << "Error better Evalue found: ";
843 (*it)->print(std::cerr);
844 std::cerr << '\n';
845 }
846 }
847 else // A new query sequence
848 {
849 // Must be best hit this query
850 last_hit_query = this_hit_query;
851 best_e_value_this_query = this_hit_e;
852 // keep
853 }
854 } // if (this_hit_e < max_e)
855 else // erase
856 {
857 erase_this = true;
858 }
859
860 // Simple logic to remove this hit.
861 if (erase_this)
862 {
863 delete *it;
864 it = lbh.erase(it);
865 }
866 else
867 {
868 ++it;
869 }
870 }
871 }
872
873
874
875
876
877 void print_all(std::ostream &os)
878 {
879 std::list<CBlastHit*>::iterator it, it_end;
880 it = lbh.begin();
881 it_end = lbh.end();
882
883 while (it != it_end)
884 {
885 (*it)->print(os);
886 ++it;
887 }
888 }
889
890 void print_all(std::ostream &os,
891 bool pinternal_number,
892 bool pqueryname,
893 bool ptargetname,
894 bool pperfection,
895 bool plength,
896 bool pmismatches,
897 bool pgaps,
898 bool pstart_query,
899 bool pend_query,
900 bool pstart_target,
901 bool pend_target,
902 bool pe_value,
903 bool pscore,
904 char delim = '\t')
905 {
906 std::list<CBlastHit*>::iterator it, it_end;
907 it = lbh.begin();
908 it_end = lbh.end();
909
910 while (it != it_end)
911 {
912 (*it)->print(os,
913 pinternal_number,
914 pqueryname,
915 ptargetname,
916 pperfection,
917 plength,
918 pmismatches,
919 pgaps,
920 pstart_query,
921 pend_query,
922 pstart_target,
923 pend_target,
924 pe_value,
925 pscore,
926 delim = '\t');
927 ++it;
928 }
929 }
930
931 void print_with_title(std::ostream &os, const std::map<unsigned, faststring> &gi2title_map)
932 {
933 std::list<CBlastHit*>::iterator it, it_end;
934 faststring tmp;
935 unsigned target_gi;
936
937 it = lbh.begin();
938 it_end = lbh.end();
939
940 while (it != it_end)
941 {
942 (*it)->print_essential_1(os);
943 os << std::endl;
944 (**it).extract_GI_number_target(tmp);
945 target_gi = tmp.ToUnsigned();
946
947 const_iterator_U_Faststring_map find_it;
948 find_it = gi2title_map.find(target_gi);
949
950 if (find_it != gi2title_map.end() )
951 {
952 os << find_it->second << std::endl;
953 }
954 else
955 {
956 os << "*** No title available. for gi" << target_gi << " ***" << std::endl;
957 }
958 ++it;
959 }
960
961
962 }
963
964 void sort_by_query_name_quality()
965 {
966 // std::cerr << "RESORT" << std::endl;
967 if (!query_name_quality_sorted)
968 {
969 lbh.sort(less_than_CBlastHit_pointer_query_quality);
970 query_name_quality_sorted = true;
971 }
972 }
973
974 // Calling this function is discouraged. We recommend to call:
975 // sort_by_query_name_quality(), since this is more efficient
976 // in the case of multiple calls.
977 void sort_query()
978 {
979 lbh.sort(less_than_CBlastHit_pointer_query);
980 query_name_quality_sorted = false;
981 }
982
983
984 void sort_target()
985 {
986 lbh.sort(less_than_CBlastHit_pointer_target);
987 query_name_quality_sorted = false;
988 }
989
990
991 std::list<CBlastHit*>::iterator begin()
992 {
993 return lbh.begin();
994 }
995
996
997 std::list<CBlastHit*>::iterator end()
998 {
999 return lbh.end();
1000 }
1001
1002 /*
1003 void erase(std::list<CBlastHit*>::iterator it)
1004 {
1005 lbh.erase(it);
1006 }
1007 */
1008
1009 void filter_CSeqNameList_with_major_blast_hit(CSeqNameList &orig, CSeqNameList &result_with,
1010 double min_query_prop, double min_perfection, double max_evalue,
1011 bool min_query_prop_with_respect_to_all_hits_this_query,
1012 const char * accepted_hits_Log_file_name=NULL,
1013 CSeqNameList *target_list=NULL, const char * search_expr=NULL)
1014 {
1015 if ( orig.is_only_names() )
1016 {
1017 std::cerr << "Object orig was created with the option <only_names>." << std::endl;
1018 std::cerr << "I do not know how to proceed." << std::endl;
1019 exit(0);
1020 }
1021
1022
1023
1024 if (min_query_prop_with_respect_to_all_hits_this_query)
1025 compute_coverage_map(min_perfection, max_evalue);
1026
1027 bool check_target_seq_match = target_list!= NULL && search_expr != NULL;
1028
1029 std::list<CBlastHit*>::iterator it, it_end;
1030
1031 sort_by_query_name_quality();
1032 // sort_query(); // This guarantees that hits are ordered by query name.
1033 // This will be used here.
1034
1035 it = lbh.begin();
1036 it_end = lbh.end();
1037
1038 // List of seq names:
1039 unsigned id_of_hit;
1040
1041 // std::map<faststring *, unsigned, less_than_pointer_to_faststring_struct>::iterator it_find;
1042
1043 CBlastHit* tmp;
1044
1045 faststring sname; // = tmp->get_query_seq_name();
1046 faststring lastname;
1047
1048 FILE *accepted_hits_log;
1049 if (accepted_hits_Log_file_name != NULL)
1050 {
1051 accepted_hits_log = fopen(accepted_hits_Log_file_name, "w");
1052 }
1053
1054 // We move through all Blast hits:
1055 while (it != it_end)
1056 {
1057 tmp = *it;
1058
1059 unsigned seq_len;
1060 unsigned hit_len;
1061 double hit_coverage;
1062 double hit_perfection;
1063 double hit_evalue;
1064
1065 // Get name of query of blast hit:
1066 sname = tmp->get_query_seq_name();
1067
1068 // std::cerr << "Working on hit with sname " << sname << std::endl;
1069
1070 if (sname != lastname) // We never want to add the same sequence twice.
1071 // If it has been added (see below) we won't check hits with the same query name
1072 // If the last hit has not been added lastname
1073 // should not have been updated to this name.
1074 {
1075 // Look up the name of the query in the list of sequences in the fasta file.
1076 // Remember: blast tells us the short name only.
1077 id_of_hit = orig.get_id_short_name(sname);
1078
1079 // std::cerr << "sname " << sname << " id-of-hit " << id_of_hit << std::endl;
1080
1081 if (id_of_hit == UINT_MAX)
1082 {
1083 std::cerr << "Error: Could not find sequence name: "
1084 << tmp->get_query_seq_name()
1085 << " for which a blast hit has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!"
1086 << std::endl;
1087 }
1088 else // Sequence of blast hit has been found
1089 {
1090 seq_len = orig.get_seq_length(id_of_hit);
1091
1092 // std::cerr << "sname " << sname << " " << id_of_hit << " " << seq_len << std::endl;
1093
1094 if (min_query_prop_with_respect_to_all_hits_this_query)
1095 {
1096 std::map<faststring, unsigned>::iterator it_find;
1097 it_find = total_coverage_map.find(sname);
1098 if (it_find != total_coverage_map.end())
1099 hit_len = it_find->second;
1100 else
1101 {
1102 std::cerr << "Warning: Could not find sequence "<< sname << " in total_coverage_map." << std::endl;
1103 hit_len = 0;
1104 }
1105 }
1106 else
1107 {
1108 // hit_len = tmp->get_length();
1109 // length might be wrong for protein / nucleotide balsts
1110 hit_len = tmp->get_end_query() - tmp->get_start_query() +1; // We need to add 1 since the end is the last index in hit range.
1111 }
1112 hit_perfection = tmp->get_perfection();
1113 hit_evalue = tmp->get_evalue();
1114
1115 hit_coverage = (double)hit_len/seq_len;
1116
1117 //
1118 // std::cerr << "seq-len hit_len coverage "<< sname << " " << seq_len << " " << hit_len << " " << hit_coverage << std::endl;
1119 //
1120
1121 if (hit_coverage >= min_query_prop && hit_perfection >= min_perfection && hit_evalue <= max_evalue)
1122 {
1123 // Query test OK!!
1124 if (check_target_seq_match) // Do we check the target seq. full name for a match??
1125 {
1126 unsigned t_id;
1127 faststring target_short_name = tmp->get_target_seq_name();
1128 t_id = target_list->get_id_short_name(target_short_name);
1129 faststring target_full_name = target_list->get_name(t_id);
1130
1131 // Strange effect: hit_coverage can 1.01 - is this a bug?
1132 if (hit_coverage > 1)
1133 {
1134 std::cerr << "Detected hit_coverage>1: " << hit_coverage << "#" << hit_len << "/" << seq_len << "#" << sname << "#" << target_full_name << std::endl;
1135 }
1136 faststring::size_t find_pos = target_full_name.find(search_expr);
1137 if (find_pos != faststring::npos) // search_expr has been found - we have a match
1138 {
1139 // This is an accepted hit:
1140
1141 if (accepted_hits_Log_file_name != NULL)
1142 {
1143 fprintf(accepted_hits_log, "Accepted hit (qT and tT passed):\t%s\t%s\thc:\t%.2lf\tperf:\t%.3lf\te-val:\t%8lf\n",
1144 sname.c_str(), target_full_name.c_str(), hit_coverage, hit_perfection, hit_evalue);
1145 }
1146 result_with.add_non_redundant(orig,id_of_hit);
1147 lastname = sname; // In case we add the hit, we will ignore other blast hits with the same query name.
1148 // In other words: A query with one or more hits is only inserted once.
1149 // std::cerr << "Would add: " << id_of_hit << std::endl;
1150 }
1151 else
1152 {
1153 if (accepted_hits_Log_file_name != NULL)
1154 {
1155 fprintf(accepted_hits_log, "Hit not accepted (qT OK but tT failed): %s hc: %.2lf perf: %.3lf e-val: %8lf\n",
1156 sname.c_str(), hit_coverage, hit_perfection, hit_evalue);
1157 }
1158
1159 std::cerr << "--Hit not accepted (qery-test OK, target does not match). Target seq: " << target_full_name << " ";
1160 tmp->print(std::cerr);
1161 }
1162 }
1163 else // Do not check target seq full name - so we have an accepted hit
1164 {
1165 // unsigned t_id;
1166 faststring target_short_name = tmp->get_target_seq_name();
1167
1168 // This is an accepted hit:
1169 result_with.add_non_redundant(orig, id_of_hit);
1170
1171 if (accepted_hits_Log_file_name != NULL)
1172 {
1173 fprintf(accepted_hits_log, "Accepted hit (qT OK, no tT):\t%s\t%s\thc:\t%.2lf\tperf:\t%.3lf\te-val:\t%8lf\n",
1174 // fprintf(accepted_hits_log, "Accepted hit (qT OK, no tT): %s hc: %.2lf perf: %.3lf e-val: %8lf\n",
1175 sname.c_str(), target_short_name.c_str(), hit_coverage, hit_perfection, hit_evalue);
1176 }
1177
1178 lastname = sname; // In case we add the hit, we will ignore other blast hits with the same query name.
1179 // std::cerr << "Would add: " << id_of_hit << std::endl;
1180 }
1181 }
1182 else // Does not pass the query test. coverage, perfection, Evalue
1183 {
1184 if (accepted_hits_Log_file_name != NULL)
1185 {
1186 fprintf(accepted_hits_log, "Hit not accepted (query-test not passed): %s hc: %.2lf perf: %.3lf e-val: %8lf\n",
1187 sname.c_str(), hit_coverage, hit_perfection, hit_evalue);
1188 }
1189
1190 #ifdef FINANA
1191 std::cerr << "--Hit not accepted (qery-test failed). ";
1192 tmp->print(std::cerr);
1193 #endif
1194 }
1195 }
1196
1197 } // End if (sname != lastname)
1198
1199 ++it;
1200 } // END while (it != it_end)
1201
1202 if (accepted_hits_Log_file_name != NULL)
1203 {
1204 fclose(accepted_hits_log);
1205 }
1206 }
1207
1208
1209 // Typical application:
1210 // For a given query, the best hit has an Evalue of e-12,
1211 // the second best hit has an Evalue of e-10.
1212 // This indicates two independent good hits for the same query.
1213 // These hits shall be saved in the double_hits data structure.
1214
1215 // Mode 0:
1216 // First hit has fixed Evalue threshold.
1217 // Second hit has a floating threshold depending on the the Evalue of the first hit.
1218 // Mode 1:
1219 // First and second hits have fixed Evalue thresholds.
1220 // This mode makes more sense. Example: First hit: E=10^-90
1221 // Second hits needs e.g. 10^-87, while 10^-10 is already more than significant.
1222
1223 // Depricated function name detect_2_target_hits
1224 void detect_2_target_hits(double max_e_1, double max_e_2, CBlast_parser &double_hits, int mode=1)
1225 {
1226 detect_2_good_hits_per_query(max_e_1, max_e_2, double_hits, mode);
1227 }
1228
1229 void detect_2_good_hits_per_query(double max_e_1, double max_e_2, CBlast_parser &double_hits, int mode=1)
1230 {
1231 // Sort by query name, then by e-value.
1232 // Filter all those with e < max_e and e < best-hit-this-query * factor_max_decrease
1233
1234 sort_by_query_name_quality();
1235 // lbh.sort(less_than_CBlastHit_pointer_query_quality);
1236
1237 std::list<CBlastHit*>::iterator it, it_end, tmp;
1238 it = lbh.begin();
1239 it_end = lbh.end();
1240
1241 faststring last_hit_query = "";
1242 double best_e_value_this_query = 100; // Initialised to avoid a warning. The code below should always assign a value to it before it is used.
1243 // This should be the case, since it is only used if (this_hit_query == last_hit_query) which should only be
1244 // the case if it has been assigned a value.
1245 bool still_increment_it;
1246
1247 // mode 0:
1248 // First hit threshold: max_e_1
1249 // Second hit threshold: factor_max_decrease*best_e_value_this_query (factor_max_decrease := max_e_2)
1250
1251 if (mode == 0)
1252 {
1253 while (it != it_end)
1254 {
1255 faststring this_hit_query = (*it)->get_query_seq_name();
1256 double this_hit_e = (*it)->get_evalue();
1257 double factor_max_decrease = max_e_2;
1258
1259 still_increment_it = true;
1260
1261 if (this_hit_query == last_hit_query) // Still the same query
1262 {
1263 //
1264 if (best_e_value_this_query < max_e_1 &&
1265 this_hit_e < best_e_value_this_query*factor_max_decrease)
1266 {
1267 double_hits.add(*it);
1268 it = lbh.erase(it); // This line does an implicit ++it
1269 still_increment_it = false;
1270 }
1271
1272 if (this_hit_e < best_e_value_this_query)
1273 {
1274 // Should never happen since this list is sorted.
1275 std::cerr << "Error better Evalue found: ";
1276 (*it)->print(std::cerr);
1277 std::cerr << std::endl;
1278 exit(-1);
1279 }
1280 }
1281 else // New query. We store the new reference data.
1282 {
1283 // Must be best hit this query
1284 last_hit_query = this_hit_query;
1285 best_e_value_this_query = this_hit_e;
1286 }
1287 if (still_increment_it)
1288 ++it;
1289 }
1290 }
1291 // mode 1:
1292 // First hit threshold: max_e_1
1293 // Second hit threshold: max_e_2
1294
1295 else if (mode == 1)
1296 {
1297
1298 while (it != it_end)
1299 {
1300 faststring this_hit_query = (*it)->get_query_seq_name();
1301 double this_hit_e = (*it)->get_evalue();
1302
1303 still_increment_it = true;
1304
1305 if (this_hit_query == last_hit_query) // Still the same query
1306 {
1307 //
1308 if ( best_e_value_this_query < max_e_1 &&
1309 this_hit_e < max_e_2 )
1310 {
1311 double_hits.add(*it);
1312 it = lbh.erase(it); // This line does an implicit ++it
1313 still_increment_it = false;
1314 }
1315
1316 if (this_hit_e < best_e_value_this_query)
1317 {
1318 // Should never happen since this list is sorted.
1319 std::cerr << "Error better Evalue found: ";
1320 (*it)->print(std::cerr);
1321 std::cerr << std::endl;
1322 exit(-1);
1323 }
1324 }
1325 else // New query. We store the new reference data.
1326 {
1327 // Must be best hit this query
1328 last_hit_query = this_hit_query;
1329 best_e_value_this_query = this_hit_e;
1330 }
1331 if (still_increment_it)
1332 ++it;
1333 }
1334 }
1335 else
1336 {
1337 std::cerr << "Intern error: Unknown mode in detect_2_target_hits" << std::endl;
1338 exit(-2);
1339 }
1340 }
1341
1342
1343 // The reverse mode needs to be revised. CSeqNameList does not allow to add redundant elements since
1344 // redundant entries are not handled in a save way at the moment.
1345
1346
1347 /*
1348 void filter_CSeqNameList_with_major_reverse_blast_hit(CSeqNameList &orig, CSeqNameList &result_with,
1349 double min_query_prop, double min_perfection, double max_evalue, bool multi=true)
1350 // The multi paramter determines whether multiple entries are made if the target sequence has multiple hits.
1351 // Multiple hits of the query are often not of interest, but multiple hits to the same target should usually be considered as independent.
1352 {
1353 std::cerr << "Called filter_CSeqNameList_with_major_reverse_blast_hit and multi=" << multi << std::endl;
1354
1355 // compute_coverage_map();
1356
1357 std::list<CBlastHit*>::iterator it, it_end;
1358
1359 sort_target(); // This guarantees that hits are ordered by query name.
1360 // This will be used here.
1361
1362 it = lbh.begin();
1363 it_end = lbh.end();
1364
1365 // List of seq names:
1366 unsigned id_of_hit;
1367
1368 // std::map<faststring *, unsigned, less_than_pointer_to_faststring_struct>::iterator it_find;
1369
1370 CBlastHit* tmp;
1371
1372 faststring sname;
1373 faststring lastname;
1374
1375 // We move through all Blast hits:
1376 while (it != it_end)
1377 {
1378 tmp = *it;
1379
1380 unsigned seq_len;
1381 unsigned hit_len;
1382 double hit_coverage;
1383 double hit_perfection;
1384 double hit_evalue;
1385
1386 // Get name of target:
1387 sname = tmp->get_target_seq_name();
1388
1389 // std::cerr << "Target sequence name: " << sname << std::endl;
1390
1391 if (multi || sname != lastname) // In contrast to the forward direction we usually want to keep multiple hits against the target.
1392 // If it has been added (see below) we won't check hits with the same query name
1393 // Here we need that the sequences are ordered - hits to the same sequence are successors.
1394 {
1395 id_of_hit = orig.get_id_short_name(sname); // Look up the name in the list of sequences in the fasta file.
1396
1397 // std::cerr << "sname " << sname << " " << id_of_hit << std::endl;
1398
1399 if (id_of_hit == UINT_MAX)
1400 {
1401 std::cerr << "Error: Could not find sequence name: "
1402 << sname
1403 << " for which a blast hit (target) has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!"
1404 << std::endl;
1405 }
1406 else // Sequence of blast hit has been found
1407 {
1408 seq_len = orig.get_seq_length(id_of_hit);
1409
1410 // hit_len = tmp->get_length();
1411 // length might be wrong for protein / nucleotide balsts
1412
1413 // We need to add 1 since the end is the last index in hit range.
1414
1415 hit_len = tmp->get_end_target() - tmp->get_start_target() +1;
1416
1417
1418 hit_perfection = tmp->get_perfection();
1419 hit_evalue = tmp->get_evalue();
1420
1421 hit_coverage = (double)hit_len/seq_len;
1422
1423 if (hit_coverage >= min_query_prop && hit_perfection >= min_perfection && hit_evalue <= max_evalue)
1424 {
1425 // This is an accepted hit:
1426 // result_with.add_non_redundant(orig,id_of_hit);
1427 result_with.add(orig,id_of_hit); // multi=true allows redundant entries.
1428 if (!multi)
1429 lastname = sname; // In case we add the hit, we will ignore other blast hits with the same target name.
1430 // std::cerr << "Would add: " << id_of_hit << std::endl;
1431 }
1432 else
1433 {
1434 std::cerr << "--Hit not accepted (target test). ID: " << id_of_hit << std::endl;
1435 }
1436 }
1437
1438 } // End if (sname != lastname)
1439
1440 ++it;
1441 } // END while (it != it_end)
1442
1443 } // END filter_CSeqNameList_with_major_reverse_blast_hit
1444 */
1445
1446 // Input: CSeqNameList of all query names
1447 // Putput: CSeqNameList of all query names that have a blast hit in *this.
1448
1449 void filter_CSeqNameList_has_simple_hit(CSeqNameList &orig, CSeqNameList &result_with)
1450 {
1451 std::list<CBlastHit*>::iterator it, it_end;
1452
1453 sort_by_query_name_quality();
1454 // sort_query(); // This guarantees that hits are ordered by query name.
1455 // This simplifies the further algorithm.
1456 //
1457
1458 it = lbh.begin();
1459 it_end = lbh.end();
1460
1461 // List of seq names:
1462 unsigned id_of_hit;
1463
1464 CBlastHit* tmp;
1465
1466 faststring query_name;
1467 faststring last_query_name;
1468
1469 // We move through all Blast hits:
1470 // - we fetch the sequence name and copy the data to the new CSeqNameList.
1471
1472 while (it != it_end)
1473 {
1474 tmp = *it;
1475
1476 // Get name of query of blast hit:
1477 query_name = tmp->get_query_seq_name();
1478
1479 if (query_name != last_query_name) // We never want to add the same sequence twice.
1480 {
1481 // Look up the name of the query in the list of sequences in the fasta file.
1482 // Remember: blast tells us the short name only.
1483 id_of_hit = orig.get_id_short_name(query_name);
1484
1485 // std::cerr << "query_name " << query_name << " " << id_of_hit << std::endl;
1486
1487 if (id_of_hit == UINT_MAX)
1488 {
1489 std::cerr << "Error: Could not find sequence name: "
1490 << query_name
1491 << " for which a blast hit has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!"
1492 << std::endl;
1493 }
1494 else // Sequence of blast hit has been found
1495 {
1496 // This is an accepted hit:
1497 result_with.add_non_redundant(orig, id_of_hit);
1498 last_query_name = query_name;
1499 }
1500
1501 } // End if (sname != lastname)
1502
1503 ++it;
1504 } // END while (it != it_end)
1505 }
1506
1507
1508
1509 void compute_coverage_map(double min_perfection, double max_e_value)
1510 {
1511 std::cerr << "Started to compute coverage values" << std::endl;
1512
1513 sort_by_query_name_quality();
1514 // sort_query(); // Sort by query name and coordinates
1515
1516 std::list<CBlastHit*>::iterator it, it2, it_end;
1517 it = lbh.begin();
1518 it_end = lbh.end();
1519
1520 const faststring *current_query, *last_query;
1521
1522 last_query = NULL;
1523 current_query = NULL;
1524
1525 if (it == it_end)
1526 {
1527 return;
1528 }
1529
1530 CRangeList rl_current_query;
1531 Crange r_all(0, UINT_MAX);
1532 unsigned cov;
1533
1534 // Move through all hits:
1535 while (it != it_end)
1536 {
1537 // Get sequence name of query of this hit.
1538 current_query = &((**it).get_query_seq_name());
1539
1540 if (last_query && *current_query != *last_query) // next query - not for first!
1541 {
1542 // Save coverage of last query
1543 cov = rl_current_query.coverage_len(r_all);
1544
1545 // current_query is the next query so last_query contains the correct name for this:
1546 std::cerr << *last_query << " cov: " << cov << std::endl;
1547
1548 total_coverage_map[*last_query] = cov;
1549
1550 // Clear range list:
1551 rl_current_query.clear();
1552 }
1553
1554 // For all queries, We have to add all hits that meet the criteria to the list of ranges: rl_current_query
1555 // We add this hit:
1556 // Remember: The blast result contains the last position in the range so we have to add one.
1557
1558 // Let us check the criteria before we add the hit:
1559 if ((**it).get_evalue() <= max_e_value && (**it).get_perfection() >= min_perfection)
1560 {
1561 rl_current_query.add((**it).get_start_query(), (**it).get_end_query()+1 );
1562
1563 std::cerr << "Adding to range of " << *current_query << " "
1564 << (**it).get_start_query() << " " << (**it).get_end_query()+1 << std::endl;
1565 }
1566 else
1567 {
1568 std::cerr << "Not adding to range of " << *current_query << " "
1569 << (**it).get_start_query() << " " << (**it).get_end_query()+1 << std::endl;
1570 }
1571
1572 ++it;
1573 last_query = current_query;
1574 }
1575 // After exiting we have to save the last query-sequence:
1576 cov = rl_current_query.coverage_len(r_all);
1577 std::cerr << *last_query << " cov: " << cov << std::endl;
1578 total_coverage_map[*last_query] = cov;
1579
1580 // std::cerr << "Coverage map computed- " << std::endl;
1581
1582 std::cerr << "Finished computing coverage values" << std::endl;
1583 }
1584
1585 /*
1586 std::list<CBlastHit*>::iterator blc_lower_bound(faststring &value)
1587 {
1588
1589 std::list<CBlastHit*>::iterator it, first;
1590 unsigned count, step;
1591 count = std::distance(lbh.begin(), lbh.end());
1592 first = lbh.begin();
1593
1594 while (count > 0)
1595 {
1596 it = first;
1597 step = count / 2;
1598 std::advance(it, step);
1599 if ((**it).get_query_seq_name() < value)
1600 {
1601 first = ++it;
1602 count -= step + 1;
1603 }
1604 else
1605 {
1606 count = step;
1607 }
1608 }
1609 return first;
1610 }
1611
1612 //
1613 // Search all blast hits that have a query name that begins identical to the query_beginning_match_str
1614 // and determine the maximum hit length in this set.
1615 // More formally: Search for all hits with a query that is identical to query_beginning_match_str
1616 // when restricted to the first query_beginning_match_str.size() characters.
1617 int get_max_hit_query_span__matching_beginning1(faststring &query_beginning_match_str)
1618 {
1619 int max_len;
1620
1621 std::cout << "Entering: get_max_hit_query_span__matching_beginning1 with " << query_beginning_match_str << std::endl;
1622
1623 sort_by_query_name_quality();
1624
1625 // Find first hit which start with the search string:
1626 std::list<CBlastHit*>::iterator it, it_end;
1627 it = blc_lower_bound(query_beginning_match_str);
1628 it_end = lbh.end();
1629
1630 if (it == it_end)
1631 {
1632 std::cout << "No hit found (p1) for partial name of query: " << query_beginning_match_str
1633 << std::endl;
1634 return -1;
1635 }
1636
1637 // If there is no Blast hit for the query with this name,
1638 // it can be but in most cases will not be equal to it_end
1639 // The definitive check is that it points to a hit that matches
1640
1641 if (fstrncmp(query_beginning_match_str, (**it).get_query_seq_name(),query_beginning_match_str.size() ) != 0)
1642 {
1643 std::cout << "No hit found (p2) for partial name of query: " << query_beginning_match_str
1644 << std::endl;
1645 return -2;
1646 }
1647
1648 max_len = (**it).get_query_span();
1649 ++it;
1650
1651 while (it != it_end)
1652 {
1653 // If the strings to not match over the length of query_beginning_match_str.size(), we break
1654 if (fstrncmp(query_beginning_match_str, (**it).get_query_seq_name(),query_beginning_match_str.size() ) != 0)
1655 break;
1656 // If they are still equal over the length of query_beginning_match_str.size(),
1657 if ( (int)(**it).get_query_span() > max_len)
1658 max_len = (int)(**it).get_query_span();
1659 ++it;
1660 }
1661
1662 std::cout << "Found partial name of query: " << query_beginning_match_str
1663 << " " << max_len << std::endl;
1664
1665 return max_len;
1666 }
1667 */
1668
1669
1670 int get_max_hit_query_span__matching_beginning2(faststring &query_beginning_match_str, unsigned verbosity)
1671 {
1672 int max_len;
1673
1674 if (verbosity > 100)
1675 std::cout << "Entering: get_max_hit_query_span__matching_beginning2 with " << query_beginning_match_str << std::endl;
1676
1677 // Find first hit which start with the search string:
1678 std::multimap<faststring, CBlastHit*>::iterator it, it_end;
1679 it = bh_map.lower_bound(query_beginning_match_str);
1680 it_end = bh_map.end();
1681
1682 if (it == it_end)
1683 {
1684 if (verbosity > 100)
1685 {
1686 std::cout << "No hit found (p1) for partial name of query: " << query_beginning_match_str
1687 << std::endl;
1688 }
1689 return -1;
1690 }
1691
1692 // If there is no Blast hit for the query with this name,
1693 // the iterator it can be but in most cases will not be equal to it_end
1694 // The definitive check is that it points to a hit that matches
1695
1696 if (fstrncmp(query_beginning_match_str, (it->second)->get_query_seq_name(),query_beginning_match_str.size() ) != 0)
1697 {
1698 if (verbosity > 100)
1699 {
1700 std::cout << "No hit found (p2) for partial name of query: " << query_beginning_match_str
1701 << std::endl;
1702 }
1703 return -2;
1704 }
1705
1706 max_len = (it->second)->get_query_span();
1707 ++it;
1708
1709 while (it != it_end)
1710 {
1711 // If the strings to not match over the length of query_beginning_match_str.size(), we break
1712 if (fstrncmp(query_beginning_match_str, (it->second)->get_query_seq_name(),query_beginning_match_str.size() ) != 0)
1713 break;
1714 // If they are still equal over the length of query_beginning_match_str.size(),
1715 if ( (int)(it->second)->get_query_span() > max_len)
1716 max_len = (int)(it->second)->get_query_span();
1717 ++it;
1718 }
1719
1720 if (verbosity > 100)
1721 {
1722 std::cout << "Found partial name of query: " << query_beginning_match_str
1723 << " " << max_len << std::endl;
1724 }
1725
1726 return max_len;
1727 }
1728
1729
1730
1731 void set_of_gi_numbers_target(std::set<unsigned> &gi_set)
1732 {
1733 std::list<CBlastHit*>::iterator it, it_end;
1734 it = lbh.begin();
1735 it_end = lbh.end();
1736
1737 faststring tmp_gi;
1738
1739 while (it != it_end)
1740 {
1741 (**it).extract_GI_number_target(tmp_gi);
1742 gi_set.insert(tmp_gi.ToUnsigned());
1743 ++it;
1744 }
1745 }
1746
1747 void set_of_query_names(std::set<faststring> &s)
1748 {
1749 std::list<CBlastHit*>::iterator it, it_end;
1750 it = lbh.begin();
1751 it_end = lbh.end();
1752
1753 while (it != it_end)
1754 {
1755 s.insert( (**it).get_query_seq_name() );
1756 ++it;
1757 }
1758 }
1759
1760 /* void get_max_query_span_map_for_matching_queries(std::map<faststring, int> m, char stop_char, int num_stop_char) */
1761 /* { */
1762
1763 /* } */
1764
1765 void write_set_of_gi_numbers_to_file(const char *fname)
1766 {
1767 std::set<unsigned> gi_set;
1768 set_of_gi_numbers_target(gi_set);
1769 std::set<unsigned>::iterator it,it_end;
1770 it = gi_set.begin();
1771 it_end = gi_set.end();
1772
1773 std::ofstream os(fname);
1774 while (it != it_end)
1775 {
1776 os << *it << std::endl;
1777 ++it;
1778 }
1779 os.close();
1780 } // END write_set_of_gi_numbers_to_file
1781
1782
1783
1784
1785 // fill a map with the following information:
1786 // For all gi numbers of the target sequences, the map contains the number of occurrences of this target.
1787 void get_gi_occurence_map(std::map<unsigned, unsigned> &gim)
1788 {
1789 std::list<CBlastHit*>::iterator it, it_end;
1790 it = lbh.begin();
1791 it_end = lbh.end();
1792
1793 faststring tmp_gi;
1794
1795 while (it != it_end)
1796 {
1797 (**it).extract_GI_number_target(tmp_gi);
1798 __add_or_count(gim, tmp_gi.ToUnsigned());
1799 ++it;
1800 }
1801
1802 }
1803
1804
1805 };
1806
1807 #endif