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