2 * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8)
3 * Copyright (C) 2012 J Procter, AM Waterhouse, LM Lui, J Engelhardt, G Barton, M Clamp, S Searle
5 * This file is part of Jalview.
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 of the License, or (at your option) any later version.
11 * Jalview is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty
13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 * PURPOSE. See the GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along with Jalview. If not, see <http://www.gnu.org/licenses/>.
18 package jalview.datamodel;
22 public abstract class CigarBase
25 * Base class for compact idiosyncratic representation of gaps and aligned
26 * residues Regards to Tom Oldfield for his DynamicArray class. 17th July 2006
31 // nothing to be done (probably)
34 protected int length = 0;
36 protected int _inc_length = 10; // extension range for addition of new
40 protected char[] operation = null;
42 protected int[] range = null;
45 * Range of Hidden residues in seq (translated as deleted in seq)
47 public static final char D = 'D';
50 * Range of insertions to seq
52 public static final char I = 'I';
55 * Range of aligned residues
57 public static final char M = 'M';
59 static protected final char _case_shift = 'a' - 'A';
62 * Ugly function to get edited sequence string, start and end symbol positions
63 * and the deletion regions as an array of int pairs May return null for an
64 * empty cigar string. May return null for deletion ranges if there are none.
67 * - the symbol sequence to apply the cigar operations to (or null if
70 * - the symbol to use for Insert operations
71 * @return Object[] { String, int[] {start, startcol, end, endcol}, int[][3]
72 * {start, end, col} or null} the gapped sequence, first and last
73 * residue index, and the deletion ranges on the reference sequence
75 public Object[] getSequenceAndDeletions(String reference, char GapChar)
78 int[][] deletions = new int[length][];
79 int[][] trunc_deletions = null;
80 StringBuffer sq = new StringBuffer();
81 int cursor = 0, alcursor = 0, start = 0, startpos = 0, end = 0, endpos = 0, delcount = -1;
82 boolean consecutive_del = false;
87 if (reference != null)
89 rlength = reference.length();
91 boolean modstart = true;
92 for (int i = 0; i < length; i++)
99 deletions[++delcount] = new int[]
100 { cursor, 0, alcursor };
103 deletions[delcount][1] = cursor - 1;
104 consecutive_del = true;
107 consecutive_del = false;
108 for (int r = 0; r < range[i]; r++)
115 consecutive_del = false;
122 if (reference != null)
124 int sbend = cursor + range[i];
127 sq.append(reference.substring(cursor, rlength));
128 while (sbend-- >= rlength)
135 sq.append(reference.substring(cursor, sbend));
138 alcursor += range[i];
144 throw new Error("Unknown SeqCigar operation '" + operation[i] + "'");
149 trunc_deletions = new int[delcount][];
150 System.arraycopy(deletions, 0, trunc_deletions, 0, delcount);
154 { ((reference != null) ? sq.toString() : null), new int[]
155 { start, startpos, end, endpos }, trunc_deletions };
158 protected void compact_operations()
161 if (operation == null)
165 char last = operation[0];
168 if (last == operation[i])
170 range[i - 1] += range[i];
174 System.arraycopy(range, i + 1, range, i, r);
175 System.arraycopy(operation, i + 1, operation, i, r);
181 last = operation[i++];
187 * turn a cigar string into a series of operation range pairs
191 * @return object[] {char[] operation, int[] range}
192 * @throws java.lang.Exception
193 * for improperly formated cigar strings or ones with unknown
196 public static Object[] parseCigarString(String cigarString)
200 for (int i = 0, l = cigarString.length(); i < l; i++)
202 char c = cigarString.charAt(i);
203 if (c == M || c == (M - _case_shift) || c == I
204 || c == (I - _case_shift) || c == D || c == (D - _case_shift))
209 char[] operation = new char[ops];
210 int[] range = new int[ops];
212 int i = 0, l = cigarString.length();
219 c = cigarString.charAt(j++);
220 } while (c >= '0' && c <= '9' && j < l);
221 if (j >= l && c >= '0' && c <= '9')
223 throw new Exception("Unterminated cigar string.");
227 String rangeint = cigarString.substring(i, j - 1);
228 range[op] = Integer.parseInt(rangeint);
230 } catch (Exception e)
232 throw new Error("Implementation bug in parseCigarString");
234 if (c >= 'a' && c <= 'z')
238 if ((c == M || c == I || c == D))
244 throw new Exception("Unexpected operation '" + c
245 + "' in cigar string (position " + i + " in '"
246 + cigarString + "'");
250 { operation, range };
254 * add an operation to cigar string
261 public void addOperation(char op, int range)
263 if (op >= 'a' && op <= 'z')
267 if (op != M && op != D && op != I)
269 throw new Error("Implementation error. Invalid operation string.");
273 return; // No Operation to add.
278 "Invalid range string (must be zero or positive number)");
281 if (operation == null)
283 this.operation = new char[_inc_length];
284 this.range = new int[_inc_length];
286 if (length + 1 == operation.length)
288 char[] ops = this.operation;
289 this.operation = new char[length + 1 + _inc_length];
290 System.arraycopy(ops, 0, this.operation, 0, length);
292 int[] rng = this.range;
293 this.range = new int[length + 1 + _inc_length];
294 System.arraycopy(rng, 0, this.range, 0, length);
297 if ((length > 0) && (operation[length - 1] == op))
299 length--; // modify existing operation.
303 this.range[length] = 0; // reset range
305 this.operation[length] = op;
306 this.range[length++] += range;
310 * semi-efficient insert an operation on the current cigar string set at
311 * column pos (from 1) NOTE: Insertion operations simply extend width of cigar
312 * result - affecting registration of alignment Deletion ops will shorten
313 * length of result - and affect registration of alignment Match ops will also
314 * affect length of result - affecting registration of alignment (ie
315 * "10M".insert(4,I,3)->"4M3I3M") - (replace?) (ie
316 * "10M".insert(4,D,3)->"4M3D3M") - (shortens alignment) (ie
317 * "5I5M".insert(4,I,3)->"8I5M") - real insertion (ie
318 * "5I5M".insert(4,D,3)->"4I2D3M") - shortens aligment - I's are removed, Ms
319 * changed to Ds (ie "10M".insert(4,M,3)->"13M") - lengthens - Is changed to
320 * M, Ds changed to M. (ie "5I5M".insert(4,M,3)->"4I8M") - effectively shifts
321 * sequence left by 1 residue and extends it by 3 (
322 * "10D5M".insert(-1,M,3)->"3M7D5M") ( "10D5M".insert(0,M,3)->"7D8M") (
323 * "10D5M".insert(1,M,3)->"10D8M") ( "1M10D5M".insert(0,M,3)->"1M10D8M") (
324 * "1M10D5M".insert(1,M,3)->"
326 * if pos is beyond width - I operations are added before the operation
329 * int -1, 0-length of visible region, or greater to append new ops
330 * (with insertions in between)
334 * int public void addOperationAt(int pos, char op, int range) { int
335 * cursor = -1; // mark the position for the current operation being
336 * edited. int o = 0; boolean last_d = false; // previous op was a
337 * deletion. if (pos < -1) throw new
338 * Error("pos<-1 is not supported."); while (o<length) { if
339 * (operation[o] != D) { if ( (cursor + this.range[o]) < pos) {
340 * cursor += this.range[o]; o++; last_d=false; } else { break; } }
341 * else { last_d=true; o++; } } if (o==length) { // must insert more
342 * operations before pos if (pos-cursor>0) addInsertion(pos-cursor);
343 * // then just add the new operation. Regardless of what it is.
344 * addOperation(op, range); } else { int diff = pos - cursor;
346 * int e_length = length-o; // new edit operation array length. //
347 * diff<0 - can only happen before first insertion or match. -
348 * affects op and all following // dif==0 - only when at first
349 * position of existing op - // diff>0 - must preserve some existing
350 * operations int[] e_range = new int[e_length];
351 * System.arraycopy(this.range, o, e_range, 0, e_length); char[] e_op
352 * = new char[e_length]; System.arraycopy(this.operation, o, e_op, 0,
353 * e_length); length = o; // can now use add_operation to extend
354 * list. int e_o=0; // current operation being edited. switch (op) {
355 * case M: switch (e_op[e_o]) { case M: if (last_d && diff <= 0) { //
356 * reduce D's, if possible if (range<=this.range[o-1]) { this.range[o
357 * - 1] -= range; } else { this.range[o-1]=0; } if
358 * (this.range[o-1]==0) o--; // lose this op. } e_range[e_o] +=
359 * range; // just add more matched residues break; case I: // change
360 * from insertion to match if (last_d && diff<=0) { // reduce D's, if
361 * possible if (range<=this.range[o-1]) { this.range[o - 1] -= range;
362 * } else { this.range[o-1]=0; } if (this.range[o-1]==0) o--; // lose
363 * this op. } e_range[e_o] break; default: throw new Inp }
365 * break; case I: break; case D: } break; default: throw new
366 * Error("Implementation Error: Unknown operation in addOperation!");
367 * } // finally, add remaining ops. while (e_o<e_length) {
368 * addOperation(e_op[e_o], e_range[e_o]); e_o++; } } }
371 * Mark residues from start to end (inclusive) as deleted from the alignment,
372 * and removes any insertions.
378 * @return deleted int - number of symbols marked as deleted
380 public int deleteRange(int start, int end)
385 // nothing to do here
388 if (start < 0 || start > end)
391 "Implementation Error: deleteRange out of bounds: start must be non-negative and less than end.");
394 int cursor = 0; // mark the position for the current operation being edited.
395 int rlength = 1 + end - start; // number of positions to delete
398 boolean editing = false;
399 char[] oldops = operation;
400 int[] oldrange = range;
404 compact_operations();
405 while (o < oldlen && cursor <= end && rlength > 0)
409 // absorbed into new deleted region.
410 addDeleted(oldrange[o++]);
414 int remain = oldrange[o]; // number of op characters left to edit
417 if ((cursor + remain) <= start)
419 addOperation(oldops[o], oldrange[o]);
420 cursor += oldrange[o++];
421 continue; // next operation
424 // add operations before hidden region
425 if (start - cursor > 0)
427 addOperation(oldops[o], start - cursor);
428 remain -= start - cursor;
431 // start inserting new ops
432 if (o < oldlen && editing && rlength > 0 && remain > 0)
437 if (rlength > remain)
446 if (remain - rlength > 0)
448 this.addOperation(M, remain - rlength); // add remaining back.
455 if (remain - rlength > 0)
457 // only remove some gaps
458 addInsertion(remain - rlength);
463 throw new Error("Implementation error."); // do nothing;
465 throw new Error("Implementation Error! Unknown operation '"
469 remain = oldrange[++o]; // number of op characters left to edit
475 addOperation(oldops[o], oldrange[o++]);
477 // if (cursor<(start+1)) {
478 // ran out of ops - nothing to do here ?
479 // addInsertion(start-cursor);
485 * Deleted regions mean that there will be discontinuous sequence numbering in
486 * the sequence returned by getSeq(char).
488 * @return true if there deletions
490 public boolean hasDeletedRegions()
492 for (int i = 0; i < length; i++)
494 if (operation[i] == D)
503 * enumerate the ranges on seq that are marked as deleted in this cigar
505 * @return int[] { vis_start, sym_start, length }
507 public int[] getDeletedRegions()
513 Vector dr = new Vector();
514 int cursor = 0, vcursor = 0;
515 for (int i = 0; i < length; i++)
517 switch (operation[i])
525 dr.addElement(new int[]
526 { vcursor, cursor, range[i] });
534 int[] delregions = new int[dr.size() * 3];
535 for (int i = 0, l = dr.size(); i < l; i++)
537 int[] reg = (int[]) dr.elementAt(i);
538 delregions[i * 3] = reg[0];
539 delregions[i * 3 + 1] = reg[1];
540 delregions[i * 3 + 2] = reg[2];
546 * sum of ranges in cigar string
548 * @return int number of residues hidden, matched, or gaps inserted into
551 public int getFullWidth()
556 for (int i = 0; i < length; i++)
565 * Visible length of aligned sequence
567 * @return int length of including gaps and less hidden regions
569 public int getWidth()
574 for (int i = 0; i < length; i++)
576 if (operation[i] == M || operation[i] == I)
586 * mark a range of inserted residues
591 public void addInsertion(int range)
593 this.addOperation(I, range);
597 * mark the next range residues as hidden (not aligned) or deleted
602 public void addDeleted(int range)
604 this.addOperation(D, range);
608 * Modifies operation list to delete columns from start to end (inclusive)
609 * editing will remove insertion operations, and convert matches to deletions
615 * @return boolean true if residues were marked as deleted. public boolean
616 * deleteRange(int start, int end) { boolean deleted = false; int op =
617 * 0, prevop = -1, firstm = -1, lastm = -1, postop = -1; int width =
618 * 0; // zero'th column if (length > 0) { // find operation bracketing
619 * start of the range do { if (operation[op] != D) { width +=
620 * range[prevop = op]; } op++; } while (op < length && width < start);
621 * } if (width < start) { // run off end - add more operations up to
622 * deletion. addInsertion(start - width); } else { // edit existing
623 * operations. op = prevop; width -= range[prevop]; int[] oldrange =
624 * range; char[] oldops = operation; range = new int[oldrange.length];
625 * operation = new char[oldops.length]; if (op < length) { do { if
626 * (operation[op] != D) { width += range[postop = op]; } op++; } while
627 * (op < length && width <= end); } } if (deleted == true) {
628 * addDeleted(end - start + 1); } return deleted; }
631 * Return an ENSEMBL style cigar string where D may indicates excluded parts
634 * @return String of form ([0-9]+[IMD])+
636 public String getCigarstring()
638 StringBuffer cigarString = new StringBuffer();
639 for (int i = 0; i < length; i++)
641 cigarString.append("" + range[i]);
642 cigarString.append(operation[i]);
644 return cigarString.toString();