src/jalview/datamodel/CigarArray.java

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