src/jalview/analysis/AlignmentSorter.java

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