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