JnetFIle is a readable format
[jalview.git] / src / jalview / analysis / AlignmentSorter.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer
3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
18  */
19 package jalview.analysis;
20
21 import java.util.*;
22
23 import jalview.datamodel.*;
24 import jalview.util.*;
25
26 /** 
27  * Routines for manipulating the order of a multiple sequence alignment
28  * TODO: this class retains some global states concerning sort-order which should be made attributes for the caller's alignment visualization. 
29  */
30 public class AlignmentSorter
31 {
32   static boolean sortIdAscending = true;
33   static int lastGroupHash = 0;
34   static boolean sortGroupAscending = true;
35   static AlignmentOrder lastOrder = null;
36   static boolean sortOrderAscending = true;
37   static NJTree lastTree = null;
38   static boolean sortTreeAscending = true;
39   private static String lastSortByScore;
40
41   /**
42    * Sort by Percentage Identity
43    *
44    * @param align AlignmentI
45    * @param s SequenceI
46    */
47   public static void sortByPID(AlignmentI align, SequenceI s)
48   {
49     int nSeq = align.getHeight();
50
51     float[] scores = new float[nSeq];
52     SequenceI[] seqs = new SequenceI[nSeq];
53
54     for (int i = 0; i < nSeq; i++)
55     {
56       scores[i] = Comparison.PID(align.getSequenceAt(i).getSequenceAsString(),
57                                  s.getSequenceAsString());
58       seqs[i] = align.getSequenceAt(i);
59     }
60
61     QuickSort.sort(scores, 0, scores.length - 1, seqs);
62
63     setReverseOrder(align, seqs);
64   }
65
66   /**
67    * Reverse the order of the sort
68    *
69    * @param align DOCUMENT ME!
70    * @param seqs DOCUMENT ME!
71    */
72   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
73   {
74     int nSeq = seqs.length;
75
76     int len = 0;
77
78     if ( (nSeq % 2) == 0)
79     {
80       len = nSeq / 2;
81     }
82     else
83     {
84       len = (nSeq + 1) / 2;
85     }
86
87     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
88     for (int i = 0; i < len; i++)
89     {
90       //SequenceI tmp = seqs[i];
91       align.getSequences().setElementAt(seqs[nSeq - i - 1], i);
92       align.getSequences().setElementAt(seqs[i], nSeq - i - 1);
93     }
94   }
95
96   /**
97    * Sets the Alignment object with the given sequences
98    *
99    * @param align Alignment object to be updated
100    * @param tmp sequences as a vector
101    */
102   private static void setOrder(AlignmentI align, Vector tmp)
103   {
104     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
105   }
106
107   /**
108    * Sets the Alignment object with the given sequences
109    *
110    * @param align DOCUMENT ME!
111    * @param seqs sequences as an array
112    */
113   public static void setOrder(AlignmentI align, SequenceI[] seqs)
114   {
115     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
116     Vector algn = align.getSequences();
117     Vector tmp = new Vector();
118
119     for (int i = 0; i < seqs.length; i++)
120     {
121       if (algn.contains(seqs[i]))
122       {
123         tmp.addElement(seqs[i]);
124       }
125     }
126
127     algn.removeAllElements();
128     //User may have hidden seqs, then clicked undo or redo
129     for (int i = 0; i < tmp.size(); i++)
130     {
131       algn.addElement(tmp.elementAt(i));
132     }
133
134   }
135
136   /**
137    * Sorts by ID. Numbers are sorted before letters.
138    *
139    * @param align The alignment object to sort
140    */
141   public static void sortByID(AlignmentI align)
142   {
143     int nSeq = align.getHeight();
144
145     String[] ids = new String[nSeq];
146     SequenceI[] seqs = new SequenceI[nSeq];
147
148     for (int i = 0; i < nSeq; i++)
149     {
150       ids[i] = align.getSequenceAt(i).getName();
151       seqs[i] = align.getSequenceAt(i);
152     }
153
154     QuickSort.sort(ids, seqs);
155
156     if (sortIdAscending)
157     {
158       setReverseOrder(align, seqs);
159     }
160     else
161     {
162       setOrder(align, seqs);
163     }
164
165     sortIdAscending = !sortIdAscending;
166   }
167
168   /**
169    * Sorts the alignment by size of group.
170    * <br>Maintains the order of sequences in each group
171    * by order in given alignment object.
172    *
173    * @param align sorts the given alignment object by group
174    */
175   public static void sortByGroup(AlignmentI align)
176   {
177     //MAINTAINS ORIGNAL SEQUENCE ORDER,
178     //ORDERS BY GROUP SIZE
179     Vector groups = new Vector();
180
181     if (groups.hashCode() != lastGroupHash)
182     {
183       sortGroupAscending = true;
184       lastGroupHash = groups.hashCode();
185     }
186     else
187     {
188       sortGroupAscending = !sortGroupAscending;
189     }
190
191     //SORTS GROUPS BY SIZE
192     //////////////////////
193     for (int i = 0; i < align.getGroups().size(); i++)
194     {
195       SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);
196
197       for (int j = 0; j < groups.size(); j++)
198       {
199         SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);
200
201         if (sg.getSize() > sg2.getSize())
202         {
203           groups.insertElementAt(sg, j);
204
205           break;
206         }
207       }
208
209       if (!groups.contains(sg))
210       {
211         groups.addElement(sg);
212       }
213     }
214
215     //NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER
216     ///////////////////////////////////////////////
217     Vector seqs = new Vector();
218
219     for (int i = 0; i < groups.size(); i++)
220     {
221       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
222       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);
223
224       for (int j = 0; j < orderedseqs.length; j++)
225       {
226         seqs.addElement(orderedseqs[j]);
227       }
228     }
229
230     if (sortGroupAscending)
231     {
232       setOrder(align, seqs);
233     }
234     else
235     {
236       setReverseOrder(align,
237                       vectorSubsetToArray(seqs, align.getSequences()));
238     }
239   }
240
241   /**
242    * Converts Vector to array.
243    * java 1.18 does not have Vector.toArray()
244    *
245    * @param tmp Vector of SequenceI objects
246    *
247    * @return array of Sequence[]
248    */
249   private static SequenceI[] vectorToArray(Vector tmp)
250   {
251     SequenceI[] seqs = new SequenceI[tmp.size()];
252
253     for (int i = 0; i < tmp.size(); i++)
254     {
255       seqs[i] = (SequenceI) tmp.elementAt(i);
256     }
257
258     return seqs;
259   }
260
261   /**
262    * DOCUMENT ME!
263    *
264    * @param tmp DOCUMENT ME!
265    * @param mask DOCUMENT ME!
266    *
267    * @return DOCUMENT ME!
268    */
269   private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)
270   {
271     Vector seqs = new Vector();
272     int i;
273     boolean[] tmask = new boolean[mask.size()];
274
275     for (i = 0; i < mask.size(); i++)
276     {
277       tmask[i] = true;
278     }
279
280     for (i = 0; i < tmp.size(); i++)
281     {
282       Object sq = tmp.elementAt(i);
283
284       if (mask.contains(sq) && tmask[mask.indexOf(sq)])
285       {
286         tmask[mask.indexOf(sq)] = false;
287         seqs.addElement(sq);
288       }
289     }
290
291     for (i = 0; i < tmask.length; i++)
292     {
293       if (tmask[i])
294       {
295         seqs.addElement(mask.elementAt(i));
296       }
297     }
298
299     return vectorToArray(seqs);
300   }
301
302   /**
303    * Sorts by a given AlignmentOrder object
304    *
305    * @param align Alignment to order
306    * @param order specified order for alignment
307    */
308   public static void sortBy(AlignmentI align, AlignmentOrder order)
309   {
310     // Get an ordered vector of sequences which may also be present in align
311     Vector tmp = order.getOrder();
312
313     if (lastOrder == order)
314     {
315       sortOrderAscending = !sortOrderAscending;
316     }
317     else
318     {
319       sortOrderAscending = true;
320     }
321
322     if (sortOrderAscending)
323     {
324       setOrder(align, tmp);
325     }
326     else
327     {
328       setReverseOrder(align,
329                       vectorSubsetToArray(tmp, align.getSequences()));
330     }
331   }
332
333   /**
334    * DOCUMENT ME!
335    *
336    * @param align alignment to order
337    * @param tree tree which has
338    *
339    * @return DOCUMENT ME!
340    */
341   private static Vector getOrderByTree(AlignmentI align, NJTree tree)
342   {
343     int nSeq = align.getHeight();
344
345     Vector tmp = new Vector();
346
347     tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
348
349     if (tmp.size() != nSeq)
350     {
351       // TODO: JBPNote - decide if this is always an error
352       // (eg. not when a tree is associated to another alignment which has more
353       //  sequences)
354       if (tmp.size() < nSeq)
355       {
356         addStrays(align, tmp);
357       }
358
359       if (tmp.size() != nSeq)
360       {
361         System.err.println("ERROR: tmp.size()=" + tmp.size() +
362                            " != nseq=" + nSeq + " in getOrderByTree");
363       }
364     }
365
366     return tmp;
367   }
368
369   /**
370    * Sorts the alignment by a given tree
371    *
372    * @param align alignment to order
373    * @param tree tree which has
374    */
375   public static void sortByTree(AlignmentI align, NJTree tree)
376   {
377     Vector tmp = getOrderByTree(align, tree);
378
379     // tmp should properly permute align with tree.
380     if (lastTree != tree)
381     {
382       sortTreeAscending = true;
383       lastTree = tree;
384     }
385     else
386     {
387       sortTreeAscending = !sortTreeAscending;
388     }
389
390     if (sortTreeAscending)
391     {
392       setOrder(align, tmp);
393     }
394     else
395     {
396       setReverseOrder(align,
397                       vectorSubsetToArray(tmp, align.getSequences()));
398     }
399   }
400
401   /**
402    * DOCUMENT ME!
403    *
404    * @param align DOCUMENT ME!
405    * @param seqs DOCUMENT ME!
406    */
407   private static void addStrays(AlignmentI align, Vector seqs)
408   {
409     int nSeq = align.getHeight();
410
411     for (int i = 0; i < nSeq; i++)
412     {
413       if (!seqs.contains(align.getSequenceAt(i)))
414       {
415         seqs.addElement(align.getSequenceAt(i));
416       }
417     }
418
419     if (nSeq != seqs.size())
420     {
421       System.err.println(
422           "ERROR: Size still not right even after addStrays");
423     }
424   }
425
426   /**
427    * DOCUMENT ME!
428    *
429    * @param node DOCUMENT ME!
430    * @param tmp DOCUMENT ME!
431    * @param seqset DOCUMENT ME!
432    *
433    * @return DOCUMENT ME!
434    */
435   private static Vector _sortByTree(SequenceNode node, Vector tmp,
436                                     Vector seqset)
437   {
438     if (node == null)
439     {
440       return tmp;
441     }
442
443     SequenceNode left = (SequenceNode) node.left();
444     SequenceNode right = (SequenceNode) node.right();
445
446     if ( (left == null) && (right == null))
447     {
448       if (!node.isPlaceholder() && (node.element() != null))
449       {
450         if (node.element() instanceof SequenceI)
451         {
452           if (!tmp.contains(node.element()))
453           {
454             tmp.addElement( (SequenceI) node.element());
455           }
456         }
457       }
458
459       return tmp;
460     }
461     else
462     {
463       _sortByTree(left, tmp, seqset);
464       _sortByTree(right, tmp, seqset);
465     }
466
467     return tmp;
468   }
469
470   // Ordering Objects
471   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order
472   //
473
474   /**
475    * recover the order of sequences given by the safe numbering scheme introducd
476    * SeqsetUtils.uniquify.
477    */
478   public static void recoverOrder(SequenceI[] alignment)
479   {
480     float[] ids = new float[alignment.length];
481
482     for (int i = 0; i < alignment.length; i++)
483     {
484       ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();
485     }
486
487     jalview.util.QuickSort.sort(ids, alignment);
488   }
489   /**
490    * Sort sequence in order of increasing score attribute for annotation with a particular
491    * scoreLabel. Or reverse if same label was used previously
492    * @param scoreLabel exact label for sequence associated AlignmentAnnotation scores to use for sorting.
493    * @param alignment sequences to be sorted
494    */
495   public static void sortByAnnotationScore(String scoreLabel, AlignmentI alignment)
496   {
497     SequenceI[] seqs = alignment.getSequencesArray();
498     boolean[] hasScore = new boolean[seqs.length]; // per sequence score presence
499     int hasScores=0; // number of scores present on set
500     double[] scores = new double[seqs.length];
501     double min=0,max=0;
502     for (int i = 0; i < seqs.length; i++)
503     {
504       AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
505       if (scoreAnn!=null)
506       {
507         hasScores++;
508         hasScore[i] = true;
509         scores[i] = scoreAnn[0].getScore(); // take the first instance of this score.
510         if (hasScores==1)
511         {
512           max = min = scores[i];
513         } else
514         {
515           if (max<scores[i])
516           {
517             max = scores[i];
518           }
519           if (min>scores[i])
520           {
521             min = scores[i];
522           }
523         }
524       }
525       else
526       {
527         hasScore[i] = false;
528       }
529     }
530     if (hasScores==0)
531     {
532       return; // do nothing - no scores present to sort by.
533     }
534     if (hasScores<seqs.length)
535     {
536       for (int i=0; i<seqs.length;i++)
537       {
538         if (!hasScore[i])
539         {
540           scores[i] = (max+i);
541         }
542       }
543     }
544     
545     jalview.util.QuickSort.sort(scores, seqs);
546     if (lastSortByScore!=scoreLabel)
547     {
548       lastSortByScore = scoreLabel;
549       setOrder(alignment, seqs);
550     } else {
551       setReverseOrder(alignment, seqs);
552     }
553   }
554 }