src/jalview/datamodel/CigarArray.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 java.util.List;
  24
  25 public class CigarArray extends CigarBase
  26 {
  27   /**
  28    * Do CIGAR operations on a set of sequences from many other cigars BAD THINGS
  29    * WILL HAPPEN IF A CIGARARRAY IS PASSED TO A CIGARARRAY or a CIGARCIGAR is
  30    * given a CIGARARRAY to insert gaps into.
  31    */
  32   /**
  33    * array of subject cigars
  34    */
  35   public CigarSimple refCigars[] = null;
  36
  37   private boolean seqcigararray = false;
  38
  39   private CigarArray()
  40   {
  41     super();
  42   }
  43
  44   /**
  45    * isSeqCigarArray()
  46    *
  47    * @return boolean true if all refCigars resolve to a SeqCigar or a CigarCigar
  48    */
  49   public boolean isSeqCigarArray()
  50   {
  51     return seqcigararray;
  52   }
  53
  54   /**
  55    * Apply CIGAR operations to several cigars in parallel will throw an error if
  56    * any of cigar are actually CigarArrays.
  57    *
  58    * @param cigar
  59    *          Cigar[]
  60    */
  61   public CigarArray(CigarSimple[] cigars)
  62   {
  63     super();
  64     seqcigararray = true;
  65     if (cigars != null && cigars.length > 0)
  66     {
  67       refCigars = new CigarSimple[cigars.length];
  68       for (int c = 0; c < cigars.length; c++)
  69       {
  70         refCigars[c] = cigars[c];
  71         if (!((cigars[c] instanceof SeqCigar)
  72                 || cigars[c] instanceof CigarCigar))
  73         {
  74           seqcigararray = false;
  75         }
  76       }
  77     }
  78   }
  79
  80   /**
  81    * construct a cigar array from the current alignment, or just the subset of
  82    * the current alignment specified by selectionGroup. Any columns marked as
  83    * hidden in columnSelection will be marked as deleted in the array.
  84    *
  85    * @param alignment
  86    * @param columnSelection
  87    * @param selectionGroup
  88    */
  89   public CigarArray(AlignmentI alignment, HiddenColumns hidden,
  90           SequenceGroup selectionGroup)
  91   {
  92     this(constructSeqCigarArray(alignment, selectionGroup));
  93     constructFromAlignment(alignment,
  94             hidden != null ? hidden.getHiddenColumnsCopy() : null,
  95             selectionGroup);
  96   }
  97
  98   private static int[] _calcStartEndBounds(AlignmentI alignment,
  99           SequenceGroup selectionGroup)
 100   {
 101     int[] startend = new int[] { 0, 0, 0 };
 102     if (selectionGroup != null)
 103     {
 104       startend[0] = selectionGroup.getSize();
 105       startend[1] = selectionGroup.getStartRes();
 106       startend[2] = selectionGroup.getEndRes(); // inclusive for start and end
 107                                                 // in
 108       // SeqCigar constructor
 109     }
 110     else
 111     {
 112       startend[0] = alignment.getHeight();
 113       startend[2] = alignment.getWidth() - 1;
 114     }
 115     return startend;
 116   }
 117
 118   public static SeqCigar[] constructSeqCigarArray(AlignmentI alignment,
 119           SequenceGroup selectionGroup)
 120   {
 121     SequenceI[] seqs = null;
 122     int i, iSize;
 123     int _startend[] = _calcStartEndBounds(alignment, selectionGroup);
 124     int start = _startend[1], end = _startend[2];
 125     if (selectionGroup != null)
 126     {
 127       iSize = selectionGroup.getSize();
 128       seqs = selectionGroup.getSequencesInOrder(alignment);
 129       start = selectionGroup.getStartRes();
 130       end = selectionGroup.getEndRes(); // inclusive for start and end in
 131       // SeqCigar constructor
 132     }
 133     else
 134     {
 135       iSize = alignment.getHeight();
 136       seqs = alignment.getSequencesArray();
 137       end = alignment.getWidth() - 1;
 138     }
 139     SeqCigar[] selseqs = new SeqCigar[iSize];
 140     for (i = 0; i < iSize; i++)
 141     {
 142       selseqs[i] = new SeqCigar(seqs[i], start, end);
 143     }
 144     return selseqs;
 145   }
 146
 147   /**
 148    * internal constructor function - called by CigarArray(AlignmentI, ...);
 149    *
 150    * @param alignment
 151    * @param list
 152    *          - vector of visible regions as returned from
 153    *          columnSelection.getHiddenColumns()
 154    * @param selectionGroup
 155    */
 156   private void constructFromAlignment(AlignmentI alignment,
 157           List<int[]> list, SequenceGroup selectionGroup)
 158   {
 159     int[] _startend = _calcStartEndBounds(alignment, selectionGroup);
 160     int start = _startend[1], end = _startend[2];
 161     // now construct the CigarArray operations
 162     if (list != null)
 163     {
 164       int[] region;
 165       int hideStart, hideEnd;
 166       int last = start;
 167       for (int j = 0; last < end & j < list.size(); j++)
 168       {
 169         region = list.get(j);
 170         hideStart = region[0];
 171         hideEnd = region[1];
 172         // edit hidden regions to selection range
 173
 174         // just move on if hideEnd is before last
 175         if (hideEnd < last)
 176         {
 177           continue;
 178         }
 179         // exit if next region is after end
 180         if (hideStart > end)
 181         {
 182           break;
 183         }
 184
 185         // truncate region at start if last falls in region
 186         if ((hideStart < last) && (hideEnd >= last))
 187         {
 188           hideStart = last;
 189         }
 190
 191         // truncate region at end if end falls in region
 192         if (hideEnd > end) // already checked that hideStart<=end
 193         {
 194           hideEnd = end;
 195         }
 196
 197         /**
 198          * form operations...
 199          */
 200         if (last < hideStart)
 201         {
 202           addOperation(CigarArray.M, hideStart - last);
 203         }
 204         addOperation(CigarArray.D, 1 + hideEnd - hideStart);
 205         last = hideEnd + 1;
 206       }
 207       // Final match if necessary.
 208       if (last <= end)
 209       {
 210         addOperation(CigarArray.M, end - last + 1);
 211       }
 212     }
 213     else
 214     {
 215       addOperation(CigarArray.M, end - start + 1);
 216     }
 217   }
 218
 219   /**
 220    * @see CigarBase.getSequenceAndDeletions
 221    * @param GapChar
 222    *          char
 223    * @return Object[][]
 224    */
 225   protected Object[][] getArrayofSequenceAndDeletions(char GapChar)
 226   {
 227     if (refCigars == null || refCigars.length == 0 || length == 0)
 228     {
 229       return null;
 230     }
 231     Object[][] sqanddels = new Object[refCigars.length][];
 232     for (int c = 0; c < refCigars.length; c++)
 233     {
 234       String refString = refCigars[c].getSequenceString(GapChar);
 235       if (refString != null)
 236       {
 237         sqanddels[c] = getSequenceAndDeletions(refString, GapChar);
 238       }
 239       else
 240       {
 241         sqanddels[c] = null;
 242       }
 243     }
 244     return sqanddels;
 245   }
 246
 247   /**
 248    * NOTE: this is an improper sequence string function
 249    *
 250    * @return String formed by newline concatenated results of applying CIGAR
 251    *         operations to each reference object in turn.
 252    * @param GapChar
 253    *          char
 254    * @return '\n' separated strings (empty results included as \n\n)
 255    */
 256   public String getSequenceString(char GapChar)
 257   {
 258     if (length == 0 || refCigars == null)
 259     {
 260       return "";
 261     }
 262     StringBuffer seqStrings = new StringBuffer();
 263     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 264     for (int c = 0; c < refCigars.length; c++)
 265     {
 266       if (sqanddels[c] != null)
 267       {
 268         seqStrings.append((String) sqanddels[c][0]);
 269         sqanddels[c][0] = null;
 270       }
 271       seqStrings.append('\n');
 272     }
 273     return seqStrings.toString();
 274   }
 275
 276   /**
 277    * return string results of applying cigar string to all reference cigars
 278    *
 279    * @param GapChar
 280    *          char
 281    * @return String[]
 282    */
 283   public String[] getSequenceStrings(char GapChar)
 284   {
 285
 286     if (length == 0 || refCigars == null || refCigars.length == 0)
 287     {
 288       return null;
 289     }
 290     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 291     String[] seqs = new String[sqanddels.length];
 292     for (int c = 0; c < refCigars.length; c++)
 293     {
 294       seqs[c] = (String) sqanddels[c][0];
 295     }
 296     return seqs;
 297   }
 298
 299   /**
 300    * Combines the CigarArray cigar operations with the operations in each
 301    * reference cigar - creating a new reference cigar
 302    *
 303    * @return Cigar[]
 304    *
 305    *         public CigarBase[] getEditedCigars() {
 306    *
 307    *         return new CigarBase[] {}; }
 308    */
 309   /**
 310    * applyDeletions edits underlying refCigars to propagate deleted regions, and
 311    * removes deletion operations from CigarArray operation list.
 312    *
 313    * @return int[] position after deletion occured and range of deletion in
 314    *         cigarArray or null if none occured
 315    */
 316   public int[] applyDeletions()
 317   {
 318     java.util.Vector delpos = null;
 319     if (length == 0)
 320     {
 321       return null;
 322     }
 323     int cursor = 0; // range counter for deletions
 324     int vcursor = 0; // visible column index
 325     int offset = 0; // shift in visible column index as deletions are made
 326     int i = 0;
 327     while (i < length)
 328     {
 329       if (operation[i] != D)
 330       {
 331         if (operation[i] == M)
 332         {
 333           cursor += range[i];
 334         }
 335         vcursor += range[i++];
 336       }
 337       else
 338       {
 339         if (delpos == null)
 340         {
 341           delpos = new java.util.Vector();
 342         }
 343         int delstart = cursor, delend = cursor + range[i] - 1; // inclusive
 344         delpos.addElement(new int[] { vcursor + offset, range[i] }); // index of
 345                                                                      // right
 346                                                                      // hand
 347                                                                      // column
 348                                                                      // after
 349         // hidden region boundary
 350         offset += range[i] - 1; // shift in visible column coordinates
 351         System.arraycopy(operation, i + 1, operation, i, length - i);
 352         System.arraycopy(range, i + 1, range, i, length - i);
 353         length--;
 354         /*
 355          * int dmax=0; for (int s=0; s<refCigars.length; s++) { int d =
 356          * refCigars[s].deleteRange(delstart, delend); if (d>dmax) dmax=d; }
 357          * offset+=dmax; // shift in visible column coordinates
 358          */
 359         for (int s = 0; s < refCigars.length; s++)
 360         {
 361           int d = refCigars[s].deleteRange(delstart, delend);
 362         }
 363
 364       }
 365     }
 366     if (delpos != null)
 367     {
 368       int[] pos = new int[delpos.size() * 2];
 369       for (int k = 0, l = delpos.size(); k < l; k++)
 370       {
 371         int[] dr = ((int[]) delpos.elementAt(k));
 372         pos[k * 2] = dr[0];
 373         pos[k * 2 + 1] = dr[1];
 374         delpos.setElementAt(null, k);
 375       }
 376       delpos = null;
 377       return pos;
 378     }
 379     return null;
 380   }
 381
 382   /**
 383    *
 384    * @return SeqCigar[] or null if CigarArray is not a SeqCigarArray (ie it does
 385    *         not resolve to set of seqCigars)
 386    */
 387   public SeqCigar[] getSeqCigarArray()
 388   {
 389     if (!isSeqCigarArray())
 390     {
 391       return null;
 392     }
 393     SeqCigar[] sa = new SeqCigar[refCigars.length];
 394     for (int i = 0; i < refCigars.length; i++)
 395     {
 396       sa[i] = (SeqCigar) refCigars[i];
 397     }
 398     return sa;
 399   }
 400 }