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