1 package jalview.analysis;
\r
3 import jalview.datamodel.*;
\r
4 import jalview.util.*;
\r
9 /** Data structure to hold and manipulate a multiple sequence alignment
\r
11 public class AlignmentSorter {
\r
13 private AlignmentSorter() {
\r
18 catch (Exception ex)
\r
20 ex.printStackTrace();
\r
24 public static void sortGroups(AlignmentI align) {
\r
25 Vector groups = align.getGroups();
\r
26 int nGroup = groups.size();
\r
28 float[] arr = new float [nGroup];
\r
29 Object[] s = new Object[nGroup];
\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
36 QuickSort.sort(arr,s);
\r
38 Vector newg = new Vector(nGroup);
\r
40 for (int i=nGroup-1; i >= 0; i--) {
\r
41 newg.addElement(s[i]);
\r
44 // align.setGroups(newg);
\r
48 * Sort by Percentage Identity
\r
50 * @param align AlignmentI
\r
51 * @param s SequenceI
\r
53 public static void sortByPID(AlignmentI align, SequenceI s) {
\r
54 int nSeq = align.getHeight();
\r
56 float scores[] = new float[nSeq];
\r
57 SequenceI seqs[] = new SequenceI[nSeq];
\r
59 for (int i = 0; i < nSeq; i++) {
\r
60 scores[i] = Comparison.compare(align.getSequenceAt(i),s);
\r
61 seqs[i] = align.getSequenceAt(i);
\r
64 QuickSort.sort(scores,0,scores.length-1,seqs);
\r
66 setReverseOrder(align,seqs);
\r
69 private static void setReverseOrder(AlignmentI align, SequenceI [] seqs) {
\r
70 int nSeq = seqs.length;
\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
87 private static void setOrder(AlignmentI align, Vector tmp) {
\r
88 setOrder(align,vectorSubsetToArray(tmp, align.getSequences()));
\r
91 private static void setOrder(AlignmentI align, SequenceI [] seqs) {
\r
92 // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
\r
94 Vector algn = align.getSequences();
\r
96 for (int i = 0, p = 0; i < seqs.length; i++)
\r
97 algn.setElementAt(seqs[i], p++);
\r
100 static boolean sortIdAscending = true;
\r
101 public static void sortByID(AlignmentI align) {
\r
102 int nSeq = align.getHeight();
\r
104 String ids[] = new String[nSeq];
\r
105 SequenceI seqs[] = new SequenceI[nSeq];
\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
112 QuickSort.sort(ids,seqs);
\r
114 if(sortIdAscending)
\r
115 setReverseOrder(align,seqs);
\r
117 setOrder(align, seqs);
\r
119 sortIdAscending = !sortIdAscending;
\r
121 static int lastGroupHash = 0;
\r
122 static boolean sortGroupAscending = true;
\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
131 sortGroupAscending = ! sortGroupAscending;
\r
133 Vector seqs = new Vector();
\r
135 for (int i=0; i < groups.size(); i++) {
\r
136 SequenceGroup sg = (SequenceGroup)groups.elementAt(i);
\r
138 for (int j = 0; j < sg.getSize(); j++) {
\r
139 seqs.addElement(sg.getSequenceAt(j));
\r
143 // Deletions can happen so this check may fail
\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
152 if(sortGroupAscending)
\r
153 setOrder(align,seqs);
\r
155 setReverseOrder( align, vectorSubsetToArray(seqs, align.getSequences()));
\r
159 private static SequenceI [] vectorToArray(Vector tmp) {
\r
160 SequenceI[] seqs = new SequenceI[tmp.size()];
\r
162 for (int i=0; i < tmp.size(); i++) {
\r
163 seqs[i] = (SequenceI)tmp.elementAt(i);
\r
168 private static SequenceI [] vectorSubsetToArray(Vector tmp, Vector mask) {
\r
169 Vector seqs = new Vector();
\r
171 boolean[] tmask = new boolean[m=mask.size()];
\r
172 for (i=0; i<m; i++)
\r
174 for (i=0; i < tmp.size(); i++) {
\r
176 if (mask.contains(sq=tmp.elementAt(i))) {
\r
177 tmask[mask.indexOf(sq)] = false;
\r
178 seqs.addElement(sq);
\r
182 for (i=0; i<tmask.length; i++)
\r
184 seqs.addElement(mask.elementAt(i));
\r
185 return vectorToArray(seqs);
\r
188 static AlignmentOrder lastOrder = null;
\r
189 static boolean sortOrderAscending = true;
\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
199 sortOrderAscending=true;
\r
201 if (sortOrderAscending)
\r
202 setOrder(align, tmp);
\r
204 setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
\r
206 static NJTree lastTree = null;
\r
207 static boolean sortTreeAscending = true;
\r
209 public static Vector getOrderByTree(AlignmentI align, NJTree tree) {
\r
210 int nSeq = align.getHeight();
\r
212 Vector tmp = new Vector();
\r
214 tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
\r
216 if (tmp.size() != nSeq)
\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
222 if (tmp.size() < nSeq)
\r
224 addStrays(align, tmp);
\r
226 if (tmp.size() != nSeq)
\r
227 System.err.println("ERROR: tmp.size()="+tmp.size()+" != nseq="+nSeq+" in getOrderByTree");
\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
240 sortTreeAscending = !sortTreeAscending;
\r
242 if(sortTreeAscending)
\r
243 setOrder(align,tmp);
\r
245 setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
\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
255 if (nSeq != seqs.size()) {
\r
256 System.err.println("ERROR: Size still not right even after addStrays");
\r
260 public static Vector _sortByTree(SequenceNode node, Vector tmp, Vector seqset) {
\r
261 if (node == null) {return tmp;}
\r
263 SequenceNode left = (SequenceNode)node.left();
\r
264 SequenceNode right = (SequenceNode)node.right();
\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
274 _sortByTree(left,tmp, seqset);
\r
275 _sortByTree(right,tmp, seqset);
\r
279 // Ordering Objects
\r
280 // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order
\r
284 * recover the order of sequences given by the safe numbering scheme introducd
\r
285 * SeqsetUtils.uniquify.
\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
294 private void jbInit()
\r