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