/* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits * BaitFilter (version 1.0.6) a program for selecting optimal bait regions * Copyright 2013-2017 by Christoph Mayer * * This source file is part of the BaitFisher-package. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with BaitFisher. If not, see . * * * For any enquiries send an Email to Christoph Mayer * c.mayer.zfmk@uni-bonn.de * * When publishing work that is based on the results please cite: * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design * */ // Some parts of this header file could be made more efficient. // Much of the functionality relies on a sorted list of Blast hits. // The question arises whether a list is the best data structure for such // a purpose. It could be more efficient to use a data structure such as // a set, which is sorted automatically and which should in principle be // more efficient. // GI number will not be supported by NCBI in the future! So far we have not removed the code. // This should be done soon. #ifndef CBLASTPARSER_H #define CBLASTPARSER_H // The following two defines allow us to use fopen() in "CSeqNameList.h" // without error message when using the Visual Studio 2015 compiler. #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_NO_WARNINGS #include #include "CFile/CFile2_1.h" #include "faststring2.h" #include #include #include #include "CSeqNameList.h" #include "range_functions.h" #include "CHistogram.h" #include "typedefs.h" #include class CTaxonomy; class CBlastHit; // Forward declaration of friend functions in order to make them globally visible (friend injection problem): bool less_than_CBlastHit_query(const CBlastHit &a, const CBlastHit &b); bool less_than_CBlastHit_query_quality(const CBlastHit &a, const CBlastHit &b); bool less_than_CBlastHit_target(const CBlastHit &a, const CBlastHit &b); bool operator<(const CBlastHit &a, const CBlastHit &b); bool less_than_CBlastHit_pointer_query(const CBlastHit *a, const CBlastHit *b); bool less_than_CBlastHit_pointer_query_quality(const CBlastHit *a, const CBlastHit *b); bool less_than_CBlastHit_pointer_target(const CBlastHit *a, const CBlastHit *b); signed char CB_is_gi_of_type(CTaxonomy *tax, unsigned gi, unsigned type); struct struct_less_than_CBlastHit_pointer_query_quality { bool operator()(const CBlastHit *a, const CBlastHit *b) { return less_than_CBlastHit_pointer_query_quality(a,b); } }; static void __add_or_count(std::map &m, unsigned x) { std::map::iterator it; it = m.find(x); if (it == m.end() ) { m[x] = 1; } else { ++it->second; } } /* //Not used in most applications. Not tested yet. Needs to be tested before it is used. static void majority_rule(std::vector v, int &val, double &prop) { CHistogram h(v, -10); double value; h.dominant_category(value, prop); val = (int)(value+0.5); // Adding 0.5 ensures we are not returning a wrong int due to // rounding errors. } */ class CBlastHit { private: unsigned internal_number; faststring target_seq_name; faststring query_seq_name; double perfection; unsigned length; unsigned mismatches; unsigned gaps; bool reverse_query; bool reverse_target; unsigned start_query; unsigned end_query; unsigned start_target; unsigned end_target; double e_value; double score; public: CBlastHit(const faststring& line, unsigned in):internal_number(in) { std::vector v; split(v, line); // std::cout << v.size() << std::endl; if (v.size() == 12) { query_seq_name = v[0]; target_seq_name = v[1]; perfection = v[2].ToDouble(); length = v[3].ToUnsigned(); mismatches = v[4].ToUnsigned(); gaps = v[5].ToUnsigned(); start_query = v[6].ToUnsigned(); end_query = v[7].ToUnsigned(); // std::cerr << "Identfied start_query: " << start_query << std::endl; // std::cerr << "Identfied end_query: " << end_query << std::endl; start_target = v[8].ToUnsigned(); end_target = v[9].ToUnsigned(); e_value = v[10].ToDouble(); score = v[11].ToDouble(); if (start_query > end_query) { reverse_query= true; unsigned tmp; tmp = start_query; start_query = end_query; end_query = tmp; } else reverse_query= false; if (start_target > end_target) { reverse_target = true; unsigned tmp; tmp = start_target; start_target = end_target; end_target = tmp; } else reverse_target= false; } else { std::cerr << "Unrecognised line of input passed to CBlastHit constructor: " << line << "\n"; } } double get_perfection() { return perfection; } unsigned get_length() { return length; } unsigned get_query_span() { if (end_query >= start_query) return end_query - start_query+1; else return start_query - end_query+1; } // Searches for gi|xxxxxxxx| in the query sequence and returns the xxx string. void extract_GI_number_query(faststring &gi) { faststring::size_t pos1 = query_seq_name.find("gi|"); faststring::size_t pos2; if (pos1 != faststring::npos) { pos2 = query_seq_name.find("|", pos1+3); if (pos2 == faststring::npos) // No proper gi number found so we return empty string; { gi.clear(); return; } gi = query_seq_name.substr(pos1+3, pos2-pos1-3); return; } else // No proper gi number found so we return empty string; { gi.clear(); return; } } void extract_GI_number_target(faststring &gi) { faststring::size_t pos1 = target_seq_name.find("gi|"); faststring::size_t pos2; if (pos1 != faststring::npos) { pos2 = target_seq_name.find("|", pos1+3); if (pos2 == faststring::npos) // No proper gi number found so we return empty string; { gi.clear(); return; } gi = target_seq_name.substr(pos1+3, pos2-pos1-3); return; } else // No proper gi number found so we return empty string; { gi.clear(); return; } } double get_evalue() { return e_value; } unsigned get_start_query() { return start_query; } unsigned get_end_query() { return end_query; } unsigned get_start_target() { return start_target; } unsigned get_end_target() { return end_target; } const faststring &get_query_seq_name() { return query_seq_name; } const faststring &get_target_seq_name() { return target_seq_name; } friend bool less_than_CBlastHit_query(const CBlastHit &a, const CBlastHit &b) { // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection // a.print(std::cerr); // b.print(cerr); // Primary criterion: Query seq name: if (a.query_seq_name != b.query_seq_name) return a.query_seq_name < b.query_seq_name; if (a.start_query != b.start_query) return a.start_query < b.start_query; if (a.end_query != b.end_query) return a.end_query < b.end_query; if (a.target_seq_name != b.target_seq_name) return a.target_seq_name < b.target_seq_name; if (a.start_target != b.start_target) return a.start_target < b.start_target; if (a.end_target != b.end_target) return a.end_target < b.end_target; // They should be irrelevant since we would have multiple identical hits // if we come here. if (a.length != b.length) return a.length < b.length; // if (a.perfection != b.perfection) // Including this line is a bug. This was a bug. return a.perfection < b.perfection; } friend bool less_than_CBlastHit_query_quality(const CBlastHit &a, const CBlastHit &b) { // First criterion: name of query sequence: ascending (smaller is "better") // Second criterion: e_value ascending (smaller is better) // Third criterion: score descending (higher is better) // Fourth criterion: perfection descending (higher is better) // Fifth criterion: sequence positions // Sixth criterion: target sequence name and positions // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection // a.print(std::cerr); // b.print(cerr); // Primary criterion: Query seq name: if (a.query_seq_name != b.query_seq_name) return a.query_seq_name < b.query_seq_name; // Secondary criterion: e_value if (a.e_value != b.e_value) return a.e_value < b.e_value; if (a.score != b.score) return a.score > b.score; if (a.perfection != b.perfection) return a.perfection > b.perfection; if (a.start_query != b.start_query) return a.start_query < b.start_query; if (a.end_query != b.end_query) return a.end_query < b.end_query; if (a.target_seq_name != b.target_seq_name) return a.target_seq_name < b.target_seq_name; if (a.start_target != b.start_target) return a.start_target < b.start_target; if (a.end_target != b.end_target) return a.end_target < b.end_target; // They should be irrelevant since we would have multiple identical hits // if we come here. // if (a.length != b.length) // Including this line is a bug. This was a bug. return a.length < b.length; } friend bool less_than_CBlastHit_target(const CBlastHit &a, const CBlastHit &b) { // sort first by -query name, -query start, -query end, - target name, target start, target end, -length, -perfection // a.print(std::cerr); // b.print(cerr); // Primary criterion: Target seq name: if (a.target_seq_name != b.target_seq_name) return a.target_seq_name < b.target_seq_name; if (a.start_target != b.start_target) return a.start_target < b.start_target; if (a.end_target != b.end_target) return a.end_target < b.end_target; if (a.query_seq_name != b.query_seq_name) return a.query_seq_name < b.query_seq_name; if (a.start_query != b.start_query) return a.start_query < b.start_query; if (a.end_query != b.end_query) return a.end_query < b.end_query; // They should be irrelevant since we would have multiple identical hits // if we come here. if (a.length != b.length) return a.length < b.length; // if (a.perfection != b.perfection) // Including this line is a bug. This was a bug. return a.perfection < b.perfection; } friend bool operator<(const CBlastHit &a, const CBlastHit &b) { // std::cout << "---------------" << std::endl; return less_than_CBlastHit_query(a,b); } friend bool less_than_CBlastHit_pointer_query(const CBlastHit *a, const CBlastHit *b) { return (*a < *b); } friend bool less_than_CBlastHit_pointer_query_quality(const CBlastHit *a, const CBlastHit *b) { return (less_than_CBlastHit_query_quality(*a, *b)); } friend bool less_than_CBlastHit_pointer_target(const CBlastHit *a, const CBlastHit *b) { return (less_than_CBlastHit_target(*a, *b)); } void print(std::ostream &os, char delim = '\t') const { os << internal_number << delim; os << query_seq_name << delim; os << target_seq_name << delim; os << perfection << delim; os << length << delim; os << mismatches << delim; os << gaps << delim; os << start_query << delim; os << end_query << delim; os << start_target << delim; os << end_target << delim; os << e_value << delim; os << score; os << '\n'; } void print(std::ostream &os, bool pinternal_number, bool pqueryname, bool ptargetname, bool pperfection, bool plength, bool pmismatches, bool pgaps, bool pstart_query, bool pend_query, bool pstart_target, bool pend_target, bool pe_value, bool pscore, char delim = '\t') const { if (pinternal_number) os << internal_number << delim; if (pqueryname) os << query_seq_name << delim; if (ptargetname) os << target_seq_name << delim; if (pperfection) os << perfection << delim; if (plength) os << length << delim; if (pmismatches) os << mismatches << delim; if (pgaps) os << gaps << delim; if (pstart_query) os << start_query << delim; if (pend_query) os << end_query << delim; if (pstart_target) os << start_target << delim; if (pend_target) os << end_target << delim; if (pe_value) os << e_value << delim; if (pscore) os << score; os << '\n'; } void print_essential_1(std::ostream &os, char delim = '\t') const { os << query_seq_name << delim; os << "E: " << e_value << delim; os << "len: " << length << delim; os << "%: " << perfection << delim; os << '\n'; } }; class CBlast_parser { std::list lbh; // Previous versions of this header file used a map in the declaration of bh_map. // This map is/was only used in the get_max_hit_query_span__matching_beginning2 function. // In a map in which elements are inserted with the insert function we only inserted the first (and best entry) for // each query. This was fine for all cases for which we used this map so far. // However, a multimap has the same functionality and is more secure, since it will store all entries. std::multimap bh_map; // Stores coverage in bp. If query seq. length is known it can be used to determine the relative sequence length. std::map total_coverage_map; bool query_name_quality_sorted; //TODO: add delete in destructor concept to improve performance in some constructors by avoiding to copy the data. void add(CBlastHit* p) { lbh.push_back(p); faststring tmp = p->get_query_seq_name(); bh_map.insert(bh_map.end(), std::make_pair(tmp, p)); } public: CBlast_parser(const char *filename):query_name_quality_sorted(false) { CFile f; faststring line; unsigned counter=0; f.ffopen(filename); #ifdef FINANA std::cerr << "We are in the FINANA mode.\n"; #endif f.getline(line); while (!f.fail() ) { line.removeSpacesFront(); line.removeSpacesBack(); if (!line.empty() && line[0] != '#') // if not a comment - allows us to read the -m 9 in addition to the -m 8 output format { CBlastHit* p = new CBlastHit(line, counter); // Debugging code: // if (counter > 1) // break; ++counter; add(p); } f.getline(line); } } // Default constructor - rarely used. CBlast_parser():query_name_quality_sorted(false) {} ~CBlast_parser() { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); while (it != it_end) { // (**it).print(std::cout); delete *it; ++it; } } // See also keep_only_n_top_hits // Copy constructor that can be used to filter the n first blast hits for a query. // Will be sorted by query name, since the source will be sorted. CBlast_parser(CBlast_parser &b, unsigned n=UINT_MAX):query_name_quality_sorted(true) { b.sort_by_query_name_quality(); std::list::iterator it, it_end; it = b.lbh.begin(); it_end = b.lbh.end(); faststring last_qname; unsigned count = 0; while (it != it_end) { if ((**it).get_query_seq_name() == last_qname) { ++count; } else { count = 1; last_qname = (**it).get_query_seq_name(); } CBlastHit* tmp_copy; if (count <= n) { tmp_copy = new CBlastHit(**it); add(tmp_copy); } ++it; } } // Copy constructor which filters hits that have a specific taxonomy // of the target. CBlast_parser(CBlast_parser &b, CTaxonomy *tax, unsigned type, signed char (*func)(CTaxonomy *, unsigned, unsigned)):query_name_quality_sorted(b.query_name_quality_sorted) { std::list::iterator it, it_end; it = b.lbh.begin(); it_end = b.lbh.end(); unsigned target_gi; faststring tmp; CBlastHit *tmp_copy; signed char res; while (it != it_end) { (**it).extract_GI_number_target(tmp); target_gi = tmp.ToUnsigned(); res = func(tax,target_gi, type); if (res < 0) { std::cerr << "Warning: In CBlast_parser. res < 0.\n"; std::cerr << "GI number seems to be unknown: String: " << tmp << " unsigned: " << target_gi << '\n'; // exit(0); } if (res > 0) { tmp_copy = new CBlastHit(**it); add(tmp_copy); } ++it; } } // Copy constructor which filters hits that have a match in the title field CBlast_parser(CBlast_parser &b, CTaxonomy *tax, std::vector &query_strings, signed char (*func)(CTaxonomy *, unsigned, std::vector &query_strings)):query_name_quality_sorted(b.query_name_quality_sorted) { std::list::iterator it, it_end; it = b.lbh.begin(); it_end = b.lbh.end(); unsigned target_gi; faststring tmp; CBlastHit *tmp_copy; signed char res; while (it != it_end) { (**it).extract_GI_number_target(tmp); target_gi = tmp.ToUnsigned(); res = func(tax,target_gi, query_strings); if (res < 0) { std::cerr << "Error in CBlast_parser. res < 0.\n\n"; exit(0); } if (res > 0) { tmp_copy = new CBlastHit(**it); add(tmp_copy); } ++it; } } void clear() { lbh.clear(); query_name_quality_sorted = false; } unsigned get_hit_count() { return lbh.size(); } void keep_only_n_top_hits(unsigned n=1) { sort_by_query_name_quality(); // lbh.sort(less_than_CBlastHit_pointer_query_quality); std::list::iterator it, it2, it_end; it = lbh.begin(); it_end = lbh.end(); faststring last_name; unsigned i=1; while (it != it_end) { if ( (**it).get_query_seq_name() == last_name ) { ++i; // Count this hit if (i>n) { // Remove *it: delete *it; it = lbh.erase(it); } // it now points to the hit behind the hit that has been removed. // it should not be incremented any more. } else { last_name = (**it).get_query_seq_name(); i=1; ++it; } } } // Remove all hits for func does not return true when given gi: void keep_only_hits_for_which_func_returns_true_for_parameter_gi(CTaxonomy *tax, bool (*func)(CTaxonomy *, unsigned gi), const char *s) { std::list::iterator it, it2, it_end; it = lbh.begin(); it_end = lbh.end(); unsigned gi; faststring tmp; unsigned count = 0; while (it != it_end) { (**it).extract_GI_number_target(tmp); gi = tmp.ToUnsigned(); if (!func(tax, gi)) { std::cerr << s << (**it).get_target_seq_name() << " Gi: " << gi << ". Blast hit will be removed.\n"; ++count; // Remove *it: delete *it; it = lbh.erase(it); } else { ++it; } } std::cerr << "WARNING: Number of blast hits removed since no taxid could be found for gi: " << count << '\n'; } void keep_only_e_select(double max_e, double factor_max_decrease) { // Sort by query name, then by e-value. // Filter all those with e < max_e and e < best-hit-this-query * factor_max_decrease sort_by_query_name_quality(); // lbh.sort(less_than_CBlastHit_pointer_query_quality); std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); faststring last_hit_query = ""; double best_e_value_this_query; bool erase_this; while (it != it_end) { faststring this_hit_query = (*it)->get_query_seq_name(); double this_hit_e = (*it)->get_evalue(); erase_this = false; if (this_hit_e < max_e) { if (this_hit_query == last_hit_query) // Still the same query { // if (this_hit_e > best_e_value_this_query*factor_max_decrease) { erase_this = true; } // else // if "<=" then keep if (this_hit_e < best_e_value_this_query) { // Should never happen since this is sorted. std::cerr << "Error better Evalue found: "; (*it)->print(std::cerr); std::cerr << '\n'; } } else // A new query sequence { // Must be best hit this query last_hit_query = this_hit_query; best_e_value_this_query = this_hit_e; // keep } } // if (this_hit_e < max_e) else // erase { erase_this = true; } // Simple logic to remove this hit. if (erase_this) { delete *it; it = lbh.erase(it); } else { ++it; } } } void print_all(std::ostream &os) { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); while (it != it_end) { (*it)->print(os); ++it; } } void print_all(std::ostream &os, bool pinternal_number, bool pqueryname, bool ptargetname, bool pperfection, bool plength, bool pmismatches, bool pgaps, bool pstart_query, bool pend_query, bool pstart_target, bool pend_target, bool pe_value, bool pscore, char delim = '\t') { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); while (it != it_end) { (*it)->print(os, pinternal_number, pqueryname, ptargetname, pperfection, plength, pmismatches, pgaps, pstart_query, pend_query, pstart_target, pend_target, pe_value, pscore, delim = '\t'); ++it; } } void print_with_title(std::ostream &os, const std::map &gi2title_map) { std::list::iterator it, it_end; faststring tmp; unsigned target_gi; it = lbh.begin(); it_end = lbh.end(); while (it != it_end) { (*it)->print_essential_1(os); os << std::endl; (**it).extract_GI_number_target(tmp); target_gi = tmp.ToUnsigned(); const_iterator_U_Faststring_map find_it; find_it = gi2title_map.find(target_gi); if (find_it != gi2title_map.end() ) { os << find_it->second << std::endl; } else { os << "*** No title available. for gi" << target_gi << " ***" << std::endl; } ++it; } } void sort_by_query_name_quality() { // std::cerr << "RESORT" << std::endl; if (!query_name_quality_sorted) { lbh.sort(less_than_CBlastHit_pointer_query_quality); query_name_quality_sorted = true; } } // Calling this function is discouraged. We recommend to call: // sort_by_query_name_quality(), since this is more efficient // in the case of multiple calls. void sort_query() { lbh.sort(less_than_CBlastHit_pointer_query); query_name_quality_sorted = false; } void sort_target() { lbh.sort(less_than_CBlastHit_pointer_target); query_name_quality_sorted = false; } std::list::iterator begin() { return lbh.begin(); } std::list::iterator end() { return lbh.end(); } /* void erase(std::list::iterator it) { lbh.erase(it); } */ void filter_CSeqNameList_with_major_blast_hit(CSeqNameList &orig, CSeqNameList &result_with, double min_query_prop, double min_perfection, double max_evalue, bool min_query_prop_with_respect_to_all_hits_this_query, const char * accepted_hits_Log_file_name=NULL, CSeqNameList *target_list=NULL, const char * search_expr=NULL) { if ( orig.is_only_names() ) { std::cerr << "Object orig was created with the option ." << std::endl; std::cerr << "I do not know how to proceed." << std::endl; exit(0); } if (min_query_prop_with_respect_to_all_hits_this_query) compute_coverage_map(min_perfection, max_evalue); bool check_target_seq_match = target_list!= NULL && search_expr != NULL; std::list::iterator it, it_end; sort_by_query_name_quality(); // sort_query(); // This guarantees that hits are ordered by query name. // This will be used here. it = lbh.begin(); it_end = lbh.end(); // List of seq names: unsigned id_of_hit; // std::map::iterator it_find; CBlastHit* tmp; faststring sname; // = tmp->get_query_seq_name(); faststring lastname; FILE *accepted_hits_log; if (accepted_hits_Log_file_name != NULL) { accepted_hits_log = fopen(accepted_hits_Log_file_name, "w"); } // We move through all Blast hits: while (it != it_end) { tmp = *it; unsigned seq_len; unsigned hit_len; double hit_coverage; double hit_perfection; double hit_evalue; // Get name of query of blast hit: sname = tmp->get_query_seq_name(); // std::cerr << "Working on hit with sname " << sname << std::endl; if (sname != lastname) // We never want to add the same sequence twice. // If it has been added (see below) we won't check hits with the same query name // If the last hit has not been added lastname // should not have been updated to this name. { // Look up the name of the query in the list of sequences in the fasta file. // Remember: blast tells us the short name only. id_of_hit = orig.get_id_short_name(sname); // std::cerr << "sname " << sname << " id-of-hit " << id_of_hit << std::endl; if (id_of_hit == UINT_MAX) { std::cerr << "Error: Could not find sequence name: " << tmp->get_query_seq_name() << " for which a blast hit has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!" << std::endl; } else // Sequence of blast hit has been found { seq_len = orig.get_seq_length(id_of_hit); // std::cerr << "sname " << sname << " " << id_of_hit << " " << seq_len << std::endl; if (min_query_prop_with_respect_to_all_hits_this_query) { std::map::iterator it_find; it_find = total_coverage_map.find(sname); if (it_find != total_coverage_map.end()) hit_len = it_find->second; else { std::cerr << "Warning: Could not find sequence "<< sname << " in total_coverage_map." << std::endl; hit_len = 0; } } else { // hit_len = tmp->get_length(); // length might be wrong for protein / nucleotide balsts 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. } hit_perfection = tmp->get_perfection(); hit_evalue = tmp->get_evalue(); hit_coverage = (double)hit_len/seq_len; // // std::cerr << "seq-len hit_len coverage "<< sname << " " << seq_len << " " << hit_len << " " << hit_coverage << std::endl; // if (hit_coverage >= min_query_prop && hit_perfection >= min_perfection && hit_evalue <= max_evalue) { // Query test OK!! if (check_target_seq_match) // Do we check the target seq. full name for a match?? { unsigned t_id; faststring target_short_name = tmp->get_target_seq_name(); t_id = target_list->get_id_short_name(target_short_name); faststring target_full_name = target_list->get_name(t_id); // Strange effect: hit_coverage can 1.01 - is this a bug? if (hit_coverage > 1) { std::cerr << "Detected hit_coverage>1: " << hit_coverage << "#" << hit_len << "/" << seq_len << "#" << sname << "#" << target_full_name << std::endl; } faststring::size_t find_pos = target_full_name.find(search_expr); if (find_pos != faststring::npos) // search_expr has been found - we have a match { // This is an accepted hit: if (accepted_hits_Log_file_name != NULL) { 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", sname.c_str(), target_full_name.c_str(), hit_coverage, hit_perfection, hit_evalue); } result_with.add_non_redundant(orig,id_of_hit); lastname = sname; // In case we add the hit, we will ignore other blast hits with the same query name. // In other words: A query with one or more hits is only inserted once. // std::cerr << "Would add: " << id_of_hit << std::endl; } else { if (accepted_hits_Log_file_name != NULL) { fprintf(accepted_hits_log, "Hit not accepted (qT OK but tT failed): %s hc: %.2lf perf: %.3lf e-val: %8lf\n", sname.c_str(), hit_coverage, hit_perfection, hit_evalue); } std::cerr << "--Hit not accepted (qery-test OK, target does not match). Target seq: " << target_full_name << " "; tmp->print(std::cerr); } } else // Do not check target seq full name - so we have an accepted hit { // unsigned t_id; faststring target_short_name = tmp->get_target_seq_name(); // This is an accepted hit: result_with.add_non_redundant(orig, id_of_hit); if (accepted_hits_Log_file_name != NULL) { 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", // fprintf(accepted_hits_log, "Accepted hit (qT OK, no tT): %s hc: %.2lf perf: %.3lf e-val: %8lf\n", sname.c_str(), target_short_name.c_str(), hit_coverage, hit_perfection, hit_evalue); } lastname = sname; // In case we add the hit, we will ignore other blast hits with the same query name. // std::cerr << "Would add: " << id_of_hit << std::endl; } } else // Does not pass the query test. coverage, perfection, Evalue { if (accepted_hits_Log_file_name != NULL) { fprintf(accepted_hits_log, "Hit not accepted (query-test not passed): %s hc: %.2lf perf: %.3lf e-val: %8lf\n", sname.c_str(), hit_coverage, hit_perfection, hit_evalue); } #ifdef FINANA std::cerr << "--Hit not accepted (qery-test failed). "; tmp->print(std::cerr); #endif } } } // End if (sname != lastname) ++it; } // END while (it != it_end) if (accepted_hits_Log_file_name != NULL) { fclose(accepted_hits_log); } } // Typical application: // For a given query, the best hit has an Evalue of e-12, // the second best hit has an Evalue of e-10. // This indicates two independent good hits for the same query. // These hits shall be saved in the double_hits data structure. // Mode 0: // First hit has fixed Evalue threshold. // Second hit has a floating threshold depending on the the Evalue of the first hit. // Mode 1: // First and second hits have fixed Evalue thresholds. // This mode makes more sense. Example: First hit: E=10^-90 // Second hits needs e.g. 10^-87, while 10^-10 is already more than significant. // Depricated function name detect_2_target_hits void detect_2_target_hits(double max_e_1, double max_e_2, CBlast_parser &double_hits, int mode=1) { detect_2_good_hits_per_query(max_e_1, max_e_2, double_hits, mode); } void detect_2_good_hits_per_query(double max_e_1, double max_e_2, CBlast_parser &double_hits, int mode=1) { // Sort by query name, then by e-value. // Filter all those with e < max_e and e < best-hit-this-query * factor_max_decrease sort_by_query_name_quality(); // lbh.sort(less_than_CBlastHit_pointer_query_quality); std::list::iterator it, it_end, tmp; it = lbh.begin(); it_end = lbh.end(); faststring last_hit_query = ""; 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. // This should be the case, since it is only used if (this_hit_query == last_hit_query) which should only be // the case if it has been assigned a value. bool still_increment_it; // mode 0: // First hit threshold: max_e_1 // Second hit threshold: factor_max_decrease*best_e_value_this_query (factor_max_decrease := max_e_2) if (mode == 0) { while (it != it_end) { faststring this_hit_query = (*it)->get_query_seq_name(); double this_hit_e = (*it)->get_evalue(); double factor_max_decrease = max_e_2; still_increment_it = true; if (this_hit_query == last_hit_query) // Still the same query { // if (best_e_value_this_query < max_e_1 && this_hit_e < best_e_value_this_query*factor_max_decrease) { double_hits.add(*it); it = lbh.erase(it); // This line does an implicit ++it still_increment_it = false; } if (this_hit_e < best_e_value_this_query) { // Should never happen since this list is sorted. std::cerr << "Error better Evalue found: "; (*it)->print(std::cerr); std::cerr << std::endl; exit(-1); } } else // New query. We store the new reference data. { // Must be best hit this query last_hit_query = this_hit_query; best_e_value_this_query = this_hit_e; } if (still_increment_it) ++it; } } // mode 1: // First hit threshold: max_e_1 // Second hit threshold: max_e_2 else if (mode == 1) { while (it != it_end) { faststring this_hit_query = (*it)->get_query_seq_name(); double this_hit_e = (*it)->get_evalue(); still_increment_it = true; if (this_hit_query == last_hit_query) // Still the same query { // if ( best_e_value_this_query < max_e_1 && this_hit_e < max_e_2 ) { double_hits.add(*it); it = lbh.erase(it); // This line does an implicit ++it still_increment_it = false; } if (this_hit_e < best_e_value_this_query) { // Should never happen since this list is sorted. std::cerr << "Error better Evalue found: "; (*it)->print(std::cerr); std::cerr << std::endl; exit(-1); } } else // New query. We store the new reference data. { // Must be best hit this query last_hit_query = this_hit_query; best_e_value_this_query = this_hit_e; } if (still_increment_it) ++it; } } else { std::cerr << "Intern error: Unknown mode in detect_2_target_hits" << std::endl; exit(-2); } } // The reverse mode needs to be revised. CSeqNameList does not allow to add redundant elements since // redundant entries are not handled in a save way at the moment. /* void filter_CSeqNameList_with_major_reverse_blast_hit(CSeqNameList &orig, CSeqNameList &result_with, double min_query_prop, double min_perfection, double max_evalue, bool multi=true) // The multi paramter determines whether multiple entries are made if the target sequence has multiple hits. // Multiple hits of the query are often not of interest, but multiple hits to the same target should usually be considered as independent. { std::cerr << "Called filter_CSeqNameList_with_major_reverse_blast_hit and multi=" << multi << std::endl; // compute_coverage_map(); std::list::iterator it, it_end; sort_target(); // This guarantees that hits are ordered by query name. // This will be used here. it = lbh.begin(); it_end = lbh.end(); // List of seq names: unsigned id_of_hit; // std::map::iterator it_find; CBlastHit* tmp; faststring sname; faststring lastname; // We move through all Blast hits: while (it != it_end) { tmp = *it; unsigned seq_len; unsigned hit_len; double hit_coverage; double hit_perfection; double hit_evalue; // Get name of target: sname = tmp->get_target_seq_name(); // std::cerr << "Target sequence name: " << sname << std::endl; if (multi || sname != lastname) // In contrast to the forward direction we usually want to keep multiple hits against the target. // If it has been added (see below) we won't check hits with the same query name // Here we need that the sequences are ordered - hits to the same sequence are successors. { id_of_hit = orig.get_id_short_name(sname); // Look up the name in the list of sequences in the fasta file. // std::cerr << "sname " << sname << " " << id_of_hit << std::endl; if (id_of_hit == UINT_MAX) { std::cerr << "Error: Could not find sequence name: " << sname << " for which a blast hit (target) has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!" << std::endl; } else // Sequence of blast hit has been found { seq_len = orig.get_seq_length(id_of_hit); // hit_len = tmp->get_length(); // length might be wrong for protein / nucleotide balsts // We need to add 1 since the end is the last index in hit range. hit_len = tmp->get_end_target() - tmp->get_start_target() +1; hit_perfection = tmp->get_perfection(); hit_evalue = tmp->get_evalue(); hit_coverage = (double)hit_len/seq_len; if (hit_coverage >= min_query_prop && hit_perfection >= min_perfection && hit_evalue <= max_evalue) { // This is an accepted hit: // result_with.add_non_redundant(orig,id_of_hit); result_with.add(orig,id_of_hit); // multi=true allows redundant entries. if (!multi) lastname = sname; // In case we add the hit, we will ignore other blast hits with the same target name. // std::cerr << "Would add: " << id_of_hit << std::endl; } else { std::cerr << "--Hit not accepted (target test). ID: " << id_of_hit << std::endl; } } } // End if (sname != lastname) ++it; } // END while (it != it_end) } // END filter_CSeqNameList_with_major_reverse_blast_hit */ // Input: CSeqNameList of all query names // Putput: CSeqNameList of all query names that have a blast hit in *this. void filter_CSeqNameList_has_simple_hit(CSeqNameList &orig, CSeqNameList &result_with) { std::list::iterator it, it_end; sort_by_query_name_quality(); // sort_query(); // This guarantees that hits are ordered by query name. // This simplifies the further algorithm. // it = lbh.begin(); it_end = lbh.end(); // List of seq names: unsigned id_of_hit; CBlastHit* tmp; faststring query_name; faststring last_query_name; // We move through all Blast hits: // - we fetch the sequence name and copy the data to the new CSeqNameList. while (it != it_end) { tmp = *it; // Get name of query of blast hit: query_name = tmp->get_query_seq_name(); if (query_name != last_query_name) // We never want to add the same sequence twice. { // Look up the name of the query in the list of sequences in the fasta file. // Remember: blast tells us the short name only. id_of_hit = orig.get_id_short_name(query_name); // std::cerr << "query_name " << query_name << " " << id_of_hit << std::endl; if (id_of_hit == UINT_MAX) { std::cerr << "Error: Could not find sequence name: " << query_name << " for which a blast hit has been found in fasta file. I guess the files are incompatible or target and query are interchanged!!" << std::endl; } else // Sequence of blast hit has been found { // This is an accepted hit: result_with.add_non_redundant(orig, id_of_hit); last_query_name = query_name; } } // End if (sname != lastname) ++it; } // END while (it != it_end) } void compute_coverage_map(double min_perfection, double max_e_value) { std::cerr << "Started to compute coverage values" << std::endl; sort_by_query_name_quality(); // sort_query(); // Sort by query name and coordinates std::list::iterator it, it2, it_end; it = lbh.begin(); it_end = lbh.end(); const faststring *current_query, *last_query; last_query = NULL; current_query = NULL; if (it == it_end) { return; } CRangeList rl_current_query; Crange r_all(0, UINT_MAX); unsigned cov; // Move through all hits: while (it != it_end) { // Get sequence name of query of this hit. current_query = &((**it).get_query_seq_name()); if (last_query && *current_query != *last_query) // next query - not for first! { // Save coverage of last query cov = rl_current_query.coverage_len(r_all); // current_query is the next query so last_query contains the correct name for this: std::cerr << *last_query << " cov: " << cov << std::endl; total_coverage_map[*last_query] = cov; // Clear range list: rl_current_query.clear(); } // For all queries, We have to add all hits that meet the criteria to the list of ranges: rl_current_query // We add this hit: // Remember: The blast result contains the last position in the range so we have to add one. // Let us check the criteria before we add the hit: if ((**it).get_evalue() <= max_e_value && (**it).get_perfection() >= min_perfection) { rl_current_query.add((**it).get_start_query(), (**it).get_end_query()+1 ); std::cerr << "Adding to range of " << *current_query << " " << (**it).get_start_query() << " " << (**it).get_end_query()+1 << std::endl; } else { std::cerr << "Not adding to range of " << *current_query << " " << (**it).get_start_query() << " " << (**it).get_end_query()+1 << std::endl; } ++it; last_query = current_query; } // After exiting we have to save the last query-sequence: cov = rl_current_query.coverage_len(r_all); std::cerr << *last_query << " cov: " << cov << std::endl; total_coverage_map[*last_query] = cov; // std::cerr << "Coverage map computed- " << std::endl; std::cerr << "Finished computing coverage values" << std::endl; } /* std::list::iterator blc_lower_bound(faststring &value) { std::list::iterator it, first; unsigned count, step; count = std::distance(lbh.begin(), lbh.end()); first = lbh.begin(); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if ((**it).get_query_seq_name() < value) { first = ++it; count -= step + 1; } else { count = step; } } return first; } // // Search all blast hits that have a query name that begins identical to the query_beginning_match_str // and determine the maximum hit length in this set. // More formally: Search for all hits with a query that is identical to query_beginning_match_str // when restricted to the first query_beginning_match_str.size() characters. int get_max_hit_query_span__matching_beginning1(faststring &query_beginning_match_str) { int max_len; std::cout << "Entering: get_max_hit_query_span__matching_beginning1 with " << query_beginning_match_str << std::endl; sort_by_query_name_quality(); // Find first hit which start with the search string: std::list::iterator it, it_end; it = blc_lower_bound(query_beginning_match_str); it_end = lbh.end(); if (it == it_end) { std::cout << "No hit found (p1) for partial name of query: " << query_beginning_match_str << std::endl; return -1; } // If there is no Blast hit for the query with this name, // it can be but in most cases will not be equal to it_end // The definitive check is that it points to a hit that matches if (fstrncmp(query_beginning_match_str, (**it).get_query_seq_name(),query_beginning_match_str.size() ) != 0) { std::cout << "No hit found (p2) for partial name of query: " << query_beginning_match_str << std::endl; return -2; } max_len = (**it).get_query_span(); ++it; while (it != it_end) { // If the strings to not match over the length of query_beginning_match_str.size(), we break if (fstrncmp(query_beginning_match_str, (**it).get_query_seq_name(),query_beginning_match_str.size() ) != 0) break; // If they are still equal over the length of query_beginning_match_str.size(), if ( (int)(**it).get_query_span() > max_len) max_len = (int)(**it).get_query_span(); ++it; } std::cout << "Found partial name of query: " << query_beginning_match_str << " " << max_len << std::endl; return max_len; } */ int get_max_hit_query_span__matching_beginning2(faststring &query_beginning_match_str, unsigned verbosity) { int max_len; if (verbosity > 100) std::cout << "Entering: get_max_hit_query_span__matching_beginning2 with " << query_beginning_match_str << std::endl; // Find first hit which start with the search string: std::multimap::iterator it, it_end; it = bh_map.lower_bound(query_beginning_match_str); it_end = bh_map.end(); if (it == it_end) { if (verbosity > 100) { std::cout << "No hit found (p1) for partial name of query: " << query_beginning_match_str << std::endl; } return -1; } // If there is no Blast hit for the query with this name, // the iterator it can be but in most cases will not be equal to it_end // The definitive check is that it points to a hit that matches if (fstrncmp(query_beginning_match_str, (it->second)->get_query_seq_name(),query_beginning_match_str.size() ) != 0) { if (verbosity > 100) { std::cout << "No hit found (p2) for partial name of query: " << query_beginning_match_str << std::endl; } return -2; } max_len = (it->second)->get_query_span(); ++it; while (it != it_end) { // If the strings to not match over the length of query_beginning_match_str.size(), we break if (fstrncmp(query_beginning_match_str, (it->second)->get_query_seq_name(),query_beginning_match_str.size() ) != 0) break; // If they are still equal over the length of query_beginning_match_str.size(), if ( (int)(it->second)->get_query_span() > max_len) max_len = (int)(it->second)->get_query_span(); ++it; } if (verbosity > 100) { std::cout << "Found partial name of query: " << query_beginning_match_str << " " << max_len << std::endl; } return max_len; } void set_of_gi_numbers_target(std::set &gi_set) { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); faststring tmp_gi; while (it != it_end) { (**it).extract_GI_number_target(tmp_gi); gi_set.insert(tmp_gi.ToUnsigned()); ++it; } } void set_of_query_names(std::set &s) { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); while (it != it_end) { s.insert( (**it).get_query_seq_name() ); ++it; } } /* void get_max_query_span_map_for_matching_queries(std::map m, char stop_char, int num_stop_char) */ /* { */ /* } */ void write_set_of_gi_numbers_to_file(const char *fname) { std::set gi_set; set_of_gi_numbers_target(gi_set); std::set::iterator it,it_end; it = gi_set.begin(); it_end = gi_set.end(); std::ofstream os(fname); while (it != it_end) { os << *it << std::endl; ++it; } os.close(); } // END write_set_of_gi_numbers_to_file // fill a map with the following information: // For all gi numbers of the target sequences, the map contains the number of occurrences of this target. void get_gi_occurence_map(std::map &gim) { std::list::iterator it, it_end; it = lbh.begin(); it_end = lbh.end(); faststring tmp_gi; while (it != it_end) { (**it).extract_GI_number_target(tmp_gi); __add_or_count(gim, tmp_gi.ToUnsigned()); ++it; } } }; #endif