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