src/jalview/analysis/AlignmentSorter.java

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