|
15
|
1 #include <string>
|
|
|
2 #include <sstream>
|
|
|
3 #include <iostream>
|
|
|
4 #include <fstream>
|
|
|
5 #include <vector>
|
|
|
6 #include <set>
|
|
|
7 #include <map>
|
|
|
8
|
|
|
9 #include <string.h>
|
|
|
10 #include <stdio.h>
|
|
|
11 #include <stdlib.h>
|
|
|
12 #include <time.h>
|
|
|
13
|
|
|
14 using namespace std;
|
|
|
15
|
|
|
16 string current_time()
|
|
|
17 {// get current time, in the format:
|
|
|
18 // Thu Mar 15 21:06:57 2012
|
|
|
19 time_t rawtime;
|
|
|
20 struct tm * timeinfo;
|
|
|
21 time ( &rawtime );
|
|
|
22 timeinfo = localtime ( &rawtime );
|
|
|
23 string str = asctime (timeinfo);
|
|
|
24 return str.substr(0,str.size()-1);
|
|
|
25 }
|
|
|
26
|
|
|
27 template<class key,class val>
|
|
|
28 void PrintMap(map<key,val> m)
|
|
|
29 {// print out a map
|
|
|
30 for (typename map<key,val>::iterator it = m.begin();it!=m.end(); it++)
|
|
|
31 {
|
|
|
32 cout << (*it).first << "\t=>\t" <<(*it).second<<endl;
|
|
|
33 }
|
|
|
34 }
|
|
|
35
|
|
|
36 char complement(char ch){
|
|
|
37 switch (ch)
|
|
|
38 {
|
|
|
39 case 'A':return 'T';
|
|
|
40 case 'C':return 'G';
|
|
|
41 case 'G':return 'C';
|
|
|
42 case 'T':return 'A';
|
|
|
43 default:return 'N';
|
|
|
44 }
|
|
|
45 }
|
|
|
46
|
|
|
47 string reverseComplement(string seq){
|
|
|
48 int L = seq.length();
|
|
|
49 string rc (L,'0');
|
|
|
50 for (int i=0;i<L; i++)
|
|
|
51 {
|
|
|
52 rc[L-i-1] = complement(seq[i]);
|
|
|
53 }
|
|
|
54 return rc;
|
|
|
55 }
|
|
|
56
|
|
|
57 void ReadOneSeqFromFasta(ifstream& infile, string& name, string& seq)
|
|
|
58 {
|
|
|
59 // read one sequence from fasta file
|
|
|
60 getline(infile,name); // read identifier line
|
|
|
61 name = name.substr(1);// remove leading '>'
|
|
|
62 seq = ""; // initialize sequence
|
|
|
63 string str;
|
|
|
64 while(infile.peek() != '>' && infile.good())
|
|
|
65 {// before next '>' and before hitting the end of the file
|
|
|
66 getline(infile,str);
|
|
|
67 seq.append(str);
|
|
|
68 }
|
|
|
69 }
|
|
|
70
|
|
|
71 vector<int> findall(string seq, string motif)
|
|
|
72 {
|
|
|
73 // find all match positions of motif in seq
|
|
|
74 vector<int> allpos;
|
|
|
75 size_t pos = 0;
|
|
|
76 while(pos != string::npos)
|
|
|
77 {
|
|
|
78 pos = seq.find(motif,pos+1);
|
|
|
79 allpos.push_back(pos);
|
|
|
80 }
|
|
|
81 return allpos;
|
|
|
82 }
|
|
|
83
|
|
|
84 string int2str(int number)
|
|
|
85 {
|
|
|
86 stringstream ss;//create a stringstream
|
|
|
87 ss << number;//add number to the stream
|
|
|
88 return ss.str();//return a string with the contents of the stream
|
|
|
89 }
|
|
|
90
|
|
|
91
|
|
|
92
|
|
|
93 map<string,string> ReadFasta(string filename)
|
|
|
94 {//read all sequences in a fasta file
|
|
|
95 ifstream fin(filename.c_str());
|
|
|
96
|
|
|
97 map<string,string> seqs;
|
|
|
98 string name,seq;
|
|
|
99 while(fin.good())
|
|
|
100 {
|
|
|
101 ReadOneSeqFromFasta(fin,name,seq);
|
|
|
102 seqs[name] = seq;
|
|
|
103 }
|
|
|
104 fin.close();
|
|
|
105 return seqs;
|
|
|
106 }
|
|
|
107
|
|
|
108 void mismatches(map<string,string>& mutant,map<string,int>& dist, string motif, int n, set<char> alphabet)
|
|
|
109 {
|
|
|
110 set<char>::iterator it;
|
|
|
111 if (mutant.count(motif) == 0)
|
|
|
112 {
|
|
|
113 mutant[motif] = "";
|
|
|
114 dist[motif]=n;
|
|
|
115 }
|
|
|
116 if(n==0){return;}
|
|
|
117 for (int i=0;i<motif.length();i++)
|
|
|
118 {
|
|
|
119 string str=motif;
|
|
|
120 set<char> ab = alphabet;
|
|
|
121 ab.erase(str[i]);
|
|
|
122 for (it = ab.begin(); it!=ab.end(); it++)
|
|
|
123 {
|
|
|
124 str[i] = *it;
|
|
|
125 //cout << "mutate "<<motif<<" to "<<str<<endl;
|
|
|
126 if (mutant.count(str) >0)
|
|
|
127 {
|
|
|
128 if(dist[str] >= n)
|
|
|
129 {
|
|
|
130 //cout << mutant[str] <<endl;
|
|
|
131 continue;
|
|
|
132 }
|
|
|
133 }
|
|
|
134
|
|
|
135 //mutated to a new sequence
|
|
|
136 //cout <<"new mutation"<<endl;
|
|
|
137 mutant[str] = mutant[motif];
|
|
|
138 mutant[str].push_back(',');
|
|
|
139 mutant[str].push_back(motif[i]);
|
|
|
140 mutant[str].append(int2str(i+1));
|
|
|
141 mutant[str].push_back(str[i]);
|
|
|
142 dist[str]=n;
|
|
|
143 //cout << "tag="<<mutant[str]<<" dist="<<n<<endl;
|
|
|
144
|
|
|
145 if (n>1)
|
|
|
146 {
|
|
|
147 //cout << "subproc" <<endl;
|
|
|
148 mismatches(mutant,dist,str,n-1,alphabet);
|
|
|
149 }
|
|
|
150 }
|
|
|
151
|
|
|
152 }
|
|
|
153 }
|
|
|
154
|
|
|
155 map<string,string> ExpandMotifs(map<string,string>& motifs, int nmismatch, bool rc, set<char> alphabet)
|
|
|
156 {
|
|
|
157 map<string,string> expandedmotifs;
|
|
|
158 // generate mismatched motifs
|
|
|
159 map<string,string> mutants;
|
|
|
160 map<string,int> dist;
|
|
|
161 map<string,string>::iterator it; // iterator for motifs
|
|
|
162 map<string,int>::iterator it2; // iterator for mutants
|
|
|
163 string name,seq,tmp;
|
|
|
164 //cout<<"input motifs"<<endl;
|
|
|
165 //PrintMap(motifs);
|
|
|
166 for(it=motifs.begin();it!=motifs.end();it++)
|
|
|
167 {
|
|
|
168 name = (*it).first;
|
|
|
169 seq = (*it).second;
|
|
|
170
|
|
|
171 mismatches(mutants,dist,seq,nmismatch,alphabet);
|
|
|
172 //cout << mutants.size()<<" mutants identified" <<endl;
|
|
|
173 //PrintMap(mutants);
|
|
|
174 // add mutants to motifs
|
|
|
175 for(it2=dist.begin();it2!=dist.end();it2++)
|
|
|
176 {
|
|
|
177 string tmp = name;
|
|
|
178 tmp.append(",").append((*it2).first);
|
|
|
179 tmp.append(mutants[(*it2).first]);
|
|
|
180 expandedmotifs[tmp] = (*it2).first;
|
|
|
181 //cout << name <<","<<tmp<<","<<expandedmotifs[tmp]<<endl;
|
|
|
182 }
|
|
|
183 // clear the mutants list
|
|
|
184 mutants.clear();
|
|
|
185 dist.clear();
|
|
|
186 }
|
|
|
187 //PrintMap(expandedmotifs);
|
|
|
188 //cout << expandedmotifs.size() <<" expanded motifs"<<endl;
|
|
|
189 //cout <<"add reverse complement"<<endl;
|
|
|
190 map<string,string> expandedmotifs_rc = expandedmotifs;
|
|
|
191 if (rc)
|
|
|
192 {
|
|
|
193 for(it=expandedmotifs.begin();it!=expandedmotifs.end();it++)
|
|
|
194 {
|
|
|
195 name = (*it).first;
|
|
|
196 expandedmotifs_rc[name.append(",rc")] = reverseComplement((*it).second);
|
|
|
197 }
|
|
|
198 }
|
|
|
199
|
|
|
200 return expandedmotifs_rc;
|
|
|
201
|
|
|
202 }
|
|
|
203
|
|
|
204
|
|
|
205
|
|
|
206 int* match(string motiffile, string seqfile, string outfile, int nmismatch, bool rc, set<char> alphabet)
|
|
|
207 {
|
|
|
208 int nsite = 0; // total number of matches to report
|
|
|
209 int nseq = 0;
|
|
|
210 ifstream fmotif, fseq;
|
|
|
211 ofstream fout;
|
|
|
212
|
|
|
213 // load motifs
|
|
|
214 map<string,string> motifs = ReadFasta(motiffile);
|
|
|
215 cout <<"["<<current_time()<<"] "<<motifs.size()<< " motifs loaded from "<<motiffile<<endl;
|
|
|
216
|
|
|
217 // expand motifs
|
|
|
218 map<string,string> expandedmotifs = ExpandMotifs(motifs,nmismatch,rc,alphabet);
|
|
|
219 cout <<"["<<current_time()<<"] "<<expandedmotifs.size()<< " motifs after expanding (mismatch/reverse-complement)"<<endl;
|
|
|
220
|
|
|
221 //PrintMap(expandedmotifs);
|
|
|
222
|
|
|
223 // searching motifs in each sequence
|
|
|
224 fseq.open(seqfile.c_str());
|
|
|
225 fout.open(outfile.c_str());
|
|
|
226
|
|
|
227 string seqname,seq,motifname,motif;
|
|
|
228 while(fseq.good())
|
|
|
229 {
|
|
|
230 // read one sequence
|
|
|
231 ReadOneSeqFromFasta(fseq,seqname,seq);
|
|
|
232 nseq = nseq + 1;
|
|
|
233
|
|
|
234 cout.flush();
|
|
|
235 // iterate over motifs
|
|
|
236 map<string,string>::iterator it;
|
|
|
237 for(it=expandedmotifs.begin();it!=expandedmotifs.end();it++)
|
|
|
238 {
|
|
|
239 motifname = (*it).first;
|
|
|
240 motif = (*it).second;
|
|
|
241 //cout << "searching for "<<motifname<<":"<< motif <<endl;
|
|
|
242 vector<int> found = findall(seq,motif);
|
|
|
243 for (int i =0;i<found.size()-1;i++)
|
|
|
244 {
|
|
|
245 fout <<seqname<<"\t"<<found[i]<< "\t"<< motifname <<"\t"<<motif<<endl;
|
|
|
246 }
|
|
|
247 nsite = nsite + found.size()-1;
|
|
|
248 }
|
|
|
249 cout <<"\r["<<current_time()<<"] " << nsite << " sites found in "<< nseq << " sequences " ;
|
|
|
250 }
|
|
|
251
|
|
|
252 cout << endl;
|
|
|
253 fseq.close();
|
|
|
254 fout.close();
|
|
|
255
|
|
|
256 int* res = new int[2];
|
|
|
257 res[0] = nsite;
|
|
|
258 res[1] = nseq;
|
|
|
259
|
|
|
260 return res;
|
|
|
261 }
|
|
|
262
|
|
|
263 vector<string> StringExplode(string str, string separator){
|
|
|
264 int found;
|
|
|
265 vector<string> results;
|
|
|
266 found = str.find_first_of(separator);
|
|
|
267 while(found != string::npos){
|
|
|
268 if(found > 0){
|
|
|
269 results.push_back(str.substr(0,found));
|
|
|
270 }
|
|
|
271 str = str.substr(found+1);
|
|
|
272 found = str.find_first_of(separator);
|
|
|
273 }
|
|
|
274 if(str.length() > 0){
|
|
|
275 results.push_back(str);
|
|
|
276 }
|
|
|
277 return results;
|
|
|
278 }
|
|
|
279
|
|
|
280 int tab2bed(string infile, string outfile)
|
|
|
281 {
|
|
|
282 //hg18_chr6_122208322_122209078_+ 635 5ss,A7C,G8T-rc AAGTACCTG
|
|
|
283 //hg18_chr6_122208322_122209078_+ 553 5ss,C1G,G3A GAAGTAAGT
|
|
|
284 ifstream fin;
|
|
|
285 ofstream fout;
|
|
|
286 fin.open(infile.c_str());
|
|
|
287 fout.open(outfile.c_str());
|
|
|
288 string line;
|
|
|
289 vector<string> flds;
|
|
|
290 vector<string> pos;
|
|
|
291 vector<string> nm;
|
|
|
292 while(fin)
|
|
|
293 {
|
|
|
294 getline(fin,line);
|
|
|
295 if (line.length() == 0)
|
|
|
296 continue;
|
|
|
297 flds = StringExplode(line,"\t");
|
|
|
298 pos = StringExplode(flds[0],"_");
|
|
|
299 if (pos.size() < 5)
|
|
|
300 {
|
|
|
301 cout << "\n!! incorrect sequence name format!\n make sure sequence name looks like: hg18_chr6_122208322_122209078_+\n\n";
|
|
|
302 return 0;
|
|
|
303 }
|
|
|
304 string chr = pos[1];
|
|
|
305 int start = atoi(pos[2].c_str());
|
|
|
306 int end = atoi(pos[3].c_str());
|
|
|
307 int match_start = atoi(flds[1].c_str());
|
|
|
308 int motifLen = flds[3].length();
|
|
|
309 // check if match on the other strand
|
|
|
310 string strandness = "sense";
|
|
|
311 if (flds[2].find("rc") !=string::npos)
|
|
|
312 strandness = "antisense";
|
|
|
313 string strand = pos[4];
|
|
|
314
|
|
|
315 if (strand== "+")
|
|
|
316 {
|
|
|
317 start = start + match_start;
|
|
|
318 if (strandness == "antisense")
|
|
|
319 {
|
|
|
320 strand = "-";
|
|
|
321 }
|
|
|
322 }
|
|
|
323 else//sequence on the - strand of the genome
|
|
|
324 {
|
|
|
325 start = end - match_start - motifLen;
|
|
|
326 if (strandness == "antisense")
|
|
|
327 {
|
|
|
328 strand = "+";
|
|
|
329 }
|
|
|
330 }
|
|
|
331 end = start + motifLen;
|
|
|
332 // number of mismatches
|
|
|
333 nm = StringExplode(flds[2],",");
|
|
|
334 int score = nm.size()-1;
|
|
|
335
|
|
|
336 fout << chr <<"\t"<<start<<"\t" <<end<<"\t"<<flds[3]<< "\t"<<score <<"\t"<<strand<< "\t"<<strandness<<"\t"<<flds[2]<<"\t"<<flds[0]<<"\t"<<flds[1]<<endl;
|
|
|
337
|
|
|
338 }
|
|
|
339 fin.close();
|
|
|
340 fout.close();
|
|
|
341 return 1;//return 1 if successfully created bed file
|
|
|
342 }
|
|
|
343
|
|
|
344 int main(int argc, char* argv[]) {
|
|
|
345
|
|
|
346 if (argc < 7)
|
|
|
347 {
|
|
|
348 cout << "usage\n";
|
|
|
349 cout << " match motif.fa seq.fa outfile nmismatch rc/norc bed/nobed" << endl;
|
|
|
350 cout << "==========\n";
|
|
|
351 cout << "arguments:" <<endl;
|
|
|
352 cout << "==========\n";
|
|
|
353 cout << " 1. motif file, fasta format, could include multiple sequences\n";
|
|
|
354 cout << " 2. sequence file, fasta format, could include multiple sequences\n";
|
|
|
355 cout << " 3. output file name\n";
|
|
|
356 cout << " 4. to search on reverse complement strand or not. use 'rc' or 'norc'\n";
|
|
|
357 cout << " 5. to output BED format or not. use 'bed' only if sequence have id like: hg18_chr12_52642148_52644699_+\n";
|
|
|
358 cout << "==========\n";
|
|
|
359 cout << "output format\n";
|
|
|
360 cout << "==========\n";
|
|
|
361 cout << " tabular:\n";
|
|
|
362 cout << "==========\n";
|
|
|
363 cout << " hg18_chr10_20048197_20048851_+ 21 5ss,T5A:CAGGAAAGT-rc ACTTTCCTG\n";
|
|
|
364 cout << " column 1: sequence id\n";
|
|
|
365 cout << " column 2: start of the match in sequence\n";
|
|
|
366 cout << " column 3: motif variant id, format: motif_id,mismatch:motif_sequence[-reverse_complement]\n";
|
|
|
367 cout << " column 4: actual match in target sequence\n";
|
|
|
368 cout << "==========\n";
|
|
|
369 cout << " BED format:\n";
|
|
|
370 cout << "==========\n";
|
|
|
371 cout << " column 1-3: genomic coordinates of the match, calculated using sequence ID: hg18_chr12_52642148_52644699_+ and match start in the sequence\n";
|
|
|
372 cout << " column 4: number of mismatches\n";
|
|
|
373 cout << " column 6: strand of the match sequence\n";
|
|
|
374 cout << " column 7: strandness of the match relative to the target sequence\n";
|
|
|
375 return 1;
|
|
|
376 }
|
|
|
377
|
|
|
378
|
|
|
379 string motiffile = argv[1]; // motif file
|
|
|
380 string seqfile = argv[2]; // sequence file
|
|
|
381 string outfile = argv[3]; // output file
|
|
|
382 int nmismatch = atoi(argv[4]);// # of mismatches allowed
|
|
|
383 string _rc = argv[5]; // rc or norc: to search reverse complement strand or not
|
|
|
384 string _bed = argv[6]; // to make bed output or not. only valid if sequence have id like: hg18_chr12_52642148_52644699_+
|
|
|
385 bool rc = false;
|
|
|
386 if (_rc == "rc") {rc=true;}
|
|
|
387 bool bed = false;
|
|
|
388 if (_bed == "bed") {bed=true;}
|
|
|
389
|
|
|
390 // alphabet
|
|
|
391 string ACGT_str = "ACGT";
|
|
|
392 set<char> alphabet;
|
|
|
393 for (int i=0;i<4;i++)
|
|
|
394 {
|
|
|
395 alphabet.insert(ACGT_str[i]);
|
|
|
396 }
|
|
|
397
|
|
|
398 int *res = match(motiffile, seqfile, outfile, nmismatch, rc, alphabet);
|
|
|
399
|
|
|
400 if (_bed == "bed" && res[0]>0)
|
|
|
401 {
|
|
|
402 cout <<"["<<current_time()<<"] creating BED format output..."<<endl;
|
|
|
403 string bedfile = outfile;
|
|
|
404 bedfile += ".bed";
|
|
|
405 if (tab2bed(outfile,bedfile))
|
|
|
406 {
|
|
|
407 rename(bedfile.c_str(),outfile.c_str());
|
|
|
408 }
|
|
|
409 }
|
|
|
410 cout <<"["<<current_time()<<"] Done"<<endl;
|
|
|
411 return 0;
|
|
|
412 }
|
|
|
413
|
