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