src/jalview/analysis/AlignmentSorter.java

   1 /*\r
   2  * Jalview - A Sequence Alignment Editor and Viewer\r
   3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   4  *\r
   5  * This program is free software; you can redistribute it and/or\r
   6  * modify it under the terms of the GNU General Public License\r
   7  * as published by the Free Software Foundation; either version 2\r
   8  * of the License, or (at your option) any later version.\r
   9  *\r
  10  * This program is distributed in the hope that it will be useful,\r
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13  * GNU General Public License for more details.\r
  14  *\r
  15  * You should have received a copy of the GNU General Public License\r
  16  * along with this program; if not, write to the Free Software\r
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  18  */\r
  19 package jalview.analysis;\r
  20 \r
  21 import java.util.*;\r
  22 \r
  23 import jalview.datamodel.*;\r
  24 import jalview.util.*;\r
  25 \r
  26 /** Data structure to hold and manipulate a multiple sequence alignment\r
  27  */\r
  28 public class AlignmentSorter\r
  29 {\r
  30   static boolean sortIdAscending = true;\r
  31   static int lastGroupHash = 0;\r
  32   static boolean sortGroupAscending = true;\r
  33   static AlignmentOrder lastOrder = null;\r
  34   static boolean sortOrderAscending = true;\r
  35   static NJTree lastTree = null;\r
  36   static boolean sortTreeAscending = true;\r
  37 \r
  38   /**\r
  39    * Sort by Percentage Identity\r
  40    *\r
  41    * @param align AlignmentI\r
  42    * @param s SequenceI\r
  43    */\r
  44   public static void sortByPID(AlignmentI align, SequenceI s)\r
  45   {\r
  46     int nSeq = align.getHeight();\r
  47 \r
  48     float[] scores = new float[nSeq];\r
  49     SequenceI[] seqs = new SequenceI[nSeq];\r
  50 \r
  51     for (int i = 0; i < nSeq; i++)\r
  52     {\r
  53       scores[i] = Comparison.PID(align.getSequenceAt(i).getSequenceAsString(),\r
  54                                  s.getSequenceAsString());\r
  55       seqs[i] = align.getSequenceAt(i);\r
  56     }\r
  57 \r
  58     QuickSort.sort(scores, 0, scores.length - 1, seqs);\r
  59 \r
  60     setReverseOrder(align, seqs);\r
  61   }\r
  62 \r
  63   /**\r
  64    * Reverse the order of the sort\r
  65    *\r
  66    * @param align DOCUMENT ME!\r
  67    * @param seqs DOCUMENT ME!\r
  68    */\r
  69   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)\r
  70   {\r
  71     int nSeq = seqs.length;\r
  72 \r
  73     int len = 0;\r
  74 \r
  75     if ( (nSeq % 2) == 0)\r
  76     {\r
  77       len = nSeq / 2;\r
  78     }\r
  79     else\r
  80     {\r
  81       len = (nSeq + 1) / 2;\r
  82     }\r
  83 \r
  84     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
  85     for (int i = 0; i < len; i++)\r
  86     {\r
  87       //SequenceI tmp = seqs[i];\r
  88       align.getSequences().setElementAt(seqs[nSeq - i - 1], i);\r
  89       align.getSequences().setElementAt(seqs[i], nSeq - i - 1);\r
  90     }\r
  91   }\r
  92 \r
  93   /**\r
  94    * Sets the Alignment object with the given sequences\r
  95    *\r
  96    * @param align Alignment object to be updated\r
  97    * @param tmp sequences as a vector\r
  98    */\r
  99   private static void setOrder(AlignmentI align, Vector tmp)\r
 100   {\r
 101     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));\r
 102   }\r
 103 \r
 104   /**\r
 105    * Sets the Alignment object with the given sequences\r
 106    *\r
 107    * @param align DOCUMENT ME!\r
 108    * @param seqs sequences as an array\r
 109    */\r
 110   public static void setOrder(AlignmentI align, SequenceI[] seqs)\r
 111   {\r
 112     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
 113     Vector algn = align.getSequences();\r
 114     Vector tmp = new Vector();\r
 115 \r
 116     for (int i = 0; i < seqs.length; i++)\r
 117     {\r
 118       if (algn.contains(seqs[i]))\r
 119       {\r
 120         tmp.addElement(seqs[i]);\r
 121       }\r
 122     }\r
 123 \r
 124     algn.removeAllElements();\r
 125     //User may have hidden seqs, then clicked undo or redo\r
 126     for (int i = 0; i < tmp.size(); i++)\r
 127     {\r
 128       algn.addElement(tmp.elementAt(i));\r
 129     }\r
 130 \r
 131   }\r
 132 \r
 133   /**\r
 134    * Sorts by ID. Numbers are sorted before letters.\r
 135    *\r
 136    * @param align The alignment object to sort\r
 137    */\r
 138   public static void sortByID(AlignmentI align)\r
 139   {\r
 140     int nSeq = align.getHeight();\r
 141 \r
 142     String[] ids = new String[nSeq];\r
 143     SequenceI[] seqs = new SequenceI[nSeq];\r
 144 \r
 145     for (int i = 0; i < nSeq; i++)\r
 146     {\r
 147       ids[i] = align.getSequenceAt(i).getName();\r
 148       seqs[i] = align.getSequenceAt(i);\r
 149     }\r
 150 \r
 151     QuickSort.sort(ids, seqs);\r
 152 \r
 153     if (sortIdAscending)\r
 154     {\r
 155       setReverseOrder(align, seqs);\r
 156     }\r
 157     else\r
 158     {\r
 159       setOrder(align, seqs);\r
 160     }\r
 161 \r
 162     sortIdAscending = !sortIdAscending;\r
 163   }\r
 164 \r
 165   /**\r
 166    * Sorts the alignment by size of group.\r
 167    * <br>Maintains the order of sequences in each group\r
 168    * by order in given alignment object.\r
 169    *\r
 170    * @param align sorts the given alignment object by group\r
 171    */\r
 172   public static void sortByGroup(AlignmentI align)\r
 173   {\r
 174     //MAINTAINS ORIGNAL SEQUENCE ORDER,\r
 175     //ORDERS BY GROUP SIZE\r
 176     Vector groups = new Vector();\r
 177 \r
 178     if (groups.hashCode() != lastGroupHash)\r
 179     {\r
 180       sortGroupAscending = true;\r
 181       lastGroupHash = groups.hashCode();\r
 182     }\r
 183     else\r
 184     {\r
 185       sortGroupAscending = !sortGroupAscending;\r
 186     }\r
 187 \r
 188     //SORTS GROUPS BY SIZE\r
 189     //////////////////////\r
 190     for (int i = 0; i < align.getGroups().size(); i++)\r
 191     {\r
 192       SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);\r
 193 \r
 194       for (int j = 0; j < groups.size(); j++)\r
 195       {\r
 196         SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);\r
 197 \r
 198         if (sg.getSize() > sg2.getSize())\r
 199         {\r
 200           groups.insertElementAt(sg, j);\r
 201 \r
 202           break;\r
 203         }\r
 204       }\r
 205 \r
 206       if (!groups.contains(sg))\r
 207       {\r
 208         groups.addElement(sg);\r
 209       }\r
 210     }\r
 211 \r
 212     //NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER\r
 213     ///////////////////////////////////////////////\r
 214     Vector seqs = new Vector();\r
 215 \r
 216     for (int i = 0; i < groups.size(); i++)\r
 217     {\r
 218       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
 219       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);\r
 220 \r
 221       for (int j = 0; j < orderedseqs.length; j++)\r
 222       {\r
 223         seqs.addElement(orderedseqs[j]);\r
 224       }\r
 225     }\r
 226 \r
 227     if (sortGroupAscending)\r
 228     {\r
 229       setOrder(align, seqs);\r
 230     }\r
 231     else\r
 232     {\r
 233       setReverseOrder(align,\r
 234                       vectorSubsetToArray(seqs, align.getSequences()));\r
 235     }\r
 236   }\r
 237 \r
 238   /**\r
 239    * Converts Vector to array.\r
 240    * java 1.18 does not have Vector.toArray()\r
 241    *\r
 242    * @param tmp Vector of SequenceI objects\r
 243    *\r
 244    * @return array of Sequence[]\r
 245    */\r
 246   private static SequenceI[] vectorToArray(Vector tmp)\r
 247   {\r
 248     SequenceI[] seqs = new SequenceI[tmp.size()];\r
 249 \r
 250     for (int i = 0; i < tmp.size(); i++)\r
 251     {\r
 252       seqs[i] = (SequenceI) tmp.elementAt(i);\r
 253     }\r
 254 \r
 255     return seqs;\r
 256   }\r
 257 \r
 258   /**\r
 259    * DOCUMENT ME!\r
 260    *\r
 261    * @param tmp DOCUMENT ME!\r
 262    * @param mask DOCUMENT ME!\r
 263    *\r
 264    * @return DOCUMENT ME!\r
 265    */\r
 266   private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)\r
 267   {\r
 268     Vector seqs = new Vector();\r
 269     int i;\r
 270     boolean[] tmask = new boolean[mask.size()];\r
 271 \r
 272     for (i = 0; i < mask.size(); i++)\r
 273     {\r
 274       tmask[i] = true;\r
 275     }\r
 276 \r
 277     for (i = 0; i < tmp.size(); i++)\r
 278     {\r
 279       Object sq = tmp.elementAt(i);\r
 280 \r
 281       if (mask.contains(sq) && tmask[mask.indexOf(sq)])\r
 282       {\r
 283         tmask[mask.indexOf(sq)] = false;\r
 284         seqs.addElement(sq);\r
 285       }\r
 286     }\r
 287 \r
 288     for (i = 0; i < tmask.length; i++)\r
 289     {\r
 290       if (tmask[i])\r
 291       {\r
 292         seqs.addElement(mask.elementAt(i));\r
 293       }\r
 294     }\r
 295 \r
 296     return vectorToArray(seqs);\r
 297   }\r
 298 \r
 299   /**\r
 300    * Sorts by a given AlignmentOrder object\r
 301    *\r
 302    * @param align Alignment to order\r
 303    * @param order specified order for alignment\r
 304    */\r
 305   public static void sortBy(AlignmentI align, AlignmentOrder order)\r
 306   {\r
 307     // Get an ordered vector of sequences which may also be present in align\r
 308     Vector tmp = order.getOrder();\r
 309 \r
 310     if (lastOrder == order)\r
 311     {\r
 312       sortOrderAscending = !sortOrderAscending;\r
 313     }\r
 314     else\r
 315     {\r
 316       sortOrderAscending = true;\r
 317     }\r
 318 \r
 319     if (sortOrderAscending)\r
 320     {\r
 321       setOrder(align, tmp);\r
 322     }\r
 323     else\r
 324     {\r
 325       setReverseOrder(align,\r
 326                       vectorSubsetToArray(tmp, align.getSequences()));\r
 327     }\r
 328   }\r
 329 \r
 330   /**\r
 331    * DOCUMENT ME!\r
 332    *\r
 333    * @param align alignment to order\r
 334    * @param tree tree which has\r
 335    *\r
 336    * @return DOCUMENT ME!\r
 337    */\r
 338   private static Vector getOrderByTree(AlignmentI align, NJTree tree)\r
 339   {\r
 340     int nSeq = align.getHeight();\r
 341 \r
 342     Vector tmp = new Vector();\r
 343 \r
 344     tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());\r
 345 \r
 346     if (tmp.size() != nSeq)\r
 347     {\r
 348       // TODO: JBPNote - decide if this is always an error\r
 349       // (eg. not when a tree is associated to another alignment which has more\r
 350       //  sequences)\r
 351       if (tmp.size() < nSeq)\r
 352       {\r
 353         addStrays(align, tmp);\r
 354       }\r
 355 \r
 356       if (tmp.size() != nSeq)\r
 357       {\r
 358         System.err.println("ERROR: tmp.size()=" + tmp.size() +\r
 359                            " != nseq=" + nSeq + " in getOrderByTree");\r
 360       }\r
 361     }\r
 362 \r
 363     return tmp;\r
 364   }\r
 365 \r
 366   /**\r
 367    * Sorts the alignment by a given tree\r
 368    *\r
 369    * @param align alignment to order\r
 370    * @param tree tree which has\r
 371    */\r
 372   public static void sortByTree(AlignmentI align, NJTree tree)\r
 373   {\r
 374     Vector tmp = getOrderByTree(align, tree);\r
 375 \r
 376     // tmp should properly permute align with tree.\r
 377     if (lastTree != tree)\r
 378     {\r
 379       sortTreeAscending = true;\r
 380       lastTree = tree;\r
 381     }\r
 382     else\r
 383     {\r
 384       sortTreeAscending = !sortTreeAscending;\r
 385     }\r
 386 \r
 387     if (sortTreeAscending)\r
 388     {\r
 389       setOrder(align, tmp);\r
 390     }\r
 391     else\r
 392     {\r
 393       setReverseOrder(align,\r
 394                       vectorSubsetToArray(tmp, align.getSequences()));\r
 395     }\r
 396   }\r
 397 \r
 398   /**\r
 399    * DOCUMENT ME!\r
 400    *\r
 401    * @param align DOCUMENT ME!\r
 402    * @param seqs DOCUMENT ME!\r
 403    */\r
 404   private static void addStrays(AlignmentI align, Vector seqs)\r
 405   {\r
 406     int nSeq = align.getHeight();\r
 407 \r
 408     for (int i = 0; i < nSeq; i++)\r
 409     {\r
 410       if (!seqs.contains(align.getSequenceAt(i)))\r
 411       {\r
 412         seqs.addElement(align.getSequenceAt(i));\r
 413       }\r
 414     }\r
 415 \r
 416     if (nSeq != seqs.size())\r
 417     {\r
 418       System.err.println(\r
 419           "ERROR: Size still not right even after addStrays");\r
 420     }\r
 421   }\r
 422 \r
 423   /**\r
 424    * DOCUMENT ME!\r
 425    *\r
 426    * @param node DOCUMENT ME!\r
 427    * @param tmp DOCUMENT ME!\r
 428    * @param seqset DOCUMENT ME!\r
 429    *\r
 430    * @return DOCUMENT ME!\r
 431    */\r
 432   private static Vector _sortByTree(SequenceNode node, Vector tmp,\r
 433                                     Vector seqset)\r
 434   {\r
 435     if (node == null)\r
 436     {\r
 437       return tmp;\r
 438     }\r
 439 \r
 440     SequenceNode left = (SequenceNode) node.left();\r
 441     SequenceNode right = (SequenceNode) node.right();\r
 442 \r
 443     if ( (left == null) && (right == null))\r
 444     {\r
 445       if (!node.isPlaceholder() && (node.element() != null))\r
 446       {\r
 447         if (node.element() instanceof SequenceI)\r
 448         {\r
 449           if (!tmp.contains(node.element()))\r
 450           {\r
 451             tmp.addElement( (SequenceI) node.element());\r
 452           }\r
 453         }\r
 454       }\r
 455 \r
 456       return tmp;\r
 457     }\r
 458     else\r
 459     {\r
 460       _sortByTree(left, tmp, seqset);\r
 461       _sortByTree(right, tmp, seqset);\r
 462     }\r
 463 \r
 464     return tmp;\r
 465   }\r
 466 \r
 467   // Ordering Objects\r
 468   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order\r
 469   //\r
 470 \r
 471   /**\r
 472    * recover the order of sequences given by the safe numbering scheme introducd\r
 473    * SeqsetUtils.uniquify.\r
 474    */\r
 475   public static void recoverOrder(SequenceI[] alignment)\r
 476   {\r
 477     float[] ids = new float[alignment.length];\r
 478 \r
 479     for (int i = 0; i < alignment.length; i++)\r
 480     {\r
 481       ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();\r
 482     }\r
 483 \r
 484     jalview.util.QuickSort.sort(ids, alignment);\r
 485   }\r
 486 }\r