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