Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/icecream/IceCreamAlignerJava.java @ 68:5028fdace37b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 16:23:26 -0400
parents
children
rev   line source
jpayne@68 1 package icecream;
jpayne@68 2
jpayne@68 3 import aligner.AlignmentResult;
jpayne@68 4
jpayne@68 5 public final class IceCreamAlignerJava extends IceCreamAligner {
jpayne@68 6
jpayne@68 7 IceCreamAlignerJava(){}
jpayne@68 8
jpayne@68 9 /**
jpayne@68 10 * @param query
jpayne@68 11 * @param ref
jpayne@68 12 * @param rstart
jpayne@68 13 * @param rstop
jpayne@68 14 * @param minScore Quit early if score drops below this
jpayne@68 15 * @param minRatio Don't return results if max score is less than this fraction of max possible score
jpayne@68 16 * @return
jpayne@68 17 */
jpayne@68 18 @Override
jpayne@68 19 public AlignmentResult alignForward(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore,
jpayne@68 20 final float minRatio) {
jpayne@68 21 final int arrayLength=rstop-rstart+1;
jpayne@68 22
jpayne@68 23 //Stack allocated; faster.
jpayne@68 24 final int[] array1=new int[arrayLength+1], array2=new int[arrayLength+1];
jpayne@68 25
jpayne@68 26 final int minPassingScore=(int)(query.length*minRatio*pointsMatch);
jpayne@68 27 final int minPassingScore3=minPassingScore-query.length*pointsMatch;
jpayne@68 28
jpayne@68 29 int[] prev=array1, next=array2;
jpayne@68 30 int maxScore=-999999;
jpayne@68 31 int maxQpos=-1;
jpayne@68 32 int maxRpos=-1;
jpayne@68 33
jpayne@68 34 for(int i=0; i<=arrayLength-query.length; i++){prev[i]=0;}
jpayne@68 35 for(int i=arrayLength-query.length, score=0; i<=arrayLength; i++, score+=pointsDel) {
jpayne@68 36 prev[i]=score;
jpayne@68 37 }
jpayne@68 38
jpayne@68 39 int currentRstart=rstart;
jpayne@68 40 for(int qpos=0; qpos<query.length; qpos++){
jpayne@68 41 prev[0]=pointsIns*qpos;
jpayne@68 42
jpayne@68 43 final byte q=query[qpos];
jpayne@68 44 int maxScoreThisPass=-9999;
jpayne@68 45 final int remainingBases=(query.length-qpos);
jpayne@68 46 final int remainingPoints=remainingBases*pointsMatch;
jpayne@68 47 final int minViableScore=minPassingScore3-remainingPoints;
jpayne@68 48 // int minViableRstart=rstop+1;
jpayne@68 49 for(int rpos=currentRstart, apos=1+currentRstart-rstart; rpos<=rstop; rpos++, apos++){
jpayne@68 50 final byte r=ref[rpos];
jpayne@68 51 final boolean match=(q==r);
jpayne@68 52 final int vScore=prev[apos]+pointsIns;
jpayne@68 53 final int hScore=next[apos-1]+pointsDel;
jpayne@68 54 final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
jpayne@68 55
jpayne@68 56 //Slow branchy code
jpayne@68 57 // final int score=Tools.max(vScore, hScore, dScore);
jpayne@68 58 // next[apos]=score;
jpayne@68 59 // if(score>=maxScoreThisPass){
jpayne@68 60 // maxScoreThisPass=score;
jpayne@68 61 // if(score>=maxScore){
jpayne@68 62 // maxScore=score;
jpayne@68 63 // maxQpos=qpos;
jpayne@68 64 // maxRpos=rpos;
jpayne@68 65 // }
jpayne@68 66 // }
jpayne@68 67
jpayne@68 68 //Should be branchless conditional moves
jpayne@68 69 int score=(dScore>=vScore ? dScore : vScore);
jpayne@68 70 score=(hScore>score ? hScore : score);
jpayne@68 71 next[apos]=score;
jpayne@68 72 maxScoreThisPass=(score>maxScoreThisPass ? score : maxScoreThisPass);
jpayne@68 73
jpayne@68 74 // minViableRstart=((score<minViableScore || rpos>minViableRstart) ? minViableRstart : rpos);
jpayne@68 75 }
jpayne@68 76 iters+=arrayLength;
jpayne@68 77 if(maxScoreThisPass<minScore){//Aggressive early exit
jpayne@68 78 return null;
jpayne@68 79 }
jpayne@68 80
jpayne@68 81 {//Safe early exit
jpayne@68 82 if(maxScoreThisPass<minViableScore){return null;}
jpayne@68 83 }
jpayne@68 84
jpayne@68 85 int[] temp=prev;
jpayne@68 86 prev=next;
jpayne@68 87 next=temp;
jpayne@68 88 }
jpayne@68 89
jpayne@68 90 maxScore=-999999;
jpayne@68 91 for(int rpos=rstart, apos=1; rpos<=rstop; rpos++, apos++){//Grab high score from last iteration
jpayne@68 92 int score=prev[apos];
jpayne@68 93 if(score>=maxScore){
jpayne@68 94 maxScore=score;
jpayne@68 95 maxQpos=query.length;
jpayne@68 96 maxRpos=rpos;
jpayne@68 97 }
jpayne@68 98 }
jpayne@68 99
jpayne@68 100 maxScore=(maxScore-pointsSub*query.length)/(pointsMatch-pointsSub);//Rescale 0 to length
jpayne@68 101 final float ratio=maxScore/(float)query.length;
jpayne@68 102
jpayne@68 103 if(ratio<minRatio){return null;}
jpayne@68 104 return new AlignmentResult(maxScore, maxQpos, maxRpos, query.length, ref.length, rstart, rstop, ratio);
jpayne@68 105 }
jpayne@68 106
jpayne@68 107 /**
jpayne@68 108 * @param query
jpayne@68 109 * @param ref
jpayne@68 110 * @param qstart
jpayne@68 111 * @param rstart
jpayne@68 112 * @param rstop
jpayne@68 113 * @param minScore Quit early if score drops below this
jpayne@68 114 * @param minRatio Don't return results if max score is less than this fraction of max possible score
jpayne@68 115 * @return
jpayne@68 116 */
jpayne@68 117 @Override
jpayne@68 118 public AlignmentResult alignForwardShort(final byte[] query, final byte[] ref, final int rstart, final int rstop, final int minScore,
jpayne@68 119 final float minRatio) {
jpayne@68 120
jpayne@68 121 final int arrayLength=query.length;
jpayne@68 122
jpayne@68 123 //Stack allocated; faster.
jpayne@68 124 final int[] array1=new int[arrayLength+1], array2=new int[arrayLength+1];
jpayne@68 125
jpayne@68 126 final int minPassingScore=(int)(query.length*minRatio);
jpayne@68 127 final int minPassingScore3=minPassingScore-query.length;
jpayne@68 128
jpayne@68 129 int[] prev=array1, next=array2;
jpayne@68 130 int maxScore=-999999;
jpayne@68 131 int maxQpos=-1;
jpayne@68 132 int maxRpos=-1;
jpayne@68 133
jpayne@68 134 for(int i=0; i<prev.length; i++) {
jpayne@68 135 prev[i]=pointsIns*i;
jpayne@68 136 }
jpayne@68 137
jpayne@68 138 for(int rpos=rstart; rpos<=rstop; rpos++){
jpayne@68 139 if(rstop-rpos<arrayLength){prev[0]=next[0]+pointsDel;}
jpayne@68 140
jpayne@68 141 final byte r=ref[rpos];
jpayne@68 142 int score=0;
jpayne@68 143
jpayne@68 144 //In Java, the unsplit loop is faster
jpayne@68 145 //-XX:+UseSuperWord seems to have no impact on speed.
jpayne@68 146 //Might be worth packing the query and ref into int arrays and trying again.
jpayne@68 147 for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
jpayne@68 148 final byte q=query[qpos];
jpayne@68 149 final boolean match=(q==r);
jpayne@68 150 final int vScore=prev[apos]+pointsIns;
jpayne@68 151 final int hScore=next[apos-1]+pointsDel;
jpayne@68 152 final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
jpayne@68 153
jpayne@68 154 score=(dScore>=vScore ? dScore : vScore);
jpayne@68 155 score=(hScore>score ? hScore : score);
jpayne@68 156
jpayne@68 157 next[apos]=score;
jpayne@68 158 }
jpayne@68 159
jpayne@68 160 // //Inner DV loop
jpayne@68 161 // for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
jpayne@68 162 // final int q=query[qpos];
jpayne@68 163 // final boolean match=(q==r);
jpayne@68 164 // final int vScore=prev[apos]+pointsIns;
jpayne@68 165 // final int dScore=(match ? pointsMatch : pointsSub)+prev[apos-1];
jpayne@68 166 //
jpayne@68 167 // score=(dScore>=vScore ? dScore : vScore);
jpayne@68 168 //
jpayne@68 169 // next[apos]=score;
jpayne@68 170 // }
jpayne@68 171 //
jpayne@68 172 // //Inner I loop
jpayne@68 173 // for(int qpos=0, apos=1; qpos<arrayLength; qpos++, apos++){
jpayne@68 174 // final int hScore=next[apos-1]+pointsDel;
jpayne@68 175 //
jpayne@68 176 // score=next[apos];
jpayne@68 177 // score=(hScore>score ? hScore : score);
jpayne@68 178 //
jpayne@68 179 // next[apos]=score;
jpayne@68 180 // }
jpayne@68 181
jpayne@68 182 itersShort+=arrayLength;
jpayne@68 183
jpayne@68 184 if(score>=maxScore){
jpayne@68 185 maxScore=score;
jpayne@68 186 maxQpos=arrayLength-1;
jpayne@68 187 maxRpos=rpos;
jpayne@68 188 }
jpayne@68 189
jpayne@68 190 int[] temp=prev;
jpayne@68 191 prev=next;
jpayne@68 192 next=temp;
jpayne@68 193 }
jpayne@68 194
jpayne@68 195 maxScore=(maxScore-pointsSub*query.length)/(pointsMatch-pointsSub);//Rescale 0 to length
jpayne@68 196 final float ratio=maxScore/(float)query.length;
jpayne@68 197
jpayne@68 198 if(ratio<minRatio){return null;}
jpayne@68 199
jpayne@68 200 return new AlignmentResult(maxScore, maxQpos, maxRpos, query.length, ref.length, rstart, rstop, ratio);
jpayne@68 201 }
jpayne@68 202
jpayne@68 203 /*--------------------------------------------------------------*/
jpayne@68 204 /*---------------- Getters ----------------*/
jpayne@68 205 /*--------------------------------------------------------------*/
jpayne@68 206
jpayne@68 207 @Override
jpayne@68 208 long iters(){return iters;}
jpayne@68 209
jpayne@68 210 @Override
jpayne@68 211 long itersShort(){return itersShort;}
jpayne@68 212
jpayne@68 213 /*--------------------------------------------------------------*/
jpayne@68 214 /*---------------- Fields ----------------*/
jpayne@68 215 /*--------------------------------------------------------------*/
jpayne@68 216
jpayne@68 217 long iters = 0;
jpayne@68 218 long itersShort = 0;
jpayne@68 219
jpayne@68 220 /*--------------------------------------------------------------*/
jpayne@68 221 /*---------------- Constants ----------------*/
jpayne@68 222 /*--------------------------------------------------------------*/
jpayne@68 223
jpayne@68 224 public static final int pointsMatch = 1;
jpayne@68 225 public static final int pointsSub = -1;
jpayne@68 226 public static final int pointsDel = -2;
jpayne@68 227 public static final int pointsIns = -2;
jpayne@68 228
jpayne@68 229 }