src/jalview/datamodel/CigarBase.java

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