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.Iterator;
  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, hidden, selectionGroup);
  94   }
  95
  96   private static int[] _calcStartEndBounds(AlignmentI alignment,
  97           SequenceGroup selectionGroup)
  98   {
  99     int[] startend = new int[] { 0, 0, 0 };
 100     if (selectionGroup != null)
 101     {
 102       startend[0] = selectionGroup.getSize();
 103       startend[1] = selectionGroup.getStartRes();
 104       startend[2] = selectionGroup.getEndRes(); // inclusive for start and end
 105                                                 // in
 106       // SeqCigar constructor
 107     }
 108     else
 109     {
 110       startend[0] = alignment.getHeight();
 111       startend[2] = alignment.getWidth() - 1;
 112     }
 113     return startend;
 114   }
 115
 116   public static SeqCigar[] constructSeqCigarArray(AlignmentI alignment,
 117           SequenceGroup selectionGroup)
 118   {
 119     SequenceI[] seqs = null;
 120     int i, iSize;
 121     int _startend[] = _calcStartEndBounds(alignment, selectionGroup);
 122     int start = _startend[1], end = _startend[2];
 123     if (selectionGroup != null)
 124     {
 125       iSize = selectionGroup.getSize();
 126       seqs = selectionGroup.getSequencesInOrder(alignment);
 127       start = selectionGroup.getStartRes();
 128       end = selectionGroup.getEndRes(); // inclusive for start and end in
 129       // SeqCigar constructor
 130     }
 131     else
 132     {
 133       iSize = alignment.getHeight();
 134       seqs = alignment.getSequencesArray();
 135       end = alignment.getWidth() - 1;
 136     }
 137     SeqCigar[] selseqs = new SeqCigar[iSize];
 138     for (i = 0; i < iSize; i++)
 139     {
 140       selseqs[i] = new SeqCigar(seqs[i], start, end);
 141     }
 142     return selseqs;
 143   }
 144
 145   /**
 146    * internal constructor function - called by CigarArray(AlignmentI, ...);
 147    *
 148    * @param alignment
 149    * @param list
 150    *          - vector of visible regions as returned from
 151    *          columnSelection.getHiddenColumns()
 152    * @param selectionGroup
 153    */
 154   private void constructFromAlignment(AlignmentI alignment,
 155           HiddenColumns hidden, SequenceGroup selectionGroup)
 156   {
 157     int[] _startend = _calcStartEndBounds(alignment, selectionGroup);
 158     int start = _startend[1];
 159     int end = _startend[2];
 160     // now construct the CigarArray operations
 161     if (hidden != null)
 162     {
 163       int[] region;
 164       int hideStart;
 165       int hideEnd;
 166       int last = start;
 167
 168       Iterator<int[]> regions = hidden.getBoundedIterator(start, end, true);
 169       while (regions.hasNext())
 170       {
 171         region = regions.next();
 172         hideStart = region[0];
 173         hideEnd = region[1];
 174
 175         // edit hidden regions to selection range
 176         // TODO possible bug here in original code: if hideEnd==last we continue
 177         // but shouldn't this be a single D at start?
 178         if (hideStart < last)
 179         {
 180           if (hideEnd > last)
 181           {
 182             hideStart = last;
 183           }
 184           else
 185           {
 186             continue;
 187           }
 188         }
 189
 190         if (hideStart > end)
 191         {
 192           break;
 193         }
 194
 195         if (hideEnd > end)
 196         {
 197           hideEnd = end;
 198         }
 199
 200         if (hideStart > hideEnd)
 201         {
 202           break;
 203         }
 204         /**
 205          * form operations...
 206          */
 207         if (last < hideStart)
 208         {
 209           addOperation(CigarArray.M, hideStart - last);
 210         }
 211         addOperation(CigarArray.D, 1 + hideEnd - hideStart);
 212         last = hideEnd + 1;
 213       }
 214
 215       // Final match if necessary.
 216       if (last < end)
 217       {
 218         addOperation(CigarArray.M, end - last + 1);
 219       }
 220     }
 221     else
 222     {
 223       addOperation(CigarArray.M, end - start + 1);
 224     }
 225   }
 226
 227   /**
 228    * @see CigarBase.getSequenceAndDeletions
 229    * @param GapChar
 230    *          char
 231    * @return Object[][]
 232    */
 233   protected Object[][] getArrayofSequenceAndDeletions(char GapChar)
 234   {
 235     if (refCigars == null || refCigars.length == 0 || length == 0)
 236     {
 237       return null;
 238     }
 239     Object[][] sqanddels = new Object[refCigars.length][];
 240     for (int c = 0; c < refCigars.length; c++)
 241     {
 242       String refString = refCigars[c].getSequenceString(GapChar);
 243       if (refString != null)
 244       {
 245         sqanddels[c] = getSequenceAndDeletions(refString, GapChar);
 246       }
 247       else
 248       {
 249         sqanddels[c] = null;
 250       }
 251     }
 252     return sqanddels;
 253   }
 254
 255   /**
 256    * NOTE: this is an improper sequence string function
 257    *
 258    * @return String formed by newline concatenated results of applying CIGAR
 259    *         operations to each reference object in turn.
 260    * @param GapChar
 261    *          char
 262    * @return '\n' separated strings (empty results included as \n\n)
 263    */
 264   public String getSequenceString(char GapChar)
 265   {
 266     if (length == 0 || refCigars == null)
 267     {
 268       return "";
 269     }
 270     StringBuffer seqStrings = new StringBuffer();
 271     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 272     for (int c = 0; c < refCigars.length; c++)
 273     {
 274       if (sqanddels[c] != null)
 275       {
 276         seqStrings.append((String) sqanddels[c][0]);
 277         sqanddels[c][0] = null;
 278       }
 279       seqStrings.append('\n');
 280     }
 281     return seqStrings.toString();
 282   }
 283
 284   /**
 285    * return string results of applying cigar string to all reference cigars
 286    *
 287    * @param GapChar
 288    *          char
 289    * @return String[]
 290    */
 291   public String[] getSequenceStrings(char GapChar)
 292   {
 293
 294     if (length == 0 || refCigars == null || refCigars.length == 0)
 295     {
 296       return null;
 297     }
 298     Object[][] sqanddels = getArrayofSequenceAndDeletions(GapChar);
 299     String[] seqs = new String[sqanddels.length];
 300     for (int c = 0; c < refCigars.length; c++)
 301     {
 302       seqs[c] = (String) sqanddels[c][0];
 303     }
 304     return seqs;
 305   }
 306
 307   /**
 308    * Combines the CigarArray cigar operations with the operations in each
 309    * reference cigar - creating a new reference cigar
 310    *
 311    * @return Cigar[]
 312    *
 313    *         public CigarBase[] getEditedCigars() {
 314    *
 315    *         return new CigarBase[] {}; }
 316    */
 317   /**
 318    * applyDeletions edits underlying refCigars to propagate deleted regions, and
 319    * removes deletion operations from CigarArray operation list.
 320    *
 321    * @return int[] position after deletion occured and range of deletion in
 322    *         cigarArray or null if none occured
 323    */
 324   public int[] applyDeletions()
 325   {
 326     java.util.Vector delpos = null;
 327     if (length == 0)
 328     {
 329       return null;
 330     }
 331     int cursor = 0; // range counter for deletions
 332     int vcursor = 0; // visible column index
 333     int offset = 0; // shift in visible column index as deletions are made
 334     int i = 0;
 335     while (i < length)
 336     {
 337       if (operation[i] != D)
 338       {
 339         if (operation[i] == M)
 340         {
 341           cursor += range[i];
 342         }
 343         vcursor += range[i++];
 344       }
 345       else
 346       {
 347         if (delpos == null)
 348         {
 349           delpos = new java.util.Vector();
 350         }
 351         int delstart = cursor, delend = cursor + range[i] - 1; // inclusive
 352         delpos.addElement(new int[] { vcursor + offset, range[i] }); // index of
 353                                                                      // right
 354                                                                      // hand
 355                                                                      // column
 356                                                                      // after
 357         // hidden region boundary
 358         offset += range[i] - 1; // shift in visible column coordinates
 359         System.arraycopy(operation, i + 1, operation, i, length - i);
 360         System.arraycopy(range, i + 1, range, i, length - i);
 361         length--;
 362         /*
 363          * int dmax=0; for (int s=0; s<refCigars.length; s++) { int d =
 364          * refCigars[s].deleteRange(delstart, delend); if (d>dmax) dmax=d; }
 365          * offset+=dmax; // shift in visible column coordinates
 366          */
 367         for (int s = 0; s < refCigars.length; s++)
 368         {
 369           int d = refCigars[s].deleteRange(delstart, delend);
 370         }
 371
 372       }
 373     }
 374     if (delpos != null)
 375     {
 376       int[] pos = new int[delpos.size() * 2];
 377       for (int k = 0, l = delpos.size(); k < l; k++)
 378       {
 379         int[] dr = ((int[]) delpos.elementAt(k));
 380         pos[k * 2] = dr[0];
 381         pos[k * 2 + 1] = dr[1];
 382         delpos.setElementAt(null, k);
 383       }
 384       delpos = null;
 385       return pos;
 386     }
 387     return null;
 388   }
 389
 390   /**
 391    *
 392    * @return SeqCigar[] or null if CigarArray is not a SeqCigarArray (ie it does
 393    *         not resolve to set of seqCigars)
 394    */
 395   public SeqCigar[] getSeqCigarArray()
 396   {
 397     if (!isSeqCigarArray())
 398     {
 399       return null;
 400     }
 401     SeqCigar[] sa = new SeqCigar[refCigars.length];
 402     for (int i = 0; i < refCigars.length; i++)
 403     {
 404       sa[i] = (SeqCigar) refCigars[i];
 405     }
 406     return sa;
 407   }
 408 }