src/jalview/datamodel/CigarBase.java

   1 package jalview.datamodel;
   2
   3 public abstract class CigarBase
   4 {
   5   /**
   6    * Base class for compact idiosyncratic representation of gaps and aligned residues
   7    * Regards to Tom Oldfield for his DynamicArray class.
   8    * 17th July 2006
   9    * Not thread safe.
  10    */
  11   public CigarBase()
  12   {
  13     // nothing to be done (probably)
  14   }
  15
  16   protected int length = 0;
  17   protected int _inc_length = 10; // extension range for addition of new operations
  18   protected char[] operation = null;
  19   protected int[] range = null;
  20   /**
  21    * Range of Hidden residues in seq (translated as deleted in seq)
  22    */
  23   public static final char D = 'D'; /**
  24   * Range of insertions to seq
  25   */
  26  public static final char I = 'I'; /**
  27   * Range of aligned residues
  28   */
  29  public static final char M = 'M';
  30   static protected final char _case_shift = 'a' - 'A';
  31   /**
  32    * Ugly function to get edited sequence string, start and end symbol positions and the deletion regions as an array of int pairs
  33    * May return null for an empty cigar string.
  34    * May return null for deletion ranges if there are none.
  35    * @param reference - the symbol sequence to apply the cigar operations to (or null if no sequence)
  36    * @param GapChar - the symbol to use for Insert operations
  37    * @return Object[] { String, int[] {start, startcol, end, endcol}, int[][3] {start, end, col} or null} the gapped sequence, first and last residue index, and the deletion ranges on the reference sequence
  38    */
  39   public Object[] getSequenceAndDeletions(String reference, char GapChar)
  40   {
  41     int rlength=0;
  42     int[][] deletions = new int[length][];
  43     int[][] trunc_deletions = null;
  44     StringBuffer sq = new StringBuffer();
  45     int cursor = 0, alcursor=0,start = 0, startpos=0, end = 0, endpos=0, delcount = -1;
  46     boolean consecutive_del = false;
  47     if (length == 0)
  48     {
  49       return null;
  50     }
  51     if (reference!=null)
  52       rlength=reference.length();
  53     boolean modstart = true;
  54     for (int i = 0; i < length; i++)
  55     {
  56       switch (operation[i])
  57       {
  58         case D:
  59           if (!consecutive_del)
  60           {
  61             deletions[++delcount] = new int[]
  62                 {
  63                 cursor, 0, alcursor};
  64           }
  65           cursor += range[i];
  66           deletions[delcount][1] = cursor - 1;
  67           consecutive_del = true;
  68           break;
  69         case I:
  70           consecutive_del = false;
  71           for (int r = 0; r < range[i]; r++)
  72           {
  73             sq.append(GapChar);
  74             alcursor++;
  75           }
  76           break;
  77         case M:
  78           consecutive_del = false;
  79           if (modstart)
  80           {
  81             start = cursor;
  82             startpos=alcursor;
  83             modstart = false;
  84           }
  85           if (reference!=null) {
  86             int sbend = cursor+range[i];
  87             if (sbend>rlength) {
  88               sq.append(reference.substring(cursor, rlength));
  89               while (sbend-- >= rlength)
  90               {
  91                 sq.append(GapChar);
  92               }
  93             } else {
  94               sq.append(reference.substring(cursor, sbend));
  95             }
  96           }
  97           alcursor+=range[i];
  98           cursor += range[i];
  99           end = cursor - 1;
 100           endpos = alcursor;
 101           break;
 102         default:
 103           throw new Error("Unknown SeqCigar operation '" + operation[i] + "'");
 104       }
 105     }
 106     if (++delcount > 0)
 107     {
 108       trunc_deletions = new int[delcount][];
 109       System.arraycopy(deletions, 0, trunc_deletions, 0, delcount);
 110     }
 111     deletions = null;
 112     return new Object[]
 113         {
 114         ((reference!=null) ? sq.toString() : null),
 115         new int[] {
 116         start, startpos, end, endpos}, trunc_deletions};
 117   }
 118
 119   /**
 120    * turn a cigar string into a series of operation range pairs
 121    * @param cigarString String
 122    * @return object[] {char[] operation, int[] range}
 123    * @throws java.lang.Exception for improperly formated cigar strings or ones with unknown operations
 124    */
 125   public static Object[] parseCigarString(String cigarString)
 126       throws Exception
 127   {
 128     int ops = 0;
 129     for (int i = 0, l = cigarString.length(); i < l; i++)
 130     {
 131       char c = cigarString.charAt(i);
 132       if (c == M || c == (M - _case_shift) || c == I || c == (I - _case_shift) ||
 133           c == D || c == (D - _case_shift))
 134       {
 135         ops++;
 136       }
 137     }
 138     char[] operation = new char[ops];
 139     int[] range = new int[ops];
 140     int op = 0;
 141     int i = 0, l = cigarString.length();
 142     while (i < l)
 143     {
 144       char c;
 145       int j = i;
 146       do
 147       {
 148         c = cigarString.charAt(j++);
 149       }
 150       while (c >= '0' && c <= '9' && j < l);
 151       if (j >= l && c >= '0' && c <= '9')
 152       {
 153         throw new Exception("Unterminated cigar string.");
 154       }
 155       try
 156       {
 157         String rangeint = cigarString.substring(i, j - 1);
 158         range[op] = Integer.parseInt(rangeint);
 159         i = j;
 160       }
 161       catch (Exception e)
 162       {
 163         throw new Error("Implementation bug in parseCigarString");
 164       }
 165       if (c >= 'a' && c <= 'z')
 166       {
 167         c -= _case_shift;
 168       }
 169       if ( (c == M || c == I || c == D))
 170       {
 171         operation[op++] = c;
 172       }
 173       else
 174       {
 175         throw new Exception("Unexpected operation '" + c +
 176                             "' in cigar string (position " + i + " in '" +
 177                             cigarString + "'");
 178       }
 179     }
 180     return new Object[]
 181         {
 182         operation, range};
 183   }
 184
 185   /**
 186    * add an operation to cigar string
 187    * @param op char
 188    * @param range int
 189    */
 190   public void addOperation(char op, int range)
 191   {
 192     if (op >= 'a' && op <= 'z')
 193     {
 194       op -= _case_shift;
 195     }
 196     if (op != M && op != D && op != I)
 197     {
 198       throw new Error("Implementation error. Invalid operation string.");
 199     }
 200     if (range<=0)
 201       throw new Error("Invalid range string (must be non-zero positive number)");
 202     int lngth = 0;
 203     if (operation == null)
 204     {
 205       this.operation = new char[_inc_length];
 206       this.range = new int[_inc_length];
 207     }
 208     if (length + 1 == operation.length)
 209     {
 210       char[] ops = this.operation;
 211       this.operation = new char[length + 1 + _inc_length];
 212       System.arraycopy(ops, 0, this.operation, 0, length);
 213       ops = null;
 214       int[] rng = this.range;
 215       this.range = new int[length + 1 + _inc_length];
 216       System.arraycopy(rng, 0, this.range, 0, length);
 217       rng = null;
 218     }
 219     if ((length>0) && (operation[length-1]==op))
 220       length--; // modify existing operation.
 221     else
 222       this.range[length]=0; // reset range
 223     this.operation[length] = op;
 224     this.range[length++] += range;
 225   }
 226
 227   /**
 228    * semi-efficient insert an operation on the current cigar string set at column pos (from 1)
 229    * NOTE: Insertion operations simply extend width of cigar result - affecting registration of alignment
 230    * Deletion ops will shorten length of result - and affect registration of alignment
 231    * Match ops will also affect length of result - affecting registration of alignment
 232    * (ie "10M".insert(4,I,3)->"4M3I3M") - (replace?)
 233    * (ie "10M".insert(4,D,3)->"4M3D3M") - (shortens alignment)
 234    * (ie "5I5M".insert(4,I,3)->"8I5M") - real insertion
 235    * (ie "5I5M".insert(4,D,3)->"4I2D3M") - shortens aligment - I's are removed, Ms changed to Ds
 236    * (ie "10M".insert(4,M,3)->"13M")  - lengthens - Is changed to M, Ds changed to M.
 237    * (ie "5I5M".insert(4,M,3)->"4I8M") - effectively shifts sequence left by 1 residue and extends it by 3
 238    * ( "10D5M".insert(-1,M,3)->"3M7D5M")
 239    * ( "10D5M".insert(0,M,3)->"7D8M")
 240    * ( "10D5M".insert(1,M,3)->"10D8M")
 241    *
 242    * ( "1M10D5M".insert(0,M,3)->"1M10D8M")
 243    * ( "1M10D5M".insert(1,M,3)->"
 244    *
 245    * if pos is beyond width - I operations are added before the operation
 246    * @param pos int -1, 0-length of visible region, or greater to append new ops (with insertions in between)
 247    * @param op char
 248    * @param range int
 249   public void addOperationAt(int pos, char op, int range)
 250   {
 251     int cursor = -1; // mark the position for the current operation being edited.
 252     int o = 0;
 253     boolean last_d = false; // previous op was a deletion.
 254     if (pos < -1)
 255       throw new Error("pos<-1 is not supported.");
 256     while (o<length) {
 257       if (operation[o] != D)
 258       {
 259         if ( (cursor + this.range[o]) < pos)
 260         {
 261           cursor += this.range[o];
 262           o++;
 263           last_d=false;
 264         }
 265         else
 266         {
 267           break;
 268         }
 269       }
 270       else {
 271         last_d=true;
 272         o++;
 273       }
 274     }
 275     if (o==length) {
 276       // must insert more operations before pos
 277       if (pos-cursor>0)
 278         addInsertion(pos-cursor);
 279       // then just add the new operation. Regardless of what it is.
 280       addOperation(op, range);
 281     } else {
 282       int diff = pos - cursor;
 283
 284       int e_length = length-o; // new edit operation array length.
 285       // diff<0 - can only happen before first insertion or match. - affects op and all following
 286       // dif==0 - only when at first position of existing op -
 287       // diff>0 - must preserve some existing operations
 288       int[] e_range = new int[e_length];
 289       System.arraycopy(this.range, o, e_range, 0, e_length);
 290       char[] e_op = new char[e_length];
 291       System.arraycopy(this.operation, o, e_op, 0, e_length);
 292       length = o; // can now use add_operation to extend list.
 293       int e_o=0; // current operation being edited.
 294       switch (op) {
 295         case M:
 296           switch (e_op[e_o])
 297           {
 298             case M:
 299               if (last_d && diff <= 0)
 300               {
 301                 // reduce D's, if possible
 302                 if (range<=this.range[o-1]) {
 303                   this.range[o - 1] -= range;
 304                 } else {
 305                   this.range[o-1]=0;
 306                 }
 307                 if (this.range[o-1]==0)
 308                   o--; // lose this op.
 309               }
 310               e_range[e_o] += range; // just add more matched residues
 311               break;
 312             case I:
 313               // change from insertion to match
 314               if (last_d && diff<=0)
 315               {
 316                 // reduce D's, if possible
 317                 if (range<=this.range[o-1]) {
 318                   this.range[o - 1] -= range;
 319                 } else {
 320                   this.range[o-1]=0;
 321                 }
 322                 if (this.range[o-1]==0)
 323                   o--; // lose this op.
 324               }
 325               e_range[e_o]
 326                     break;
 327                 default:
 328                   throw new Inp
 329                       }
 330
 331                       break;
 332                 case I:
 333                   break;
 334                 case D:
 335               }
 336           break;
 337         default:
 338           throw new Error("Implementation Error: Unknown operation in addOperation!");
 339       }
 340       // finally, add remaining ops.
 341       while (e_o<e_length) {
 342         addOperation(e_op[e_o], e_range[e_o]);
 343         e_o++;
 344       }
 345     }
 346   }
 347 **/
 348   /**
 349    * Mark residues from start to end (inclusive) as deleted from the alignment, and removes any insertions.
 350    * @param start int
 351    * @param end int
 352    */
 353   public void deleteRange(int start, int end) {
 354     if (length==0) {
 355       // nothing to do here
 356       return;
 357     }
 358     if (start<0 || start>end)
 359       throw new Error("Implementation Error: deleteRange out of bounds: start must be non-negative and less than end.");
 360     // find beginning
 361     int cursor = 0; // mark the position for the current operation being edited.
 362     int rlength=1+end-start; // number of positions to delete
 363     int oldlen=length;
 364     int o = 0;
 365     boolean editing=false;
 366     char[] oldops = operation;
 367     int[] oldrange = range;
 368     length=0;
 369     operation = null;
 370     range = null;
 371     while (o<oldlen && cursor<=end && rlength>0) {
 372       if (oldops[o] == D) {
 373         // absorbed into new deleted region.
 374         addDeleted(oldrange[o++]);
 375         continue;
 376       }
 377
 378       int remain = oldrange[o]; // number of op characters left to edit
 379       if (!editing) {
 380         if ( (cursor + remain) <= start)
 381         {
 382           addOperation(oldops[o],oldrange[o]);
 383           cursor+=oldrange[o++];
 384           continue; // next operation
 385         }
 386         editing=true;
 387         // add operations before hidden region
 388         if (start-cursor>0) {
 389           addOperation(oldops[o], start- cursor);
 390           remain -= start - cursor;
 391         }
 392       }
 393       // start inserting new ops
 394       if (o<oldlen && editing && rlength>0 && remain>0) {
 395         switch (oldops[o]) {
 396           case M:
 397             if (rlength>remain) {
 398               addDeleted(remain);
 399             } else {
 400               addDeleted(rlength);
 401               if (remain-rlength>0)
 402                 this.addOperation(M,remain-rlength); // add remaining back.
 403               rlength=0;
 404               remain=0;
 405             }
 406             break;
 407           case I:
 408             if (remain-rlength>0) {
 409               // only remove some gaps
 410               addInsertion(remain-rlength);
 411               rlength=0;
 412             }
 413             break;
 414           case D:
 415             throw new Error("Implementation error."); // do nothing;
 416           default:
 417             throw new Error("Implementation Error! Unknown operation '"+oldops[o]+"'");
 418         }
 419         rlength-=remain;
 420         remain = oldrange[++o]; // number of op characters left to edit
 421       }
 422     }
 423     // add remaining
 424     while (o<oldlen) {
 425       addOperation(oldops[o],oldrange[o++]);
 426     }
 427     //if (cursor<(start+1)) {
 428       // ran out of ops - nothing to do here ?
 429      // addInsertion(start-cursor);
 430     //}
 431   }
 432   /**
 433    * sum of ranges in cigar string
 434    * @return int number of residues hidden, matched, or gaps inserted into sequence
 435    */
 436   public int getFullWidth()
 437   {
 438     int w = 0;
 439     if (range != null)
 440     {
 441       for (int i = 0; i < length; i++)
 442       {
 443         w += range[i];
 444       }
 445     }
 446     return w;
 447   }
 448
 449   /**
 450    * Visible length of aligned sequence
 451    * @return int length of including gaps and less hidden regions
 452    */
 453   public int getWidth()
 454   {
 455     int w = 0;
 456     if (range != null)
 457     {
 458       for (int i = 0; i < length; i++)
 459       {
 460         if (operation[i] == M || operation[i] == I)
 461         {
 462           w += range[i];
 463         }
 464       }
 465     }
 466     return w;
 467   }
 468   /**
 469    * mark a range of inserted residues
 470    * @param range int
 471    */
 472   public void addInsertion(int range)
 473   {
 474     this.addOperation(I, range);
 475   }
 476
 477   /**
 478    * mark the next range residues as hidden (not aligned) or deleted
 479    * @param range int
 480    */
 481   public void addDeleted(int range)
 482   {
 483     this.addOperation(D, range);
 484   }
 485
 486   /**
 487    * Modifies operation list to delete columns from start to end (inclusive)
 488    * editing will remove insertion operations, and convert matches to deletions
 489    * @param start alignment column
 490    * @param end alignment column
 491    * @return boolean true if residues were marked as deleted.
 492   public boolean deleteRange(int start, int end)
 493   {
 494     boolean deleted = false;
 495     int op = 0, prevop = -1, firstm = -1,
 496         lastm = -1, postop = -1;
 497     int width = 0; // zero'th column
 498     if (length > 0)
 499     {
 500       // find operation bracketing start of the range
 501       do
 502       {
 503         if (operation[op] != D)
 504         {
 505           width += range[prevop = op];
 506         }
 507         op++;
 508       }
 509       while (op < length && width < start);
 510     }
 511     if (width < start)
 512     {
 513       // run off end - add more operations up to deletion.
 514       addInsertion(start - width);
 515     }
 516     else
 517     {
 518       // edit existing operations.
 519       op = prevop;
 520       width -= range[prevop];
 521       int[] oldrange = range;
 522       char[] oldops = operation;
 523       range = new int[oldrange.length];
 524       operation = new char[oldops.length];
 525       if (op < length)
 526       {
 527         do
 528         {
 529           if (operation[op] != D)
 530           {
 531             width += range[postop = op];
 532           }
 533           op++;
 534         }
 535         while (op < length && width <= end);
 536       }
 537     }
 538     if (deleted == true)
 539     {
 540       addDeleted(end - start + 1);
 541     }
 542     return deleted;
 543   }
 544 */
 545   /**
 546    * Return an ENSEMBL style cigar string where D may indicates excluded parts of seq
 547    * @return String of form ([0-9]+[IMD])+
 548    */
 549   public String getCigarstring()
 550   {
 551     StringBuffer cigarString = new StringBuffer();
 552     for (int i = 0; i < length; i++)
 553     {
 554       cigarString.append("" + range[i]);
 555       cigarString.append(operation[i]);
 556     }
 557     return cigarString.toString();
 558   }
 559 }