src/jalview/analysis/AlignmentSorter.java

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