Use system path separator char
[jalview.git] / src / jalview / analysis / AlignmentSorter.java
1 /*\r
2 * Jalview - A Sequence Alignment Editor and Viewer\r
3 * Copyright (C) 2006 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.util.*;\r
24 \r
25 import java.util.*;\r
26 \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     static boolean sortIdAscending = true;\r
33     static int lastGroupHash = 0;\r
34     static boolean sortGroupAscending = true;\r
35     static AlignmentOrder lastOrder = null;\r
36     static boolean sortOrderAscending = true;\r
37     static NJTree lastTree = null;\r
38     static boolean sortTreeAscending = true;\r
39 \r
40     /**\r
41      * Sort by Percentage Identity\r
42      *\r
43      * @param align AlignmentI\r
44      * @param s SequenceI\r
45      */\r
46     public static void sortByPID(AlignmentI align, SequenceI s)\r
47     {\r
48         int nSeq = align.getHeight();\r
49 \r
50         float[] scores = new float[nSeq];\r
51         SequenceI[] seqs = new SequenceI[nSeq];\r
52 \r
53         for (int i = 0; i < nSeq; i++)\r
54         {\r
55             scores[i] = Comparison.PID(align.getSequenceAt(i).getSequence(),\r
56                                        s.getSequence());\r
57             seqs[i] = align.getSequenceAt(i);\r
58         }\r
59 \r
60         QuickSort.sort(scores, 0, scores.length - 1, seqs);\r
61 \r
62         setReverseOrder(align, seqs);\r
63     }\r
64 \r
65     /**\r
66      * Reverse the order of the sort\r
67      *\r
68      * @param align DOCUMENT ME!\r
69      * @param seqs DOCUMENT ME!\r
70      */\r
71     private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)\r
72     {\r
73         int nSeq = seqs.length;\r
74 \r
75         int len = 0;\r
76 \r
77         if ((nSeq % 2) == 0)\r
78         {\r
79             len = nSeq / 2;\r
80         }\r
81         else\r
82         {\r
83             len = (nSeq + 1) / 2;\r
84         }\r
85 \r
86         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
87         for (int i = 0; i < len; i++)\r
88         {\r
89             //SequenceI tmp = seqs[i];\r
90             align.getSequences().setElementAt(seqs[nSeq - i - 1], i);\r
91             align.getSequences().setElementAt(seqs[i], nSeq - i - 1);\r
92         }\r
93     }\r
94 \r
95     /**\r
96      * Sets the Alignment object with the given sequences\r
97      *\r
98      * @param align Alignment object to be updated\r
99      * @param tmp sequences as a vector\r
100      */\r
101     private static void setOrder(AlignmentI align, Vector tmp)\r
102     {\r
103         setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));\r
104     }\r
105 \r
106     /**\r
107      * Sets the Alignment object with the given sequences\r
108      *\r
109      * @param align DOCUMENT ME!\r
110      * @param seqs sequences as an array\r
111      */\r
112     public static void setOrder(AlignmentI align, SequenceI[] seqs)\r
113     {\r
114         // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work\r
115         Vector algn = align.getSequences();\r
116 \r
117         int index = 0;\r
118         for (int i = 0; i < seqs.length; i++)\r
119         {\r
120           if(algn.contains(seqs[i]))\r
121             algn.setElementAt(seqs[i], index++);\r
122         }\r
123     }\r
124 \r
125     /**\r
126      * Sorts by ID. Numbers are sorted before letters.\r
127      *\r
128      * @param align The alignment object to sort\r
129      */\r
130     public static void sortByID(AlignmentI align)\r
131     {\r
132         int nSeq = align.getHeight();\r
133 \r
134         String[] ids = new String[nSeq];\r
135         SequenceI[] seqs = new SequenceI[nSeq];\r
136 \r
137         for (int i = 0; i < nSeq; i++)\r
138         {\r
139             ids[i] = align.getSequenceAt(i).getName();\r
140             seqs[i] = align.getSequenceAt(i);\r
141         }\r
142 \r
143         QuickSort.sort(ids, seqs);\r
144 \r
145         if (sortIdAscending)\r
146         {\r
147             setReverseOrder(align, seqs);\r
148         }\r
149         else\r
150         {\r
151             setOrder(align, seqs);\r
152         }\r
153 \r
154         sortIdAscending = !sortIdAscending;\r
155     }\r
156 \r
157     /**\r
158      * Sorts the alignment by size of group.\r
159      * <br>Maintains the order of sequences in each group\r
160      * by order in given alignment object.\r
161      *\r
162      * @param align sorts the given alignment object by group\r
163      */\r
164     public static void sortByGroup(AlignmentI align)\r
165     {\r
166         //MAINTAINS ORIGNAL SEQUENCE ORDER,\r
167         //ORDERS BY GROUP SIZE\r
168         Vector groups = new Vector();\r
169 \r
170         if (groups.hashCode() != lastGroupHash)\r
171         {\r
172             sortGroupAscending = true;\r
173             lastGroupHash = groups.hashCode();\r
174         }\r
175         else\r
176         {\r
177             sortGroupAscending = !sortGroupAscending;\r
178         }\r
179 \r
180         //SORTS GROUPS BY SIZE\r
181         //////////////////////\r
182         for (int i = 0; i < align.getGroups().size(); i++)\r
183         {\r
184             SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);\r
185 \r
186             for (int j = 0; j < groups.size(); j++)\r
187             {\r
188                 SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);\r
189 \r
190                 if (sg.getSize(false) > sg2.getSize(false))\r
191                 {\r
192                     groups.insertElementAt(sg, j);\r
193 \r
194                     break;\r
195                 }\r
196             }\r
197 \r
198             if (!groups.contains(sg))\r
199             {\r
200                 groups.addElement(sg);\r
201             }\r
202         }\r
203 \r
204         //NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER\r
205         ///////////////////////////////////////////////\r
206         Vector seqs = new Vector();\r
207 \r
208         for (int i = 0; i < groups.size(); i++)\r
209         {\r
210             SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
211             SequenceI[] orderedseqs = sg.getSequencesInOrder(align);\r
212 \r
213             for (int j = 0; j < orderedseqs.length; j++)\r
214             {\r
215                 seqs.addElement(orderedseqs[j]);\r
216             }\r
217         }\r
218 \r
219         if (sortGroupAscending)\r
220         {\r
221             setOrder(align, seqs);\r
222         }\r
223         else\r
224         {\r
225             setReverseOrder(align,\r
226                 vectorSubsetToArray(seqs, align.getSequences()));\r
227         }\r
228     }\r
229 \r
230     /**\r
231      * Converts Vector to array.\r
232      * java 1.18 does not have Vector.toArray()\r
233      *\r
234      * @param tmp Vector of SequenceI objects\r
235      *\r
236      * @return array of Sequence[]\r
237      */\r
238     private static SequenceI[] vectorToArray(Vector tmp)\r
239     {\r
240         SequenceI[] seqs = new SequenceI[tmp.size()];\r
241 \r
242         for (int i = 0; i < tmp.size(); i++)\r
243         {\r
244             seqs[i] = (SequenceI) tmp.elementAt(i);\r
245         }\r
246 \r
247         return seqs;\r
248     }\r
249 \r
250     /**\r
251      * DOCUMENT ME!\r
252      *\r
253      * @param tmp DOCUMENT ME!\r
254      * @param mask DOCUMENT ME!\r
255      *\r
256      * @return DOCUMENT ME!\r
257      */\r
258     private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)\r
259     {\r
260         Vector seqs = new Vector();\r
261         int i;\r
262         boolean[] tmask = new boolean[mask.size()];\r
263 \r
264         for (i = 0; i < mask.size(); i++)\r
265             tmask[i] = true;\r
266 \r
267         for (i = 0; i < tmp.size(); i++)\r
268         {\r
269             Object sq = tmp.elementAt(i);\r
270 \r
271             if (mask.contains(sq) && tmask[mask.indexOf(sq)])\r
272             {\r
273                 tmask[mask.indexOf(sq)] = false;\r
274                 seqs.addElement(sq);\r
275             }\r
276         }\r
277 \r
278         for (i = 0; i < tmask.length; i++)\r
279             if (tmask[i])\r
280             {\r
281                 seqs.addElement(mask.elementAt(i));\r
282             }\r
283 \r
284         return vectorToArray(seqs);\r
285     }\r
286 \r
287     /**\r
288      * Sorts by a given AlignmentOrder object\r
289      *\r
290      * @param align Alignment to order\r
291      * @param order specified order for alignment\r
292      */\r
293     public static void sortBy(AlignmentI align, AlignmentOrder order)\r
294     {\r
295         // Get an ordered vector of sequences which may also be present in align\r
296         Vector tmp = order.getOrder();\r
297 \r
298         if (lastOrder == order)\r
299         {\r
300             sortOrderAscending = !sortOrderAscending;\r
301         }\r
302         else\r
303         {\r
304             sortOrderAscending = true;\r
305         }\r
306 \r
307         if (sortOrderAscending)\r
308         {\r
309             setOrder(align, tmp);\r
310         }\r
311         else\r
312         {\r
313             setReverseOrder(align,\r
314                 vectorSubsetToArray(tmp, align.getSequences()));\r
315         }\r
316     }\r
317 \r
318     /**\r
319      * DOCUMENT ME!\r
320      *\r
321      * @param align alignment to order\r
322      * @param tree tree which has\r
323      *\r
324      * @return DOCUMENT ME!\r
325      */\r
326     private static Vector getOrderByTree(AlignmentI align, NJTree tree)\r
327     {\r
328         int nSeq = align.getHeight();\r
329 \r
330         Vector tmp = new Vector();\r
331 \r
332         tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());\r
333 \r
334         if (tmp.size() != nSeq)\r
335         {\r
336             // TODO: JBPNote - decide if this is always an error\r
337             // (eg. not when a tree is associated to another alignment which has more\r
338             //  sequences)\r
339             if (tmp.size() < nSeq)\r
340             {\r
341                 addStrays(align, tmp);\r
342             }\r
343 \r
344             if (tmp.size() != nSeq)\r
345             {\r
346                 System.err.println("ERROR: tmp.size()=" + tmp.size() +\r
347                     " != nseq=" + nSeq + " in getOrderByTree");\r
348             }\r
349         }\r
350 \r
351         return tmp;\r
352     }\r
353 \r
354     /**\r
355      * Sorts the alignment by a given tree\r
356      *\r
357      * @param align alignment to order\r
358      * @param tree tree which has\r
359      */\r
360     public static void sortByTree(AlignmentI align, NJTree tree)\r
361     {\r
362         Vector tmp = getOrderByTree(align, tree);\r
363 \r
364         // tmp should properly permute align with tree.\r
365         if (lastTree != tree)\r
366         {\r
367             sortTreeAscending = true;\r
368             lastTree = tree;\r
369         }\r
370         else\r
371         {\r
372             sortTreeAscending = !sortTreeAscending;\r
373         }\r
374 \r
375         if (sortTreeAscending)\r
376         {\r
377             setOrder(align, tmp);\r
378         }\r
379         else\r
380         {\r
381             setReverseOrder(align,\r
382                 vectorSubsetToArray(tmp, align.getSequences()));\r
383         }\r
384     }\r
385 \r
386     /**\r
387      * DOCUMENT ME!\r
388      *\r
389      * @param align DOCUMENT ME!\r
390      * @param seqs DOCUMENT ME!\r
391      */\r
392     private static void addStrays(AlignmentI align, Vector seqs)\r
393     {\r
394         int nSeq = align.getHeight();\r
395 \r
396         for (int i = 0; i < nSeq; i++)\r
397         {\r
398             if (!seqs.contains(align.getSequenceAt(i)))\r
399             {\r
400                 seqs.addElement(align.getSequenceAt(i));\r
401             }\r
402         }\r
403 \r
404         if (nSeq != seqs.size())\r
405         {\r
406             System.err.println(\r
407                 "ERROR: Size still not right even after addStrays");\r
408         }\r
409     }\r
410 \r
411     /**\r
412      * DOCUMENT ME!\r
413      *\r
414      * @param node DOCUMENT ME!\r
415      * @param tmp DOCUMENT ME!\r
416      * @param seqset DOCUMENT ME!\r
417      *\r
418      * @return DOCUMENT ME!\r
419      */\r
420     private static Vector _sortByTree(SequenceNode node, Vector tmp,\r
421         Vector seqset)\r
422     {\r
423         if (node == null)\r
424         {\r
425             return tmp;\r
426         }\r
427 \r
428         SequenceNode left = (SequenceNode) node.left();\r
429         SequenceNode right = (SequenceNode) node.right();\r
430 \r
431         if ((left == null) && (right == null))\r
432         {\r
433             if (!node.isPlaceholder() && (node.element() != null))\r
434             {\r
435                 if (node.element() instanceof SequenceI)\r
436                 {\r
437                     if (!tmp.contains(node.element()))\r
438                     {\r
439                         tmp.addElement((SequenceI) node.element());\r
440                     }\r
441                 }\r
442             }\r
443 \r
444             return tmp;\r
445         }\r
446         else\r
447         {\r
448             _sortByTree(left, tmp, seqset);\r
449             _sortByTree(right, tmp, seqset);\r
450         }\r
451 \r
452         return tmp;\r
453     }\r
454 \r
455     // Ordering Objects\r
456     // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order\r
457     //\r
458 \r
459     /**\r
460      * recover the order of sequences given by the safe numbering scheme introducd\r
461      * SeqsetUtils.uniquify.\r
462      */\r
463     public static void recoverOrder(SequenceI[] alignment)\r
464     {\r
465         float[] ids = new float[alignment.length];\r
466 \r
467         for (int i = 0; i < alignment.length; i++)\r
468             ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();\r
469 \r
470         jalview.util.QuickSort.sort(ids, alignment);\r
471     }\r
472 }\r