ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/fqtrim/fqtrim.cpp
(Generate patch)
# Line 3 | Line 3
3   #include "GHash.hh"
4   #include "GList.hh"
5   #include <ctype.h>
6 + #include "GAlnExtend.h"
7  
8   #define USAGE "Usage:\n\
9   fqtrim [{-5 <5adapter> -3 <3adapter>|-f <adapters_file>}] [-a <min_matchlen>]\\\n\
# Line 30 | Line 31
31      (e.g. -5 CGACAGGTTCAGAGTTCTACAGTCCGACGATC)\n\
32   -3  trim the given adapter sequence at the 3' end of each read\n\
33      (e.g. -3 TCGTATGCCGTCTTCTGCTTG)\n\
34 < -a  minimum length of exact match to adaptor sequence at the proper end (6)\n\
34 > -A  disable polyA/T trimming (enabled by default)\n\
35 > -y  minimum length of exact match to adaptor sequence at the proper end (6)\n\
36   -q  trim bases with quality value lower than <minq> (starting at the 3' end)\n\
37   -t  for -q option, maximum trimming at the 3' end is limited to <trim_max_len>\n\
38   -m  maximum percentage of Ns allowed in a read after trimming (default 7)\n\
# Line 46 | Line 48
48   -Q  convert quality values to the other Phred qv type\n\
49   -V  verbose processing\n\
50   "
51 <
51 >
52   //-z  for -o option, the output stream(s) will be first piped into the given\n
53   //   <zcmd> command, which must output to stdout (e.g. -z 'bzip2 -9 -c')\n
54  
55 <
55 >
56   // example 3' adapter for miRNAs: TCGTATGCCGTCTTCTGCTTG
57  
58   //For paired reads sequencing:
# Line 60 | Line 62
62   //FILE* f_out2=NULL; //for paired reads
63   //FILE* f_in=NULL; //input fastq (stdin if not provided)
64   //FILE* f_in2=NULL; //for paired reads
65 +
66   FILE* freport=NULL;
67  
68   bool debug=false;
69   bool verbose=false;
70   bool doCollapse=false;
71   bool doDust=false;
72 + bool doPolyTrim=true;
73   bool fastaOutput=false;
74   bool trashReport=false;
75   //bool rawFormat=false;
# Line 74 | Line 78
78   int dust_cutoff=16;
79   bool isfasta=false;
80   bool convert_phred=false;
81 < GStr outsuffix; // -o
78 < //GStr adapter3;
79 < //GStr adapter5;
81 > GStr outsuffix; // -o
82   GStr prefix;
83   GStr zcmd;
84   int num_trimmed5=0;
# Line 91 | Line 93
93   int qv_phredtype=0; // could be 64 or 33 (0 means undetermined yet)
94   int qv_cvtadd=0; //could be -31 or +31
95  
96 < int a3len=0;
97 < int a5len=0;
98 < // adaptor matching metrics -- for extendMatch() function
99 < const int a_m_score=2; //match score
100 < const int a_mis_score=-3; //mismatch
101 < const int a_dropoff_score=7;
102 < int a_min_score=12; //an exact match of 6 bases at the proper ends WILL be trimmed
103 < const int a_min_chain_score=15; //for gapped alignments
104 <
105 < class CSegChain;
106 <
107 < class CSegPair {
108 <  public:
109 <   GSeg a;
110 <   GSeg b; //the adapter segment
111 <   int score;
112 <   int flags;
113 <   CSegChain* chain;
114 <   CSegPair(int astart=0, int aend=0, int bstart=0, int bend=0, int mscore=0):a(astart,aend),b(bstart, bend) {
115 <      score=mscore;
116 <      if (score==0) score=a.len()*a_m_score;
117 <      flags=0;
118 <      chain=NULL;
117 <      }
118 <   int len() { return  a.len(); }
119 <   bool operator==(CSegPair& d){
120 <      //return (a.start==d.a.start && a.end==d.a.end && b.start==d.b.start && b.end==d.b.end);
121 <      //make equal even segments that are included into one another:
122 <      return (d.a.start>=a.start && d.a.end<=a.end && d.b.start>=b.start && d.b.end<=b.end);
123 <      }
124 <   bool operator>(CSegPair& d){ //ordering based on b (adaptor) start coord and score
125 <     if (b.start==d.b.start) {
126 <        if (score==d.score) {
127 <           //just try to be consistent:
128 <           if (b.end==d.b.end) {
129 <             return (a.start==d.a.start)?(a.end<d.a.end):(a.start<d.a.start);
130 <             }
131 <           return (b.end>d.b.end);
132 <           }
133 <         else return (score<d.score);
134 <        }
135 <     return (b.start>d.b.start);
136 <     }
137 <   bool operator<(CSegPair& d){ //ordering based on b (adaptor) coord
138 <     /*if (b.start==d.b.start && b.end==d.b.end) {
139 <          return (a.start==d.a.start)?(a.end<d.a.end):(a.start<d.a.start);
140 <          }
141 <     return (b.start==d.b.start)?(b.end<d.b.end):(b.start<d.b.start);*/
142 <     if (b.start==d.b.start) {
143 <        if (score==d.score) {
144 <           //just try to be consistent:
145 <           if (b.end==d.b.end) {
146 <             return (a.start==d.a.start)?(a.end>d.a.end):(a.start>d.a.start);
147 <             }
148 <           return (b.end<d.b.end);
149 <           }
150 <         else return (score>d.score);
151 <        }
152 <     return (b.start<d.b.start);
153 <     }
154 < };
155 <
156 < int cmpSegEnds(pointer sa, pointer sb) { //sort by adaptor seg ends AND score
157 < CSegPair& x = *(CSegPair *)sa;
158 < CSegPair& y = *(CSegPair *)sb;
159 < /*
160 < if (x.b.end==y.b.end) {
161 <     if (x.b.start==y.b.start) {
162 <         if (x.a.end==y.a.end) {
163 <            if (x.a.start==y.a.start) return 0;
164 <            return ((x.a.start>y.a.start) ? -1 : 1);
165 <            }
166 <          else {
167 <            return ((x.a.end>y.a.end) ? -1 : 1);
168 <            }
169 <          }
170 <      else {
171 <       return ((x.b.start>y.b.start) ? -1 : 1);
96 > // adaptor matching metrics -- for X-drop ungapped extension
97 > const int match_reward=2;
98 > const int mismatch_penalty=3;
99 > const int Xdrop=8;
100 >
101 > const int poly_m_score=2; //match score
102 > const int poly_mis_score=-3; //mismatch
103 > const int poly_dropoff_score=7;
104 > int poly_minScore=12; //i.e. an exact match of 6 bases at the proper ends WILL be trimmed
105 >
106 > const char *polyA_seed="AAAA";
107 > const char *polyT_seed="TTTT";
108 >
109 > struct CASeqData {
110 >   //positional data for every possible hexamer in an adapter
111 >   GVec<uint16>* pz[64]; //0-based coordinates of all possible hexamers in the adapter sequence
112 >   GVec<uint16>* pzr[64]; //0-based coordinates of all possible hexamers for the reverse complement of the adapter sequence
113 >   GStr seq; //actual adapter sequence data
114 >   GStr seqr; //reverse complement sequence
115 >   CASeqData(bool rev=false):seq(),seqr() {
116 >     for (int i=0;i<63;i++) {
117 >       pz[i]=new GVec<uint16>(1);
118 >       if (rev) pzr[i]=new GVec<uint16>(1);
119         }
120 +   }
121 +
122 +   ~CSeqData() {
123 +     for (int i=0;i<63;i++) {
124 +     delete pz[i];
125 +     if (rev) { delete pzr[i]; }
126       }
127 <    else {
128 <     return ((x.b.end>y.b.end) ? -1 : 1);
176 <     }
177 < */
178 <  if (x.b.end==y.b.end) {
179 <     if (x.score==y.score) {
180 <     if (x.b.start==y.b.start) {
181 <         if (x.a.end==y.a.end) {
182 <            if (x.a.start==y.a.start) return 0;
183 <            return ((x.a.start<y.a.start) ? -1 : 1);
184 <            }
185 <          else {
186 <            return ((x.a.end<y.a.end) ? -1 : 1);
187 <            }
188 <          }
189 <      else {
190 <       return ((x.b.start<y.b.start) ? -1 : 1);
191 <       }
192 <      } else return ((x.score>y.score) ? -1 : 1);
193 <     }
194 <    else {
195 <     return ((x.b.end>y.b.end) ? -1 : 1);
196 <     }
127 >   }
128 > };
129  
130 < }
130 > GVec<CASeqData> adapters5;
131 > GVec<CASeqData> adapters3;
132  
133 < class CSegChain:public GList<CSegPair> {
134 < public:
202 <   uint astart;
203 <   uint aend;
204 <   uint bstart;
205 <   uint bend;
206 <   int score;
207 <   bool endSort;
208 <  CSegChain(bool aln5=false):GList<CSegPair>(true,true,true) {//sorted, free elements, unique
209 <   //as SegPairs are inserted, they will be sorted by a.start coordinate
210 <   score=0;
211 <   astart=MAX_UINT;
212 <   aend=0;
213 <   bstart=MAX_UINT;
214 <   bend=0;
215 <   endSort=aln5;
216 <   if (aln5) { setSorted(cmpSegEnds); }
217 <   }
218 < bool operator==(CSegChain& d) {
219 <   //return (score==d.score);
220 <    return (astart==d.astart && aend==d.aend && bstart==d.bstart && bend==d.bend);
221 <   }
222 < bool operator>(CSegChain& d) { // order based on b (adaptor) coordinate
223 <   //return (score<d.score);
224 <   if (bstart==d.bstart && bend==d.bend) {
225 <          return (astart==d.astart)?(aend>d.aend):(astart>d.astart);
226 <          }
227 <     return (bstart==d.bstart)?(bend>d.bend):(bstart>d.bstart);
228 <   }
229 < bool operator<(CSegChain& d) {
230 <   //return (score>d.score);
231 <   if (bstart==d.bstart && bend==d.bend) {
232 <          return (astart==d.astart)?(aend<d.aend):(astart<d.astart);
233 <          }
234 <     return (bstart==d.bstart)?(bend<d.bend):(bstart<d.bstart);
235 <   }
236 < void addSegPair(CSegPair* segp) {
237 <   if (AddIfNew(segp)!=segp) return;
238 <   score+=segp->score;
239 <   if (astart>segp->a.start) astart=segp->a.start;
240 <   if (aend<segp->a.end) aend=segp->a.end;
241 <   if (bstart>segp->b.start) bstart=segp->b.start;
242 <   if (bend<segp->b.end) bend=segp->b.end;
243 <   }
244 < //for building actual chains:
245 < bool extendChain(CSegPair* segp) { //segp expected to be "Greater Than" current chain
246 <   int bgap=0;
247 <   int agap=0;
248 <   //if (endSort) {
249 <   if (bstart>segp->b.start) {
250 <      bgap = (int)(bstart-segp->b.end);
251 <      if (abs(bgap)>2) return false;
252 <      agap = (int)(astart-segp->a.end);
253 <      if (abs(agap)>2) return false;
254 <      }
255 <     else {
256 <      bgap = (int) (segp->b.start-bend);
257 <      if (abs(bgap)>2) return false;
258 <      agap = (int)(segp->a.start-aend);
259 <      if (abs(agap)>2) return false;
260 <      }
261 <   if (agap*bgap<0) return false;
262 <   addSegPair(segp);
263 <   score-=abs(agap)+abs(bgap);
264 <   return true;
265 <   }
266 < };
133 > CGreedyAlignData* gxmem_l=NULL;
134 > CGreedyAlignData* gxmem_r=NULL;
135  
136   // element in dhash:
137   class FqDupRec {
# Line 313 | Line 181
181  
182   GHash<FqDupRec> dhash; //hash to keep track of duplicates
183  
184 < void setupFiles(FILE*& f_in, FILE*& f_in2, FILE*& f_out, FILE*& f_out2,
185 <                       GStr& s, GStr& infname, GStr& infname2);
184 > int loadAdapters(const char* fname);
185 >
186 > void setupFiles(FILE*& f_in, FILE*& f_in2, FILE*& f_out, FILE*& f_out2,
187 >                       GStr& s, GStr& infname, GStr& infname2);
188   // uses outsuffix to generate output file names and open file handles as needed
189 <
189 >
190   void writeRead(FILE* f_out, GStr& rname, GStr& rinfo, GStr& rseq, GStr& rqv, int& outcounter);
191   void trash_report(char trashcode, GStr& rname, FILE* freport);
192  
193 < bool getFastxRec(GLineReader& fq, GStr& rseq, GStr& rqv,
193 > bool getFastxRec(GLineReader& fq, GStr& rseq, GStr& rqv,
194            GStr& rname, GStr& rinfo, GStr& infname);
195  
196 < char process_read(GStr& rname, GStr& rseq, GStr& rqv, int &l5, int &l3);
196 > char process_read(GStr& rname, GStr& rseq, GStr& rqv, int &l5, int &l3);
197   //returns 0 if the read was untouched, 1 if it was trimmed and a trash code if it was trashed
198  
199   bool ntrim(GStr& rseq, int &l5, int &l3); //returns true if any trimming occured
200   bool qtrim(GStr& qvs, int &l5, int &l3); //return true if any trimming occured
201   int dust(GStr& seq);
202 < bool trim_adapter3(GStr& seq, int &l5, int &l3); //returns true if any trimming occured
202 > bool trim_poly5(GStr &seq, int &l5, int &l3, const char* poly_seed); //returns true if any trimming occured
203 > bool trim_poly3(GStr &seq, int &l5, int &l3, const char* poly_seed);
204   bool trim_adapter5(GStr& seq, int &l5, int &l3); //returns true if any trimming occured
205 + bool trim_adapter3(GStr& seq, int &l5, int &l3);
206  
207   void convertPhred(char* q, int len);
208   void convertPhred(GStr& q);
209  
210   int main(int argc, char * const argv[]) {
211 <  GArgs args(argc, argv, "YQDCVl:d:3:5:m:n:r:p:q:f:t:o:z:a:");
211 >  GArgs args(argc, argv, "YQDCVAl:d:3:5:m:n:r:p:q:f:t:o:z:a:");
212    int e;
213    if ((e=args.isError())>0) {
214        GMessage("%s\nInvalid argument: %s\n", USAGE, argv[e]);
# Line 347 | Line 219
219    convert_phred=(args.getOpt('Q')!=NULL);
220    doCollapse=(args.getOpt('C')!=NULL);
221    doDust=(args.getOpt('D')!=NULL);
222 +  if (args.getOpt('A')) doPolyTrim=false;
223    /*
224    rawFormat=(args.getOpt('R')!=NULL);
225    if (rawFormat) {
# Line 355 | Line 228
228    */
229    prefix=args.getOpt('n');
230    GStr s=args.getOpt('l');
231 <  if (!s.is_empty())
231 >  if (!s.is_empty())
232       min_read_len=s.asInt();
233    s=args.getOpt('m');
234 <  if (!s.is_empty())
234 >  if (!s.is_empty())
235       max_perc_N=s.asDouble();
236    s=args.getOpt('d');
237    if (!s.is_empty()) {
# Line 384 | Line 257
257          qv_phredtype=64;
258          qv_cvtadd=-31;
259          }
260 <       else
260 >       else
261           GMessage("%s\nInvalid value for -p option (can only be 64 or 33)!\n",USAGE);
262       }
263 <  if (args.getOpt('3')!=NULL) {
264 <    adapter3=args.getOpt('3');
265 <    adapter3.upper();
266 <    a3len=adapter3.length();
267 <    }
268 <  if (args.getOpt('5')!=NULL) {
269 <    adapter5=args.getOpt('5');
270 <    adapter5.upper();
271 <    a5len=adapter5.length();
263 >  s=args.getOpt('f');
264 >  if (!s.is_empty()) {
265 >   loadAdapters(s.chars());
266 >   }
267 >  bool fileAdapters=adapters5.Count()+adapters3.Count();
268 >  s=args.getOpt('5');
269 >  if (!s.is_empty()) {
270 >    if (fileAdapters)
271 >      GError("Error: options -5 and -f cannot be used together!\n");
272 >    s.upper();
273 >    adapters5.Add(s);
274      }
275 <  s=args.getOpt('a');
275 >  s=args.getOpt('3');
276    if (!s.is_empty()) {
277 <     int a_minmatch=s.asInt();
278 <     a_min_score=a_minmatch<<1;
277 >    if (fileAdapters)
278 >      GError("Error: options -3 and -f cannot be used together!\n");
279 >      s.upper();
280 >      adapters3.Add(s);
281 >    }
282 >  s=args.getOpt('y');
283 >  if (!s.is_empty()) {
284 >     int minmatch=s.asInt();
285 >     poly_minScore=minmatch*poly_m_score;
286       }
287 <  
287 >
288    if (args.getOpt('o')!=NULL) outsuffix=args.getOpt('o');
289                           else outsuffix="-";
290    trashReport=  (args.getOpt('r')!=NULL);
# Line 419 | Line 301
301    if (trashReport)
302      openfw(freport, args, 'r');
303    char* infile=NULL;
304 +
305 +  if (adapters5.Count()>0)
306 +    gxmem_l=new CGreedyAlignData(match_reward, mismatch_penalty, Xdrop-2);
307 +  if (adapters3.Count()>0)
308 +    gxmem_r=new CGreedyAlignData(match_reward, mismatch_penalty, Xdrop);
309 +
310    while ((infile=args.nextNonOpt())!=NULL) {
311 +    //for each input file
312      int incounter=0; //counter for input reads
313      int outcounter=0; //counter for output reads
314      int trash_s=0; //too short from the get go
315      int trash_Q=0;
316      int trash_N=0;
317      int trash_D=0;
318 +    int trash_poly=0;
319      int trash_A3=0;
320      int trash_A5=0;
321      s=infile;
# Line 450 | Line 340
340         int a5=0, a3=0, b5=0, b3=0;
341         char tcode=0, tcode2=0;
342         tcode=process_read(seqid, rseq, rqv, a5, a3);
343 <       //if (!doCollapse) {
454 <         if (fq2!=NULL) {
343 >       if (fq2!=NULL) {
344              getFastxRec(*fq2, rseq2, rqv2, seqid2, seqinfo2, infname2);
345              if (seqid.substr(0,seqid.length()-1)!=seqid2.substr(0,seqid2.length()-1)) {
346                 GError("Error: no paired match for read %s vs %s (%s,%s)\n",
# Line 483 | Line 372
372                 int nocounter=0;
373                 writeRead(f_out2, seqid2, seqinfo2, rseq2, rqv2, nocounter);
374                 }
375 <            } //paired read
487 <       // }
375 >            } //pair read
376         if (tcode>1) { //trashed
377 +         #ifdef GDEBUG
378 +         GMessage(" !!!!TRASH => 'N'\n");
379 +         #endif
380            if (tcode=='s') trash_s++;
381 +          else if (tcode=='A' || tcode=='T') trash_poly++;
382              else if (tcode=='Q') trash_Q++;
383                else if (tcode=='N') trash_N++;
384                 else if (tcode=='D') trash_D++;
# Line 499 | Line 391
391              rseq=rseq.substr(a5,a3-a5+1);
392              if (!rqv.is_empty()) rqv=rqv.substr(a5,a3-a5+1);
393              }
394 +         #ifdef GDEBUG
395 +            GMessage("  After trimming:\n");
396 +            GMessage("%s\n",rseq.chars());
397 +         #endif
398            writeRead(f_out, seqid, seqinfo, rseq, rqv, outcounter);
399            }
400         } //for each fastq record
# Line 526 | Line 422
422                 }
423              }
424           outcounter++;
425 <         if (qd->count>maxdup_count) {
425 >         if (qd->count>maxdup_count) {
426              maxdup_count=qd->count;
427              maxdup_seq=seq;
428              }
429           if (isfasta) {
430             if (prefix.is_empty()) {
431 <             fprintf(f_out, ">%s_x%d\n%s\n", qd->firstname, qd->count,
431 >             fprintf(f_out, ">%s_x%d\n%s\n", qd->firstname, qd->count,
432                             rseq.chars());
433               }
434             else { //use custom read name
# Line 543 | Line 439
439           else { //fastq format
440            if (convert_phred) convertPhred(qd->qv, qd->len);
441            if (prefix.is_empty()) {
442 <            fprintf(f_out, "@%s_x%d\n%s\n+\n%s\n", qd->firstname, qd->count,
442 >            fprintf(f_out, "@%s_x%d\n%s\n+\n%s\n", qd->firstname, qd->count,
443                             rseq.chars(), qd->qv);
444              }
445            else { //use custom read name
# Line 579 | Line 475
475           GMessage("         Trashed by N%%:%9d\n", trash_N);
476         if (trash_Q>0)
477           GMessage("Trashed by low quality:%9d\n", trash_Q);
478 +       if (trash_poly>0)
479 +         GMessage("   Trashed by poly-A/T:%9d\n", trash_poly);
480         if (trash_A5>0)
481           GMessage(" Trashed by 5' adapter:%9d\n", trash_A5);
482         if (trash_A3>0)
# Line 590 | Line 488
488      FWCLOSE(f_out);
489      FWCLOSE(f_out2);
490     } //while each input file
491 <
491 > delete gxmem_l;
492 > delete gxmem_r;
493   //getc(stdin);
494   }
495  
# Line 605 | Line 504
504     const char* seq;
505     bool valid;
506     NData() {
507 +    seqlen=0;
508      NCount=0;
509      end5=0;
510      end3=0;
# Line 635 | Line 535
535       perc_N=(n*100.0)/(end5-end3+1);
536       }
537   };
538 <
538 >
539   static NData feat;
540   int perc_lenN=12; // incremental distance from ends, in percentage of
541            // sequence length, where N-trimming is done (default:12 %) (autolimited to 20)
542 <          
542 >
543   void N_analyze(int l5, int l3, int p5, int p3) {
544   /* assumes feat was filled properly */
545   int old_dif, t5,t3,v;
546   if (l3<l5+2 || p5>p3 ) {
547     feat.end5=l5+1;
548     feat.end3=l3+1;
549 <   return;
549 >   return;
550     }
551  
552   t5=feat.NPos[p5]-l5;
553   t3=l3-feat.NPos[p3];
554   old_dif=p3-p5;
555   v=(int)((((double)(l3-l5))*perc_lenN)/100);
556 < if (v>20) v=20; /* enforce N-search limit for very long reads */
556 > if (v>20) v=20; /* enforce N-search limit for very long reads */
557   if (t5 < v ) {
558     l5=feat.NPos[p5]+1;
559     p5++;
# Line 670 | Line 570
570             feat.end3=l3+1;
571             return;
572             }
573 <    else
573 >    else
574        N_analyze(l5,l3, p5,p3);
575   }
576  
# Line 711 | Line 611
611   feat.init(rseq);
612   l5=feat.end5-1;
613   l3=feat.end3-1;
614 < N_analyze(feat.end5-1, feat.end3-1, 0, feat.NCount-1);
614 > N_analyze(feat.end5-1, feat.end3-1, 0, feat.NCount-1);
615   if (l5==feat.end5-1 && l3==feat.end3-1) {
616      if (feat.perc_N>max_perc_N) {
617             feat.valid=false;
# Line 729 | Line 629
629     return true;
630     }
631   feat.N_calc();
632 <
632 >
633   if (feat.perc_N>max_perc_N) {
634        feat.valid=false;
635        l3=l5+1;
# Line 741 | Line 641
641   //--------------- dust functions ----------------
642   class DNADuster {
643   public:
644 <  int dustword;
645 <  int dustwindow;
646 <  int dustwindow2;
644 >  int dustword;
645 >  int dustwindow;
646 >  int dustwindow2;
647    int dustcutoff;
648    int mv, iv, jv;
649    int counts[32*32*32];
# Line 838 | Line 738
738                      }
739             }
740           }
741 < //return first;
741 > //return first;
742   }
743   };
744  
# Line 856 | Line 756
756   return ncount;
757   }
758  
759 + struct SLocScore {
760 +  int pos;
761 +  int score;
762 +  SLocScore(int p=0,int s=0) {
763 +    pos=p;
764 +    score=s;
765 +    }
766 +  void set(int p, int s) {
767 +    pos=p;
768 +    score=s;
769 +    }
770 +  void add(int p, int add) {
771 +    pos=p;
772 +    score+=add;
773 +    }
774 + };
775  
776 < // ------------------ adapter matching - simple k-mer seed & extend, no indels for now
777 < //when a k-mer match is found, simply try to extend the alignment using a drop-off scheme
778 < //check minimum score and
779 < //for 3' adapter trimming:
780 < //     require that the right end of the alignment for either the adaptor OR the read must be
781 < //     < 3 distance from its right end
782 < // for 5' adapter trimming:
783 < //     require that the left end of the alignment for either the adaptor OR the read must
784 < //     be at coordinate < 3 from start
785 <
786 < bool extendMatch(const char* a, int alen, int ai,
787 <                 const char* b, int blen, int bi, int mlen, int& l5, int& l3, CSegChain& segs, bool end5=false) {
788 < //so the alignment starts at ai in a, bi in b, with a perfect match of length mlen
789 < #ifdef DEBUG
790 < GStr dbg(b);
875 < #endif
876 < //if (debug) {
877 < //  GMessage(">> in %s\n\textending hit: %s at position %d\n", a, (dbg.substr(bi, mlen)).chars(), ai);
878 < //  }
879 < int a_l=ai; //alignment coordinates on a
880 < int a_r=ai+mlen-1;
881 < int b_l=bi; //alignment coordinates on b
882 < int b_r=bi+mlen-1;
883 < int ai_maxscore=ai;
884 < int bi_maxscore=bi;
885 < int score=mlen*a_m_score;
886 < int maxscore=score;
887 < int mism5score=a_mis_score;
888 < if (end5 && ai<(alen>>1)) mism5score-=2; // increase penalty for mismatches at 5' end
889 < //try to extend to the left first, if possible
890 < while (ai>0 && bi>0) {
891 <   ai--;
892 <   bi--;
893 <   score+= (a[ai]==b[bi])? a_m_score : mism5score;
894 <   if (score>maxscore) {
895 <       ai_maxscore=ai;
896 <       bi_maxscore=bi;
897 <       maxscore=score;
898 <       }
899 <     else if (maxscore-score>a_dropoff_score) break;
900 <   }
901 < a_l=ai_maxscore;
902 < b_l=bi_maxscore;
903 < //if (debug) GMessage("  after l-extend: %*s%s\t\t(score=%d)\n",a_l," ",dbg.substr(b_l,b_r-b_l+1).chars(),maxscore);
904 < //now extend to the right
905 < ai_maxscore=a_r;
906 < bi_maxscore=b_r;
907 < ai=a_r;
908 < bi=b_r;
909 < score=maxscore;
910 < //sometimes there are extra AAAAs at the end of the read, ignore those
911 < if (strcmp(&a[alen-4],"AAAA")==0) {
912 <    alen-=3;
913 <    while (a[alen-1]=='A' && alen>ai) alen--;
914 <    }
915 < while (ai<alen-1 && bi<blen-1) {
916 <   ai++;
917 <   bi++;
918 <   //score+= (a[ai]==b[bi])? a_m_score : a_mis_score;
919 <   if (a[ai]==b[bi]) { //match
920 <      score+=a_m_score;
921 <      if (ai>=alen-2) {
922 <           score+=a_m_score-(alen-ai-1);
923 <           }
776 > bool trim_poly3(GStr &seq, int &l5, int &l3, const char* poly_seed) {
777 > if (!doPolyTrim) return false;
778 > int rlen=seq.length();
779 > l5=0;
780 > l3=rlen-1;
781 > int32 seedVal=*(int32*)poly_seed;
782 > char polyChar=poly_seed[0];
783 > //assumes N trimming was already done
784 > //so a poly match should be very close to the end of the read
785 > // -- find the initial match (seed)
786 > int lmin=GMAX((rlen-16), 0);
787 > int li;
788 > for (li=rlen-4;li>lmin;li--) {
789 >   if (seedVal==*(int*)&(seq[li])) {
790 >      break;
791        }
925    else { //mismatch
926      score+=a_mis_score;
927      }  
928   if (score>maxscore) {
929       ai_maxscore=ai;
930       bi_maxscore=bi;
931       maxscore=score;
932       }
933     else if (maxscore-score>a_dropoff_score) break;
792     }
793 <  a_r=ai_maxscore;
794 <  b_r=bi_maxscore;
795 <  int a_ovh3=alen-a_r-1;
796 <  int b_ovh3=blen-b_r-1;
797 <  int mmovh3=(a_ovh3<b_ovh3)? a_ovh3 : b_ovh3;
798 <  int mmovh5=(a_l<b_l)? a_l : b_l;
799 <  //if (debug) GMessage("  after r-extend: %*s%s\t\t(score=%d)\n",a_l," ",dbg.substr(b_l,b_r-b_l+1).chars(),maxscore);
800 < #ifdef DEBUG
801 <  if (debug) GMessage("     extended to: %*s\n",a_r+1,dbg.substr(b_l,b_r-b_l+1).chars());
802 < #endif
803 <  if (maxscore>=a_min_score && mmovh3<2 && mmovh5<2) {
804 <     if (a_l<a_ovh3) {
805 <        //adapter closer to the left end (typical for 5' adapter)
806 <        l5=a_r+1;
807 <        l3=alen-1;
808 <        }
809 <      else {
810 <        //adapter matching at the right end (typical for 3' adapter)
953 <        l5=0;
954 <        l3=a_l-1;
793 > if (li<=lmin) return false;
794 > //seed found, try to extend it both ways
795 > //extend right
796 > int ri=li+3;
797 > SLocScore loc(ri, poly_m_score<<2);
798 > SLocScore maxloc(loc);
799 > //extend right
800 > while (ri<rlen-1) {
801 >   ri++;
802 >   if (seq[ri]==polyChar) {
803 >                loc.add(ri,poly_m_score);
804 >                }
805 >   else if (seq[ri]=='N') {
806 >                loc.add(ri,0);
807 >                }
808 >   else { //mismatch
809 >        loc.add(ri,poly_mis_score);
810 >        if (maxloc.score-loc.score>poly_dropoff_score) break;
811          }
812 <     return true;
813 <     }
814 < else { //keep this segment pair for later (gapped alignment)
959 <   segs.addSegPair(new CSegPair(a_l+1, a_r+1, b_l+1, b_r+1, maxscore));
960 <   //this will also update min & max coordinates in segs (segs.astart, .aend, .bstart, .bend)
961 <   }
962 <  //do not trim:
963 <  l5=0;
964 <  l3=alen-1;
965 <  return false;
966 < }
967 <
968 < /*
969 < int getWordValue(const char* s, int wlen) {
970 < int r=0;
971 < while (wlen--) { r+=(((int)s[wlen])<<wlen) }
972 < return r;
973 < }
974 < */
975 < int get3mer_value(const char* s) {
976 < return (s[0]<<16)+(s[1]<<8)+s[2];
977 < }
978 <
979 < int w3_match(int qv, const char* str, int slen, int start_index=0) {
980 < if (start_index>=slen || start_index<0) return -1;
981 < for (int i=start_index;i<slen-3;i++) {
982 <   int rv=get3mer_value(str+i);
983 <   if (rv==qv) return i;
984 <   }
985 < return -1;
986 < }
987 <
988 < int w3_rmatch(int qv, const char* str, int slen, int end_index=-1) {
989 < if (end_index>=slen) return -1;
990 < if (end_index<0) end_index=slen-1;
991 < for (int i=end_index-2;i>=0;i--) {
992 <   int rv=get3mer_value(str+i);
993 <   if (rv==qv) return i;
994 <   }
995 < return -1;
996 < }
997 <
998 < int fast4match(int32 qv, const char* str, int slen, int start_index=0) {
999 < if (start_index>=slen || start_index<0) return -1;
1000 < for (int i=start_index;i<slen-4;i++) {
1001 <   int32* rv=(int32*)(str+i);
1002 <   if (*rv==qv) return i;
1003 <   }
1004 < return -1;
1005 < }
1006 <
1007 < int fast4rmatch(int32 qv, const char* str, int slen, int end_index=-1) {
1008 < if (end_index>=slen) return -1;
1009 < if (end_index<0) end_index=slen-1;
1010 < for (int i=end_index-3;i>=0;i--) {
1011 <   int32* rv=(int32*)(str+i);
1012 <   if (*rv==qv) return i;
1013 <   }
1014 < return -1;
1015 < }
1016 <
1017 < #ifdef DEBUG
1018 < void dbgPrintChain(CSegChain& chain, const char* aseq) {
1019 <  GStr s(aseq);
1020 <  for (int i=0;i<chain.Count();i++) {
1021 <   CSegPair& seg=*chain[i];
1022 <   GMessage("  dbg chain seg%d: %*s [%d-%d:%d-%d]\n",i,seg.a.start-1+seg.len(),
1023 <            s.substr(seg.b.start-1, seg.len()).chars(), seg.b.start,seg.b.end,seg.a.start,seg.a.end);
812 >   if (maxloc.score<=loc.score) {
813 >      maxloc=loc;
814 >      }
815     }
816 + ri=maxloc.pos;
817 + if (ri<rlen-6) return false; //no trimming wanted, too far from 3' end
818 + //ri = right boundary for the poly match
819 + //extend left
820 + loc.set(li, maxloc.score);
821 + maxloc.pos=li;
822 + while (li>0) {
823 +    li--;
824 +    if (seq[li]==polyChar) {
825 +                 loc.add(li,poly_m_score);
826 +                 }
827 +    else if (seq[li]=='N') {
828 +                 loc.add(li,0);
829 +                 }
830 +    else { //mismatch
831 +         loc.add(li,poly_mis_score);
832 +         if (maxloc.score-loc.score>poly_dropoff_score) break;
833 +         }
834 +    if (maxloc.score<=loc.score) {
835 +       maxloc=loc;
836 +       }
837 +    }
838 + li=maxloc.pos;
839 + if ((maxloc.score==poly_minScore && ri==rlen-1) ||
840 +    (maxloc.score>poly_minScore && ri>=rlen-3) ||
841 +    (maxloc.score>(poly_minScore*3) && ri>=rlen-8)) {
842 +  //trimming this li-ri match at 3' end
843 +    l3=li-1;
844 +    if (l3<0) l3=0;
845 +    return true;
846 +    }
847 + return false;
848   }
1026 #endif
849  
850 < bool trim_adapter3(GStr& seq, int&l5, int &l3) {
850 > bool trim_poly5(GStr &seq, int &l5, int &l3, const char* poly_seed) {
851 > if (!doPolyTrim) return false;
852   int rlen=seq.length();
853   l5=0;
854   l3=rlen-1;
855 < //first try a full match, we might get lucky
856 < int fi=-1;
857 < if ((fi=seq.index(adapter3))>=0) {
858 <   if (fi<rlen-fi-a3len) {//match is closer to the right end
859 <      l5=fi+a3len;
860 <      l3=rlen-1;
861 <      }
862 <    else {
863 <      l5=0;
864 <      l3=fi-1;
855 > int32 seedVal=*(int32*)poly_seed;
856 > char polyChar=poly_seed[0];
857 > //assumes N trimming was already done
858 > //so a poly match should be very close to the end of the read
859 > // -- find the initial match (seed)
860 > int lmax=GMIN(12, rlen-4);//how far from 5' end to look for 4-mer seeds
861 > int li;
862 > for (li=0;li<=lmax;li++) {
863 >   if (seedVal==*(int*)&(seq[li])) {
864 >      break;
865        }
1043   return true;
866     }
867 < #ifdef DEBUG
868 < if (debug) GMessage(">TRIM3 >>   Read: %s\n",seq.chars());
869 < #endif
870 <
871 < //also, for fast detection of other adapter-only reads that start past
872 < // the beginning of the adapter sequence, try to see if the first a3len-4
873 < // bases of the read are a substring of the adapter
874 < if (rlen>a3len-3) {
875 <   GStr rstart=seq.substr(1,a3len-4);
876 <   if ((fi=adapter3.index(rstart))>=0) {
877 <     l3=rlen-1;
878 <     l5=a3len-4;
879 <     while (fi+l5<a3len && l5<l3 && adapter3[fi+l5]==seq[l5]) l5++;
880 <     return true;
881 <     }
882 <  }
883 < CSegChain a3segs; //no chains here, just an ordered collection of segment pairs
884 <  //check the easy cases - 11 bases exact match at the end
885 < int fdlen=11;
886 <  if (a3len<16) {
1065 <   fdlen=a3len>>1;
1066 <   }
1067 < if (fdlen>4) {
1068 <     //check if we're lucky enough to have the last 11 bases of the read a part of the adapter
1069 <     GStr rstart=seq.substr(-fdlen-3,fdlen);
1070 <     if ((fi=adapter3.index(rstart))>=0) {
1071 < #ifdef DEBUG
1072 <       if (debug) GMessage("  W11match found: %*s\n", rlen-3, (adapter3.substr(fi,fdlen)).chars());
1073 < #endif
1074 <       if (extendMatch(seq.chars(), rlen, rlen-fdlen-3,
1075 <                     adapter3.chars(), a3len, fi,  fdlen, l5,l3, a3segs))
1076 <            return true;
1077 <       }
1078 <     //another easy case: first 11 characters of the adaptor found as a substring of the read
1079 <     GStr bstr=adapter3.substr(0, fdlen);
1080 <     if ((fi=seq.rindex(bstr))>=0) {
1081 < #ifdef DEBUG
1082 <       if (debug) GMessage("  A11match found: %*s\n", fi+fdlen, bstr.chars());
1083 < #endif
1084 <       if (extendMatch(seq.chars(), rlen, fi,
1085 <                     adapter3.chars(), a3len, 0,  fdlen, l5,l3, a3segs))
1086 <            return true;
867 > if (li>lmax) return false;
868 > //seed found, try to extend it both ways
869 > //extend left
870 > int ri=li+3; //save rightmost base of the seed
871 > SLocScore loc(li, poly_m_score<<2);
872 > SLocScore maxloc(loc);
873 > while (li>0) {
874 >    li--;
875 >    if (seq[li]==polyChar) {
876 >                 loc.add(li,poly_m_score);
877 >                 }
878 >    else if (seq[li]=='N') {
879 >                 loc.add(li,0);
880 >                 }
881 >    else { //mismatch
882 >         loc.add(li,poly_mis_score);
883 >         if (maxloc.score-loc.score>poly_dropoff_score) break;
884 >         }
885 >    if (maxloc.score<=loc.score) {
886 >       maxloc=loc;
887         }
888 <     } //tried to match 11 bases first
889 <    
890 < //no easy cases, so let's do the wmer hashing for the first 12 bases of the adaptor
891 < //-- only extend if the match is in the 3' (ending) region of the read
892 < int wordSize=3;
893 < int hlen=12;
894 < if (hlen>a3len-wordSize) hlen=a3len-wordSize;
895 < int imin=rlen>>1; //last half of the read, left boundary for the wmer match
896 < if (imin<a3len) { imin=GMIN(a3len, rlen-wordSize); }
897 < imin=rlen-imin;
898 < for (int iw=0;iw<hlen;iw++) {
899 <   //int32* qv=(int32*)(adapter3.chars()+iw);
900 <   int qv=get3mer_value(adapter3.chars()+iw);
901 <   fi=-1;
902 <   //while ((fi=fast4rmatch(*qv, seq.chars(), rlen, fi))>=0 && fi>=imin) {
903 <   while ((fi=w3_rmatch(qv, seq.chars(), rlen, fi))>=0 && fi>=imin) {
904 <     //GMessage(" ... fi=%d after w3_rmatch() (imin=%d)\n", fi, imin);
905 <
906 < #ifdef DEBUG
1107 <     if (debug) GMessage("    Wmatch found: %*s\n", fi+wordSize, (adapter3.substr(iw,wordSize)).chars());
1108 < #endif
1109 <     if (extendMatch(seq.chars(), rlen, fi, adapter3.chars(),
1110 <                   a3len, iw, wordSize, l5,l3, a3segs)) return true;
1111 <     fi--;
1112 <     if (fi<imin) break;
1113 <     }
1114 <   } //for each wmer in the first hlen bases of the adaptor
1115 < /*
1116 < //couldn't find a good trimming extension, hash 12 more bases of the adapter to collect more segment pairs there
1117 < //but only do this if we already have segment pairs collected in the last 12 bases of the adapter
1118 < if (a3segs.bstart>3 || a3segs.bend<(uint)(hlen-wordSize)) return false;
1119 < int hlen2=a3len-wordSize;
1120 < //if (hlen2>a3len-4) hlen2=a3len-4;
1121 < if (hlen2>hlen) {
1122 < #ifdef DEBUG
1123 <     if (debug && a3segs.Count()>0) {
1124 <        GMessage("  >>>>>2nd. hash: %s\n",seq.chars());
888 >    }
889 > li=maxloc.pos;
890 > if (li>5) return false; //no trimming wanted, too far from 5' end
891 > //li = right boundary for the poly match
892 >
893 > //extend right
894 > loc.set(ri, maxloc.score);
895 > maxloc.pos=ri;
896 > while (ri<rlen-1) {
897 >   ri++;
898 >   if (seq[ri]==polyChar) {
899 >                loc.add(ri,poly_m_score);
900 >                }
901 >   else if (seq[ri]=='N') {
902 >                loc.add(ri,0);
903 >                }
904 >   else { //mismatch
905 >        loc.add(ri,poly_mis_score);
906 >        if (maxloc.score-loc.score>poly_dropoff_score) break;
907          }
908 < #endif
909 <     for (int iw=hlen;iw<hlen2;iw++) {
1128 <         //int* qv=(int32 *)(adapter3.chars()+iw);
1129 <         int qv=get3mer_value(adapter3.chars()+iw);
1130 <         fi=-1;
1131 <         //while ((fi=fast4rmatch(*qv, seq.chars(), rlen, fi))>=0 && fi>=imin) {
1132 <         while ((fi=w3_rmatch(qv, seq.chars(), rlen, fi))>=0 && fi>=imin) {
1133 <           extendMatch(seq.chars(), rlen, fi, adapter3.chars(),
1134 <                         a3len, iw, wordSize, l5,l3, a3segs);
1135 <           fi--;
1136 <           if (fi<imin) break;
1137 <           }
1138 <         } //for each wmer between hlen2 and hlen bases of the adaptor
1139 <     }
1140 < //lastly, analyze collected a3segs for a possible gapped alignment:
1141 < GList<CSegChain> segchains(false,true,false);
1142 < #ifdef DEBUG
1143 < if (debug && a3segs.Count()>0) {
1144 <   GMessage(">>>>>>>>>   Read: %s\n",seq.chars());
1145 <   }
1146 < #endif
1147 < for (int i=0;i<a3segs.Count();i++) {
1148 <   if (a3segs[i]->chain==NULL) {
1149 <       if (a3segs[i]->b.start>3) continue; //don't start a hopeless chain
1150 <       CSegChain* newchain=new CSegChain();
1151 <       newchain->setFreeItem(false);
1152 <       newchain->addSegPair(a3segs[i]);
1153 <       a3segs[i]->chain=newchain;
1154 <       segchains.Add(newchain); //just to free them when done
1155 <       }
1156 <   for (int j=i+1;j<a3segs.Count();j++) {
1157 <      CSegChain* chain=a3segs[i]->chain;
1158 <      if (chain->extendChain(a3segs[j])) {
1159 <          a3segs[j]->chain=chain;
1160 < #ifdef DEBUG
1161 <          if (debug) dbgPrintChain(*chain, adapter3.chars());
1162 < #endif      
1163 <          //save time by checking here if the extended chain is already acceptable for trimming
1164 <          if (chain->aend>(uint)(rlen-4) && chain->bstart<4 && chain->score>a_min_chain_score) {
1165 <            l5=0;
1166 <            l3=chain->astart-2;
1167 < #ifdef DEBUG
1168 <          if (debug && a3segs.Count()>0) {
1169 <            GMessage(">>> >> trimmed-3: %*s\n",l3-l5+1,seq.substr(l5,l3-l5+1).chars());
1170 <            }
1171 < #endif
1172 <            return true;
1173 <            }
1174 <          } //chain can be extended
908 >   if (maxloc.score<=loc.score) {
909 >      maxloc=loc;
910        }
911 <   } //collect segment alignments into chains
912 < */  
913 < return false; //no adapter parts found
914 < }
911 >   }
912 > ri=maxloc.pos;
913 > if ((maxloc.score==poly_minScore && li==0) ||
914 >     (maxloc.score>poly_minScore && li<2)
915 >     || (maxloc.score>(poly_minScore*3) && li<8)) {
916 >    //adjust l5 to reflect this trimming of 5' end
917 >    l5=ri+1;
918 >    if (l5>rlen-1) l5=rlen-1;
919 >    return true;
920 >    }
921 > return false;
922 > }
923  
924 < bool trim_adapter5(GStr& seq, int&l5, int &l3) {
925 < //if (debug) GMessage("trim_adapter5 on: %s\n", seq.chars());
924 > bool trim_adapter3(GStr& seq, int&l5, int &l3) {
925 > if (adapters3.Count()==0) return false;
926   int rlen=seq.length();
927   l5=0;
928   l3=rlen-1;
929 < //try to see if adapter is fully included in the read
930 < int fi=-1;
931 < if ((fi=seq.index(adapter5))>=0) {
932 <   if (fi<rlen-fi-a5len) {//match is closer to the right end
933 <      l5=fi+a5len;
934 <      l3=rlen-1;
935 <      }
936 <    else {
937 <      l5=0;
938 <      l3=fi-1;
939 <      }
940 <   return true;
941 <   }
942 < #ifdef DEBUG
943 < if (debug) GMessage(">TRIM5 >>   Read: %s\n",seq.chars());
944 < #endif
945 <
1203 < CSegChain a5segs(true); //list of segment pairs to analyze later if no extendMatch succeeded
1204 <
1205 < //try the easy way out first - look for an exact match of 11 bases
1206 < int fdlen=11;
1207 <  if (a5len<16) {
1208 <   fdlen=a5len>>1;
1209 <   }
1210 < if (fdlen>4) {
1211 <     GStr rstart=seq.substr(1,fdlen); //skip the first base as it's sometimes bogus
1212 <     if ((fi=adapter5.index(rstart))>=0) {
1213 < #ifdef DEBUG
1214 <       if (debug) GMessage("  W11match found: %*s\n", 1+fdlen, (adapter3.substr(fi,fdlen)).chars());
1215 < #endif
1216 <       if (extendMatch(seq.chars(), rlen, 1,
1217 <                     adapter5.chars(), a5len, fi,  fdlen, l5,l3, a5segs, true))
1218 <           return true;
1219 <       }
1220 <     //another easy case: last 11 characters of the adaptor found as a substring of the read
1221 <     GStr bstr=adapter5.substr(-fdlen);
1222 <     if ((fi=seq.index(bstr))>=0) {
1223 < #ifdef DEBUG
1224 <       if (debug) GMessage("  A11match found: %*s\n", fi+fdlen, bstr.chars());
1225 < #endif
1226 <       if (extendMatch(seq.chars(), rlen, fi,
1227 <                     adapter5.chars(), a5len, a5len-fdlen,  fdlen, l5,l3,a5segs,true))
1228 <          return true;
1229 <       }
1230 <     } //tried to matching at most 11 bases first
1231 <    
1232 < //-- no easy cases, do the wmer hashing for the last 12 bases of the adaptor
1233 < //-- only extend a wmer if it matches in the 5' (beginning) region of the read
1234 < int wordSize=3;
1235 < int hlen=12;
1236 < if (hlen>a5len-wordSize) hlen=a5len-wordSize;
1237 < int imax=rlen>>1; //first half of the read, right boundary for the wmer match
1238 < if (imax<a5len) { imax=GMIN(a5len, rlen-wordSize); }
1239 < for (int iw=0;iw<=hlen;iw++) {
1240 <   int apstart=a5len-iw-wordSize;
1241 <   fi=0;
1242 <   //int* qv=(int32 *)(adapter5.chars()+apstart);
1243 <   int qv=get3mer_value(adapter5.chars()+apstart);
1244 <   //while ((fi=fast4match(*qv, seq.chars(), rlen, fi))>=0 && fi<=imax) {
1245 <   while ((fi=w3_match(qv, seq.chars(), rlen, fi))>=0 && fi<=imax) {
1246 < #ifdef DEBUG
1247 <     if (debug) GMessage("    Wmatch found: %*s\n", fi+wordSize, (adapter5.substr(apstart,wordSize)).chars());
1248 < #endif
1249 <     if (extendMatch(seq.chars(), rlen, fi, adapter5.chars(),
1250 <                a5len, apstart, wordSize, l5,l3, a5segs, true)) return true;
1251 <     fi++;
1252 <     if (fi>imax) break;
929 > bool trimmed=false;
930 > GStr wseq(seq.chars());
931 > int wlen=rlen;
932 > for (int ai=0;ai<adapters3.Count();ai++) {
933 >  if (adapters3[ai].is_empty()) continue;
934 >  int alen=adapters3[ai].length();
935 >  GStr& aseq=adapters3[ai];
936 >  GXAlnInfo* r_bestaln=match_RightEnd(aseq.chars(), alen, wseq.chars(), wlen, gxmem_r, 74);
937 >  if (r_bestaln) {
938 >     trimmed=true;
939 >     //keep unmatched region on the left, if any
940 >     l3-=(wlen-r_bestaln->sl+1);
941 >     delete r_bestaln;
942 >     if (l3<0) l3=0;
943 >     if (l3-l5+1<min_read_len) return true;
944 >     wseq=seq.substr(l5,l3-l5+1);
945 >     wlen=wseq.length();
946       }
947 <   } //for each wmer in the last hlen bases of the adaptor
948 < /*
947 >  }//for each 5' adapter
948 >  return trimmed;
949 > }
950  
951 < //couldn't find a good trimming extension, hash 12 more bases of the adapter to collect more segment pairs there
952 < //but only do this if we already have segment pairs collected in the last 12 bases of the adapter
953 < if (a5segs.bend<(uint)(a5len-3) || a5segs.bstart>(uint)(a5len-hlen+4)) return false;
954 < int hlen2=a5len-wordSize;
955 < //if (hlen2>a5len-wordSize) hlen2=a5len-wordSize;
956 < #ifdef DEBUG
957 <      if (debug && a5segs.Count()>0) {
958 <        GMessage("  >>>>>2nd. hash: %s\n",seq.chars());
959 <        }
960 < #endif
961 < if (hlen2>hlen) {
962 <     for (int iw=hlen+1;iw<=hlen2;iw++) {
963 <         int apstart=a5len-iw-wordSize;
964 <         fi=0;
965 <         //int* qv=(int32 *)(adapter5.chars()+apstart);
966 <         int qv=get3mer_value(adapter5.chars()+apstart);
967 <         //while ((fi=fast4match(*qv, seq.chars(), rlen, fi))>=0 && fi<=imax) {
968 <         while ((fi=w3_match(qv, seq.chars(), rlen, fi))>=0 && fi<=imax) {
969 <           extendMatch(seq.chars(), rlen, fi, adapter5.chars(),
970 <                      a5len, apstart, wordSize, l5,l3, a5segs, true);
971 <           fi++;
972 <           if (fi>imax) break;
1279 <           }
1280 <         } //for each wmer between hlen2 and hlen bases of the adaptor
951 > bool trim_adapter5(GStr& seq, int&l5, int &l3) {
952 > if (adapters5.Count()==0) return false;
953 > int rlen=seq.length();
954 > l5=0;
955 > l3=rlen-1;
956 > bool trimmed=false;
957 > GStr wseq(seq.chars());
958 > int wlen=rlen;
959 > for (int ai=0;ai<adapters5.Count();ai++) {
960 >  if (adapters5[ai].is_empty()) continue;
961 >  int alen=adapters5[ai].length();
962 >  GStr& aseq=adapters5[ai];
963 >  GXAlnInfo* l_bestaln=match_LeftEnd(aseq.chars(), alen, adapters5[ai].pz,
964 >                         wseq.chars(), wlen, gxmem_l, 84);
965 >  if (l_bestaln) {
966 >     trimmed=true;
967 >     l5+=l_bestaln->sr;
968 >     delete l_bestaln;
969 >     if (l5>=rlen) l5=rlen-1;
970 >     if (l3-l5+1<min_read_len) return true;
971 >     wseq=seq.substr(l5,l3-l5+1);
972 >     wlen=wseq.length();
973       }
974 < if (a5segs.bend<(uint)(a5len-3) || a5segs.bstart>(uint)(a5len-hlen+4)) return false;
975 < // lastly, analyze collected a5segs for a possible gapped alignment:
976 < GList<CSegChain> segchains(false,true,false);
1285 < #ifdef DEBUG
1286 < if (debug && a5segs.Count()>0) {
1287 <   GMessage(">>>>>>>>>   Read: %s\n",seq.chars());
1288 <   }
1289 < #endif
1290 < for (int i=0;i<a5segs.Count();i++) {
1291 <   if (a5segs[i]->chain==NULL) {
1292 <       if (a5segs[i]->b.end<(int)(a5len-4)) continue; //don't start a hopeless chain
1293 <       CSegChain* newchain=new CSegChain(true);
1294 <       newchain->setFreeItem(false);
1295 <       newchain->addSegPair(a5segs[i]);
1296 <       a5segs[i]->chain=newchain;
1297 <       segchains.Add(newchain); //just to free them when done
1298 <       }
1299 <   for (int j=i+1;j<a5segs.Count();j++) {
1300 <      CSegChain* chain=a5segs[i]->chain;
1301 <      if (chain->extendChain(a5segs[j])) {
1302 <         a5segs[j]->chain=chain;
1303 < #ifdef DEBUG
1304 <         if (debug) dbgPrintChain(*chain, adapter5.chars());
1305 < #endif      
1306 <      //save time by checking here if the extended chain is already acceptable for trimming
1307 <         if (chain->bend>(uint)(a5len-3) && chain->astart<4 && chain->score>a_min_chain_score) {
1308 <            l5=chain->aend;
1309 <            l3=rlen-1;
1310 <            return true;
1311 <            }
1312 <         } //chain can be extended
1313 <      }
1314 <   } //collect segment alignments into chains
1315 < */
1316 < return false; //no adapter parts found
1317 < }
974 >  }//for each 5' adapter
975 >  return trimmed;
976 > }
977  
978 < //convert qvs to/from phred64 from/to phread33
978 > //convert qvs to/from phred64 from/to phread33
979   void convertPhred(GStr& q) {
980   for (int i=0;i<q.length();i++) q[i]+=qv_cvtadd;
981   }
# Line 1325 | Line 984
984   for (int i=0;i<len;i++) q[i]+=qv_cvtadd;
985   }
986  
987 < bool getFastxRec(GLineReader& fq, GStr& rseq, GStr& rqv,
987 > bool getFastxRec(GLineReader& fq, GStr& rseq, GStr& rqv,
988            GStr& rname, GStr& rinfo, GStr& infname) {
989   rseq="";
990   rqv="";
# Line 1341 | Line 1000
1000        } //raw qseq format
1001   else { // FASTQ or FASTA */
1002   isfasta=(l[0]=='>');
1003 < if (!isfasta && l[0]!='@') GError("Error: fasta/fastq record marker not found(%s)\n%s\n",
1003 > if (!isfasta && l[0]!='@') GError("Error: fasta/fastq record marker not found(%s)\n%s\n",
1004        infname.chars(), l);
1005   GStr s(l);
1006   rname=&(l[1]);
1007   for (int i=0;i<rname.length();i++)
1008 <    if (rname[i]<=' ') {
1009 <       if (i<rname.length()-2) rinfo=rname.substr(i+1);
1010 <       rname.cut(i);
1011 <       break;
1008 >    if (rname[i]<=' ') {
1009 >       if (i<rname.length()-2) rinfo=rname.substr(i+1);
1010 >       rname.cut(i);
1011 >       break;
1012         }
1013    //now get the sequence
1014 < if ((l=fq.getLine())==NULL)
1014 > if ((l=fq.getLine())==NULL)
1015        GError("Error: unexpected EOF after header for read %s (%s)\n",
1016                     rname.chars(), infname.chars());
1017   rseq=l; //this must be the DNA line
1018   while ((l=fq.getLine())!=NULL) {
1019        //seq can span multiple lines
1020        if (l[0]=='>' || l[0]=='+') {
1021 <           fq.pushBack();
1021 >           fq.pushBack();
1022             break; //
1023             }
1024        rseq+=l;
1025 <      } //check for multi-line seq
1025 >      } //check for multi-line seq
1026   if (!isfasta) { //reading fastq quality values, which can also be multi-line
1027      if ((l=fq.getLine())==NULL)
1028          GError("Error: unexpected EOF after sequence for %s\n", rname.chars());
1029      if (l[0]!='+') GError("Error: fastq qv header marker not detected!\n");
1030 <    if ((l=fq.getLine())==NULL)
1030 >    if ((l=fq.getLine())==NULL)
1031          GError("Error: unexpected EOF after qv header for %s\n", rname.chars());
1032      rqv=l;
1033 <    //if (rqv.length()!=rseq.length())
1033 >    //if (rqv.length()!=rseq.length())
1034      //  GError("Error: qv len != seq len for %s\n", rname.chars());
1035      while (rqv.length()<rseq.length() && ((l=fq.getLine())!=NULL)) {
1036        rqv+=l; //append to qv string
1037        }
1038      }// fastq
1039   // } //<-- FASTA or FASTQ
1040 < rseq.upper(); //TODO: what if we care about masking?
1040 > rseq.upper();
1041   return true;
1042   }
1043  
1044 + #ifdef GDEBUG
1045 + void showTrim(GStr& s, int l5, int l3) {
1046 +  if (l5>0) {
1047 +    color_bg(c_red);
1048 +    }
1049 +  for (int i=0;i<s.length()-1;i++) {
1050 +    if (i && i==l5) color_resetbg();
1051 +    fprintf(stderr, "%c", s[i]);
1052 +    if (i==l3) color_bg(c_red);
1053 +   }
1054 +  fprintf(stderr, "%c", s[s.length()-1]);
1055 +  color_reset();
1056 +  fprintf(stderr, "\n");
1057 + }
1058 + #endif
1059 +
1060   char process_read(GStr& rname, GStr& rseq, GStr& rqv, int &l5, int &l3) {
1061 < //returns 0 if the read was untouched, 1 if it was just trimmed
1061 > //returns 0 if the read was untouched, 1 if it was just trimmed
1062   // and a trash code if it was trashed
1063   l5=0;
1064   l3=rseq.length()-1;
1065 + #ifdef GDEBUG
1066 +   //rseq.reverse();
1067 +   GMessage(">%s\n", rname.chars());
1068 +   GMessage("%s\n",rseq.chars());
1069 + #endif
1070   if (l3-l5+1<min_read_len) {
1071     return 's';
1072     }
# Line 1422 | Line 1102
1102     w5=0;
1103     w3=wseq.length()-1;
1104     }
1105 < if (a3len>0) {
1106 <  if (trim_adapter3(wseq, w5, w3)) {
1105 > char trim_code;
1106 > do {
1107 >  trim_code=0;
1108 >  if (trim_poly5(wseq, w5, w3, polyA_seed)) {
1109 >      trim_code='A';
1110 >      }
1111 >  else if (trim_poly5(wseq, w5, w3, polyT_seed)) {
1112 >      trim_code='T';
1113 >      }
1114 >  else if (trim_adapter5(wseq, w5, w3)) {
1115 >      trim_code='5';
1116 >      }
1117 >  if (trim_code) {
1118 >     #ifdef GDEBUG
1119 >      GMessage("#### TRIM by '%c' code ( w5-w3 = %d-%d ):\n",trim_code, w5,w3);
1120 >      showTrim(wseq, w5, w3);
1121 >     #endif
1122       int trimlen=wseq.length()-(w3-w5+1);
1123 <     num_trimmed3++;
1124 <     if (trimlen<min_trimmed3)
1125 <         min_trimmed3=trimlen;
1123 >     num_trimmed5++;
1124 >     if (trimlen<min_trimmed5)
1125 >         min_trimmed5=trimlen;
1126       l5+=w5;
1127       l3-=(wseq.length()-1-w3);
1128       if (w3-w5+1<min_read_len) {
1129 <         return '3';
1129 >         return trim_code;
1130           }
1131        //-- keep only the w5..w3 range
1132        wseq=wseq.substr(w5, w3-w5+1);
1133        if (!wqv.is_empty())
1134           wqv=wqv.substr(w5, w3-w5+1);
1135 <      }//some adapter was trimmed
1136 <   } //adapter trimming
1137 < if (a5len>0) {
1138 <  if (trim_adapter5(wseq, w5, w3)) {
1135 >      }// trimmed at 5' end
1136 > } while (trim_code);
1137 >
1138 > do {
1139 >  trim_code=0;
1140 >  if (trim_poly3(wseq, w5, w3, polyA_seed)) {
1141 >      trim_code='A';
1142 >      }
1143 >  else if (trim_poly3(wseq, w5, w3, polyT_seed)) {
1144 >      trim_code='T';
1145 >      }
1146 >  else if (trim_adapter3(wseq, w5, w3)) {
1147 >      trim_code='3';
1148 >      }
1149 >  if (trim_code) {
1150 >     #ifdef GDEBUG
1151 >     GMessage("#### TRIM by '%c' code ( w5-w3 = %d-%d ):\n",trim_code, w5,w3);
1152 >     showTrim(wseq, w5, w3);
1153 >     #endif
1154       int trimlen=wseq.length()-(w3-w5+1);
1155 <     num_trimmed5++;
1156 <     if (trimlen<min_trimmed5)
1157 <         min_trimmed5=trimlen;
1155 >     num_trimmed3++;
1156 >     if (trimlen<min_trimmed3)
1157 >         min_trimmed3=trimlen;
1158       l5+=w5;
1159       l3-=(wseq.length()-1-w3);
1160       if (w3-w5+1<min_read_len) {
1161 <         return '5';
1161 >         return trim_code;
1162           }
1163        //-- keep only the w5..w3 range
1164        wseq=wseq.substr(w5, w3-w5+1);
1165        if (!wqv.is_empty())
1166           wqv=wqv.substr(w5, w3-w5+1);
1167 <      }//some adapter was trimmed
1168 <   } //adapter trimming
1167 >      }//trimming at 3' end
1168 > } while (trim_code);
1169 >
1170 >
1171   if (doCollapse) {
1172     //keep read for later
1173     FqDupRec* dr=dhash.Find(wseq.chars());
1174     if (dr==NULL) { //new entry
1175 <          //if (prefix.is_empty())
1176 <             dhash.Add(wseq.chars(),
1175 >          //if (prefix.is_empty())
1176 >             dhash.Add(wseq.chars(),
1177                    new FqDupRec(&wqv, rname.chars()));
1178            //else dhash.Add(wseq.chars(), new FqDupRec(wqv.chars(),wqv.length()));
1179           }
# Line 1495 | Line 1207
1207         fprintf(f_out, "%s\n", rseq.chars()); //plain one-line fasta for now
1208         }
1209        else {
1210 <       fprintf(f_out, ">%s%08d\n%s\n", prefix.chars(), outcounter,
1210 >       fprintf(f_out, ">%s%08d\n%s\n", prefix.chars(), outcounter,
1211                            rseq.chars());
1212         }
1213       }
# Line 1506 | Line 1218
1218         fprintf(f_out, "%s\n+\n%s\n", rseq.chars(), rqv.chars());
1219         }
1220        else
1221 <       fprintf(f_out, "@%s_%08d\n%s\n+\n%s\n", prefix.chars(), outcounter,
1221 >       fprintf(f_out, "@%s_%08d\n%s\n+\n%s\n", prefix.chars(), outcounter,
1222                            rseq.chars(),rqv.chars() );
1223       }
1224   }
# Line 1514 | Line 1226
1226   void trash_report(char trashcode, GStr& rname, FILE* freport) {
1227   if (freport==NULL || trashcode<=' ') return;
1228   if (trashcode=='3' || trashcode=='5') {
1229 <   fprintf(freport, "%s\tA%c\n",rname.chars(),trashcode);
1229 >   fprintf(freport, "%s\ta%c\n",rname.chars(),trashcode);
1230     }
1231   else {
1232     fprintf(freport, "%s\t%c\n",rname.chars(),trashcode);
# Line 1606 | Line 1318
1318      }
1319   }
1320  
1321 < void setupFiles(FILE*& f_in, FILE*& f_in2, FILE*& f_out, FILE*& f_out2,
1322 <                       GStr& s, GStr& infname, GStr& infname2) {
1321 > void addAdapter(GVec<CASeqData>& adapters, GStr& seq) {
1322 > //TODO: prepare CASeqData here, and collect hexamers as well
1323 >
1324 > }
1325 >
1326 >
1327 > int loadAdapters(const char* fname) {
1328 >  GLineReader lr(fname);
1329 >  char* l;
1330 >  while ((l=lr.nextLine())!=NULL) {
1331 >   if (lr.length()<=3 || l[0]=='#') continue;
1332 >   if ( l[0]==' ' || l[0]=='\t' || l[0]==',' ||
1333 >        l[0]==';'|| l[0]==':' ) {
1334 >      int i=1;
1335 >      while (l[i]!=0 && isspace(l[i])) {
1336 >        i++;
1337 >        }
1338 >      if (l[i]!=0) {
1339 >        GStr s(&(l[i]));
1340 >      #ifdef GDEBUG
1341 >          //s.reverse();
1342 >      #endif
1343 >        addAdapter(adapters3, s);
1344 >        continue;
1345 >        }
1346 >      }
1347 >    else {
1348 >      GStr s(l);
1349 >      s.startTokenize("\t ;,:");
1350 >      GStr a5,a3;
1351 >      if (s.nextToken(a5))
1352 >         s.nextToken(a3);
1353 >      a5.upper();
1354 >      a3.upper();
1355 >     #ifdef GDEBUG
1356 >     //   a5.reverse();
1357 >     //   a3.reverse();
1358 >     #endif
1359 >      addAdapter(adapters5, a5);
1360 >      addAdapter(adapters3, a3);
1361 >      }
1362 >   }
1363 >   return adapters5.Count()+adapters3.Count();
1364 > }
1365 >
1366 > void setupFiles(FILE*& f_in, FILE*& f_in2, FILE*& f_out, FILE*& f_out2,
1367 >                       GStr& s, GStr& infname, GStr& infname2) {
1368   // uses outsuffix to generate output file names and open file handles as needed
1369   infname="";
1370   infname2="";
# Line 1635 | Line 1392
1392   s.startTokenize(",:");
1393   s.nextToken(infname);
1394   bool paired=s.nextToken(infname2);
1395 < if (fileExists(infname.chars())==0)
1395 > if (fileExists(infname.chars())==0)
1396      GError("Error: cannot find file %s!\n",infname.chars());
1397   GStr fname(getFileName(infname.chars()));
1398   GStr picmd;
# Line 1657 | Line 1414
1414   if (!paired) return;
1415   if (doCollapse) GError("Error: sorry, -C option cannot be used with paired reads!\n");
1416   // ---- paired reads:-------------
1417 < if (fileExists(infname2.chars())==0)
1417 > if (fileExists(infname2.chars())==0)
1418       GError("Error: cannot find file %s!\n",infname2.chars());
1419   picmd="";
1420   GStr fname2(getFileName(infname2.chars()));

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines