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) || cigars[c] instanceof CigarCigar))
  72         {
  73           seqcigararray = false;
  74         }
  75       }
  76     }
  77   }
  78
  79   /**
  80    * construct a cigar array from the current alignment, or just the subset of
  81    * the current alignment specified by selectionGroup. Any columns marked as
  82    * hidden in columnSelection will be marked as deleted in the array.
  83    *
  84    * @param alignment
  85    * @param columnSelection
  86    * @param selectionGroup
  87    */
  88   public CigarArray(AlignmentI alignment, ColumnSelection columnSelection,
  89           SequenceGroup selectionGroup)
  90   {
  91     this(constructSeqCigarArray(alignment, selectionGroup));
  92     constructFromAlignment(alignment,
  93             columnSelection != null ? columnSelection.getHiddenColumns()
  94                     : null, selectionGroup);
  95   }
  96
  97   private static int[] _calcStartEndBounds(AlignmentI alignment,
  98           SequenceGroup selectionGroup)
  99   {
 100     int[] startend = new int[]
 101     { 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         if (hideStart < last)
 174         {
 175           if (hideEnd > last)
 176           {
 177             hideStart = last;
 178           }
 179           else
 180           {
 181             continue;
 182           }
 183         }
 184
 185         if (hideStart > end)
 186         {
 187           break;
 188         }
 189
 190         if (hideEnd > end)
 191         {
 192           hideEnd = end;
 193         }
 194
 195         if (hideStart > hideEnd)
 196         {
 197           break;
 198         }
 199         /**
 200          * form operations...
 201          */
 202         if (last < hideStart)
 203         {
 204           addOperation(CigarArray.M, hideStart - last);
 205         }
 206         addOperation(CigarArray.D, 1 + hideEnd - hideStart);
 207         last = hideEnd + 1;
 208       }
 209       // Final match if necessary.
 210       if (last < end)
 211       {
 212         addOperation(CigarArray.M, end - last + 1);
 213       }
 214     }
 215     else
 216     {
 217       addOperation(CigarArray.M, end - start + 1);
 218     }
 219   }
 220
 221   /**
 222    * @see Cigar.getSequenceAndDeletions
 223    * @param GapChar
 224    *          char
 225    * @return Object[][]
 226    */
 227   protected Object[][] getArrayofSequenceAndDeletions(char GapChar)
 228   {
 229     if (refCigars == null || refCigars.length == 0 || length == 0)
 230     {
 231       return null;
 232     }
 233     Object[][] sqanddels = new Object[refCigars.length][];
 234     for (int c = 0; c < refCigars.length; c++)
 235     {
 236       String refString = refCigars[c].getSequenceString(GapChar);
 237       if (refString != null)
 238       {
 239         sqanddels[c] = getSequenceAndDeletions(refString, GapChar);
 240       }
 241       else
 242       {
 243         sqanddels[c] = null;
 244       }
 245     }
 246     return sqanddels;
 247   }
 248
 249   /**
 250    * NOTE: this is an improper sequence string function
 251    *
 252    * @return String formed by newline concatenated results of applying CIGAR
 253    *         operations to each reference object in turn.
 254    * @param GapChar
 255    *          char
 256    * @return '\n' separated strings (empty results included as \n\n)
 257    */
 258   public String getSequenceString(char GapChar)
 259   {
 260     if (length == 0 || refCigars == null)
 261     {
 262       return "";
 263     }
 264     StringBuffer seqStrings = new StringBuffer();
 265     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 266     for (int c = 0; c < refCigars.length; c++)
 267     {
 268       if (sqanddels[c] != null)
 269       {
 270         seqStrings.append((String) sqanddels[c][0]);
 271         sqanddels[c][0] = null;
 272       }
 273       seqStrings.append('\n');
 274     }
 275     return seqStrings.toString();
 276   }
 277
 278   /**
 279    * return string results of applying cigar string to all reference cigars
 280    *
 281    * @param GapChar
 282    *          char
 283    * @return String[]
 284    */
 285   public String[] getSequenceStrings(char GapChar)
 286   {
 287
 288     if (length == 0 || refCigars == null || refCigars.length == 0)
 289     {
 290       return null;
 291     }
 292     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 293     String[] seqs = new String[sqanddels.length];
 294     for (int c = 0; c < refCigars.length; c++)
 295     {
 296       seqs[c] = (String) sqanddels[c][0];
 297     }
 298     return seqs;
 299   }
 300
 301   /**
 302    * Combines the CigarArray cigar operations with the operations in each
 303    * reference cigar - creating a new reference cigar
 304    *
 305    * @return Cigar[]
 306    *
 307    *         public CigarBase[] getEditedCigars() {
 308    *
 309    *         return new CigarBase[] {}; }
 310    */
 311   /**
 312    * applyDeletions edits underlying refCigars to propagate deleted regions, and
 313    * removes deletion operations from CigarArray operation list.
 314    *
 315    * @return int[] position after deletion occured and range of deletion in
 316    *         cigarArray or null if none occured
 317    */
 318   public int[] applyDeletions()
 319   {
 320     java.util.Vector delpos = null;
 321     if (length == 0)
 322     {
 323       return null;
 324     }
 325     int cursor = 0; // range counter for deletions
 326     int vcursor = 0; // visible column index
 327     int offset = 0; // shift in visible column index as deletions are made
 328     int i = 0;
 329     while (i < length)
 330     {
 331       if (operation[i] != D)
 332       {
 333         if (operation[i] == M)
 334         {
 335           cursor += range[i];
 336         }
 337         vcursor += range[i++];
 338       }
 339       else
 340       {
 341         if (delpos == null)
 342         {
 343           delpos = new java.util.Vector();
 344         }
 345         int delstart = cursor, delend = cursor + range[i] - 1; // inclusive
 346         delpos.addElement(new int[]
 347         { vcursor + offset, range[i] }); // index of right hand column after
 348         // hidden region boundary
 349         offset += range[i] - 1; // shift in visible column coordinates
 350         System.arraycopy(operation, i + 1, operation, i, length - i);
 351         System.arraycopy(range, i + 1, range, i, length - i);
 352         length--;
 353         /*
 354          * int dmax=0; for (int s=0; s<refCigars.length; s++) { int d =
 355          * refCigars[s].deleteRange(delstart, delend); if (d>dmax) dmax=d; }
 356          * offset+=dmax; // shift in visible column coordinates
 357          */
 358         for (int s = 0; s < refCigars.length; s++)
 359         {
 360           int d = refCigars[s].deleteRange(delstart, delend);
 361         }
 362
 363       }
 364     }
 365     if (delpos != null)
 366     {
 367       int[] pos = new int[delpos.size() * 2];
 368       for (int k = 0, l = delpos.size(); k < l; k++)
 369       {
 370         int[] dr = ((int[]) delpos.elementAt(k));
 371         pos[k * 2] = dr[0];
 372         pos[k * 2 + 1] = dr[1];
 373         delpos.setElementAt(null, k);
 374       }
 375       delpos = null;
 376       return pos;
 377     }
 378     return null;
 379   }
 380
 381   /**
 382    *
 383    * @return SeqCigar[] or null if CigarArray is not a SeqCigarArray (ie it does
 384    *         not resolve to set of seqCigars)
 385    */
 386   public SeqCigar[] getSeqCigarArray()
 387   {
 388     if (!isSeqCigarArray())
 389     {
 390       return null;
 391     }
 392     SeqCigar[] sa = new SeqCigar[refCigars.length];
 393     for (int i = 0; i < refCigars.length; i++)
 394     {
 395       sa[i] = (SeqCigar) refCigars[i];
 396     }
 397     return sa;
 398   }
 399 }