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