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.io.*;\r
  24 \r
  25 import jalview.util.*;\r
  26 \r
  27 import java.util.*;\r
  28 \r
  29 \r
  30 /** Data structure to hold and manipulate a multiple sequence alignment\r
  31  */\r
  32 public class AlignmentSorter {\r
  33     /**    */\r
  34     static boolean sortIdAscending = true;\r
  35     static int lastGroupHash = 0;\r
  36     static boolean sortGroupAscending = true;\r
  37     static AlignmentOrder lastOrder = null;\r
  38     static boolean sortOrderAscending = true;\r
  39     static NJTree lastTree = null;\r
  40     static boolean sortTreeAscending = true;\r
  41 \r
  42     /**\r
  43      * Sort by Percentage Identity\r
  44      *\r
  45      * @param align AlignmentI\r
  46      * @param s SequenceI\r
  47      */\r
  48     public static void sortByPID(AlignmentI align, SequenceI s) {\r
  49         int nSeq = align.getHeight();\r
  50 \r
  51         float[] scores = new float[nSeq];\r
  52         SequenceI[] seqs = new SequenceI[nSeq];\r
  53 \r
  54         for (int i = 0; i < nSeq; i++) {\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     private static void setReverseOrder(AlignmentI align, SequenceI[] seqs) {\r
  65         int nSeq = seqs.length;\r
  66 \r
  67         int len = 0;\r
  68 \r
  69         if ((nSeq % 2) == 0) {\r
  70             len = nSeq / 2;\r
  71         } else {\r
  72             len = (nSeq + 1) / 2;\r
  73         }\r
  74 \r
  75         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
  76         for (int i = 0; i < len; i++) {\r
  77             //SequenceI tmp = seqs[i];\r
  78             align.getSequences().setElementAt(seqs[nSeq - i - 1], i);\r
  79             align.getSequences().setElementAt(seqs[i], nSeq - i - 1);\r
  80         }\r
  81     }\r
  82 \r
  83     private static void setOrder(AlignmentI align, Vector tmp) {\r
  84         setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));\r
  85     }\r
  86 \r
  87     private static void setOrder(AlignmentI align, SequenceI[] seqs) {\r
  88 \r
  89         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
  90         Vector algn = align.getSequences();\r
  91         for (int i = 0; i < seqs.length; i++)\r
  92         {\r
  93           algn.setElementAt(seqs[i], i);\r
  94         }\r
  95     }\r
  96 \r
  97     public static void sortByID(AlignmentI align) {\r
  98         int nSeq = align.getHeight();\r
  99 \r
 100         String[] ids = new String[nSeq];\r
 101         SequenceI[] seqs = new SequenceI[nSeq];\r
 102 \r
 103         for (int i = 0; i < nSeq; i++) {\r
 104             ids[i] = align.getSequenceAt(i).getName();\r
 105             seqs[i] = align.getSequenceAt(i);\r
 106         }\r
 107 \r
 108         QuickSort.sort(ids, seqs);\r
 109 \r
 110         if (sortIdAscending) {\r
 111             setReverseOrder(align, seqs);\r
 112         } else {\r
 113             setOrder(align, seqs);\r
 114         }\r
 115 \r
 116         sortIdAscending = !sortIdAscending;\r
 117     }\r
 118 \r
 119     public static void sortByGroup(AlignmentI align) {\r
 120       //MAINTAINS ORIGNAL SEQUENCE ORDER,\r
 121       //ORDERS BY GROUP SIZE\r
 122 \r
 123         Vector groups = new Vector();\r
 124 \r
 125         if (groups.hashCode() != lastGroupHash) {\r
 126             sortGroupAscending = true;\r
 127             lastGroupHash = groups.hashCode();\r
 128         } else {\r
 129             sortGroupAscending = !sortGroupAscending;\r
 130         }\r
 131 \r
 132         //SORTS GROUPS BY SIZE\r
 133         //////////////////////\r
 134         for(int i=0; i<align.getGroups().size(); i++)\r
 135         {\r
 136            SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);\r
 137 \r
 138            for(int j=0; j<groups.size(); j++)\r
 139            {\r
 140              SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);\r
 141              if(sg.getSize() > sg2.getSize())\r
 142              {\r
 143                groups.insertElementAt(sg, j);\r
 144                break;\r
 145              }\r
 146            }\r
 147 \r
 148            if (!groups.contains(sg))\r
 149            {\r
 150              groups.addElement(sg);\r
 151            }\r
 152         }\r
 153 \r
 154         //NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER\r
 155         ///////////////////////////////////////////////\r
 156         Vector seqs = new Vector();\r
 157         for (int i = 0; i < groups.size(); i++)\r
 158         {\r
 159             SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
 160             SequenceI [] orderedseqs = sg.getSequencesInOrder(align);\r
 161             for (int j = 0; j < orderedseqs.length; j++)\r
 162             {\r
 163                 seqs.addElement(orderedseqs[j]);\r
 164             }\r
 165         }\r
 166 \r
 167         if (sortGroupAscending) {\r
 168             setOrder(align, seqs);\r
 169         } else {\r
 170             setReverseOrder(align,\r
 171                 vectorSubsetToArray(seqs, align.getSequences()));\r
 172         }\r
 173     }\r
 174 \r
 175     private static SequenceI[] vectorToArray(Vector tmp) {\r
 176 \r
 177         SequenceI[] seqs = new SequenceI[tmp.size()];\r
 178 \r
 179         for (int i = 0; i < tmp.size(); i++) {\r
 180             seqs[i] = (SequenceI) tmp.elementAt(i);\r
 181         }\r
 182 \r
 183         return seqs;\r
 184     }\r
 185 \r
 186     private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask) {\r
 187         Vector seqs = new Vector();\r
 188         int i;\r
 189         boolean[] tmask = new boolean[mask.size()];\r
 190 \r
 191         for (i = 0; i < mask.size(); i++)\r
 192             tmask[i] = true;\r
 193 \r
 194         for (i = 0; i < tmp.size(); i++) {\r
 195 \r
 196             Object sq = tmp.elementAt(i);\r
 197 \r
 198             if (mask.contains(sq) && tmask[mask.indexOf(sq)])\r
 199             {\r
 200                 tmask[mask.indexOf(sq)] = false;\r
 201                 seqs.addElement(sq);\r
 202             }\r
 203         }\r
 204 \r
 205         for (i = 0; i < tmask.length; i++)\r
 206             if (tmask[i]) {\r
 207                 seqs.addElement(mask.elementAt(i));\r
 208             }\r
 209 \r
 210         return vectorToArray(seqs);\r
 211     }\r
 212 \r
 213     public static void sortBy(AlignmentI align, AlignmentOrder order) {\r
 214         // Get an ordered vector of sequences which may also be present in align\r
 215         Vector tmp = order.getOrder();\r
 216 \r
 217         if (lastOrder == order) {\r
 218             sortOrderAscending = !sortOrderAscending;\r
 219         } else {\r
 220             sortOrderAscending = true;\r
 221         }\r
 222 \r
 223         if (sortOrderAscending) {\r
 224             setOrder(align, tmp);\r
 225         } else {\r
 226             setReverseOrder(align,\r
 227                 vectorSubsetToArray(tmp, align.getSequences()));\r
 228         }\r
 229     }\r
 230 \r
 231     public static Vector getOrderByTree(AlignmentI align, NJTree tree) {\r
 232         int nSeq = align.getHeight();\r
 233 \r
 234         Vector tmp = new Vector();\r
 235 \r
 236         tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());\r
 237 \r
 238         if (tmp.size() != nSeq) {\r
 239             // TODO: JBPNote - decide if this is always an error\r
 240             // (eg. not when a tree is associated to another alignment which has more\r
 241             //  sequences)\r
 242             if (tmp.size() < nSeq) {\r
 243                 addStrays(align, tmp);\r
 244             }\r
 245 \r
 246             if (tmp.size() != nSeq) {\r
 247                 System.err.println("ERROR: tmp.size()=" + tmp.size() +\r
 248                     " != nseq=" + nSeq + " in getOrderByTree");\r
 249             }\r
 250         }\r
 251 \r
 252         return tmp;\r
 253     }\r
 254 \r
 255     public static void sortByTree(AlignmentI align, NJTree tree) {\r
 256         Vector tmp = getOrderByTree(align, tree);\r
 257 \r
 258         // tmp should properly permute align with tree.\r
 259         if (lastTree != tree) {\r
 260             sortTreeAscending = true;\r
 261             lastTree = tree;\r
 262         } else {\r
 263             sortTreeAscending = !sortTreeAscending;\r
 264         }\r
 265 \r
 266         if (sortTreeAscending) {\r
 267             setOrder(align, tmp);\r
 268         } else {\r
 269             setReverseOrder(align,\r
 270                 vectorSubsetToArray(tmp, align.getSequences()));\r
 271         }\r
 272     }\r
 273 \r
 274     private static void addStrays(AlignmentI align, Vector seqs) {\r
 275         int nSeq = align.getHeight();\r
 276 \r
 277         for (int i = 0; i < nSeq; i++) {\r
 278             if (!seqs.contains(align.getSequenceAt(i))) {\r
 279                 seqs.addElement(align.getSequenceAt(i));\r
 280             }\r
 281         }\r
 282 \r
 283         if (nSeq != seqs.size()) {\r
 284             System.err.println(\r
 285                 "ERROR: Size still not right even after addStrays");\r
 286         }\r
 287     }\r
 288 \r
 289     public static Vector _sortByTree(SequenceNode node, Vector tmp,\r
 290         Vector seqset) {\r
 291         if (node == null) {\r
 292             return tmp;\r
 293         }\r
 294 \r
 295         SequenceNode left = (SequenceNode) node.left();\r
 296         SequenceNode right = (SequenceNode) node.right();\r
 297 \r
 298         if ((left == null) && (right == null)) {\r
 299             if (!node.isPlaceholder() && (node.element() != null)) {\r
 300                 if (node.element() instanceof SequenceI) {\r
 301                     if (!tmp.contains(node.element())) {\r
 302                         tmp.addElement((SequenceI) node.element());\r
 303                     }\r
 304                 }\r
 305             }\r
 306 \r
 307             return tmp;\r
 308         } else {\r
 309             _sortByTree(left, tmp, seqset);\r
 310             _sortByTree(right, tmp, seqset);\r
 311         }\r
 312 \r
 313         return tmp;\r
 314     }\r
 315 \r
 316     // Ordering Objects\r
 317     // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order\r
 318     //\r
 319 \r
 320     /**\r
 321      * recover the order of sequences given by the safe numbering scheme introducd\r
 322      * SeqsetUtils.uniquify.\r
 323      */\r
 324     public static void recoverOrder(SequenceI[] alignment) {\r
 325         float[] ids = new float[alignment.length];\r
 326 \r
 327         for (int i = 0; i < alignment.length; i++)\r
 328             ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();\r
 329 \r
 330         jalview.util.QuickSort.sort(ids, alignment);\r
 331     }\r
 332 }\r