2 * Jalview - A Sequence Alignment Editor and Viewer
\r
3 * Copyright (C) 2005 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
\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
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
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
19 package jalview.analysis;
\r
21 import jalview.datamodel.*;
\r
23 import jalview.io.*;
\r
25 import jalview.util.*;
\r
30 /** Data structure to hold and manipulate a multiple sequence alignment
\r
32 public class AlignmentSorter {
\r
34 static boolean sortIdAscending = true;
\r
35 static int lastGroupHash = 0;
\r
36 static boolean sortGroupAscending = true;
\r
37 static AlignmentOrder lastOrder = null;
\r
38 static boolean sortOrderAscending = true;
\r
39 static NJTree lastTree = null;
\r
40 static boolean sortTreeAscending = true;
\r
42 private AlignmentSorter() {
\r
45 } catch (Exception ex) {
\r
46 ex.printStackTrace();
\r
50 public static void sortGroups(AlignmentI align) {
\r
51 Vector groups = align.getGroups();
\r
52 int nGroup = groups.size();
\r
54 float[] arr = new float[nGroup];
\r
55 Object[] s = new Object[nGroup];
\r
57 for (int i = 0; i < nGroup; i++) {
\r
58 arr[i] = ((SequenceGroup) groups.elementAt(i)).getSize();
\r
59 s[i] = groups.elementAt(i);
\r
62 QuickSort.sort(arr, s);
\r
64 // align..setGroups(newg);
\r
68 * Sort by Percentage Identity
\r
70 * @param align AlignmentI
\r
71 * @param s SequenceI
\r
73 public static void sortByPID(AlignmentI align, SequenceI s) {
\r
74 int nSeq = align.getHeight();
\r
76 float[] scores = new float[nSeq];
\r
77 SequenceI[] seqs = new SequenceI[nSeq];
\r
79 for (int i = 0; i < nSeq; i++) {
\r
80 scores[i] = Comparison.PID(align.getSequenceAt(i), s);
\r
81 seqs[i] = align.getSequenceAt(i);
\r
84 QuickSort.sort(scores, 0, scores.length - 1, seqs);
\r
86 setReverseOrder(align, seqs);
\r
89 private static void setReverseOrder(AlignmentI align, SequenceI[] seqs) {
\r
90 int nSeq = seqs.length;
\r
94 if ((nSeq % 2) == 0) {
\r
97 len = (nSeq + 1) / 2;
\r
100 // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
\r
101 for (int i = 0; i < len; i++) {
\r
102 //SequenceI tmp = seqs[i];
\r
103 align.getSequences().setElementAt(seqs[nSeq - i - 1], i);
\r
104 align.getSequences().setElementAt(seqs[i], nSeq - i - 1);
\r
108 private static void setOrder(AlignmentI align, Vector tmp) {
\r
109 setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
\r
112 private static void setOrder(AlignmentI align, SequenceI[] seqs) {
\r
113 // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
\r
114 Vector algn = align.getSequences();
\r
116 for (int i = 0, p = 0; i < seqs.length; i++)
\r
117 algn.setElementAt(seqs[i], p++);
\r
120 public static void sortByID(AlignmentI align) {
\r
121 int nSeq = align.getHeight();
\r
123 String[] ids = new String[nSeq];
\r
124 SequenceI[] seqs = new SequenceI[nSeq];
\r
126 for (int i = 0; i < nSeq; i++) {
\r
127 ids[i] = align.getSequenceAt(i).getName();
\r
128 seqs[i] = align.getSequenceAt(i);
\r
131 QuickSort.sort(ids, seqs);
\r
133 if (sortIdAscending) {
\r
134 setReverseOrder(align, seqs);
\r
136 setOrder(align, seqs);
\r
139 sortIdAscending = !sortIdAscending;
\r
142 public static void sortByGroup(AlignmentI align) {
\r
143 Vector groups = align.getGroups();
\r
145 if (groups.hashCode() != lastGroupHash) {
\r
146 sortGroupAscending = true;
\r
147 lastGroupHash = groups.hashCode();
\r
149 sortGroupAscending = !sortGroupAscending;
\r
152 Vector seqs = new Vector();
\r
154 for (int i = 0; i < groups.size(); i++) {
\r
155 SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
\r
157 for (int j = 0; j < sg.getSize(); j++) {
\r
158 seqs.addElement(sg.getSequenceAt(j));
\r
162 // Deletions can happen so this check may fail
\r
165 if (seqs.size() != nSeq) {
\r
166 System.err.println("ERROR: tmp.size() != nseq in sortByGroups");
\r
167 if (seqs.size() < nSeq) {
\r
168 addStrays(align,seqs);
\r
172 if (sortGroupAscending) {
\r
173 setOrder(align, seqs);
\r
175 setReverseOrder(align,
\r
176 vectorSubsetToArray(seqs, align.getSequences()));
\r
180 private static SequenceI[] vectorToArray(Vector tmp) {
\r
181 SequenceI[] seqs = new SequenceI[tmp.size()];
\r
183 for (int i = 0; i < tmp.size(); i++) {
\r
184 seqs[i] = (SequenceI) tmp.elementAt(i);
\r
190 private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask) {
\r
191 Vector seqs = new Vector();
\r
195 boolean[] tmask = new boolean[m = mask.size()];
\r
197 for (i = 0; i < m; i++)
\r
200 for (i = 0; i < tmp.size(); i++) {
\r
203 if (mask.contains(sq = tmp.elementAt(i))) {
\r
204 tmask[mask.indexOf(sq)] = false;
\r
205 seqs.addElement(sq);
\r
210 for (i = 0; i < tmask.length; i++)
\r
212 seqs.addElement(mask.elementAt(i));
\r
215 return vectorToArray(seqs);
\r
218 public static void sortBy(AlignmentI align, AlignmentOrder order) {
\r
219 // Get an ordered vector of sequences which may also be present in align
\r
220 Vector tmp = order.getOrder();
\r
222 // if (tmp.size()<align.getHeight())
\r
223 // addStrays(align, tmp);
\r
224 if (lastOrder == order) {
\r
225 sortOrderAscending = !sortOrderAscending;
\r
227 sortOrderAscending = true;
\r
230 if (sortOrderAscending) {
\r
231 setOrder(align, tmp);
\r
233 setReverseOrder(align,
\r
234 vectorSubsetToArray(tmp, align.getSequences()));
\r
238 public static Vector getOrderByTree(AlignmentI align, NJTree tree) {
\r
239 int nSeq = align.getHeight();
\r
241 Vector tmp = new Vector();
\r
243 tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
\r
245 if (tmp.size() != nSeq) {
\r
246 // TODO: JBPNote - decide if this is always an error
\r
247 // (eg. not when a tree is associated to another alignment which has more
\r
249 if (tmp.size() < nSeq) {
\r
250 addStrays(align, tmp);
\r
253 if (tmp.size() != nSeq) {
\r
254 System.err.println("ERROR: tmp.size()=" + tmp.size() +
\r
255 " != nseq=" + nSeq + " in getOrderByTree");
\r
262 public static void sortByTree(AlignmentI align, NJTree tree) {
\r
263 Vector tmp = getOrderByTree(align, tree);
\r
265 // tmp should properly permute align with tree.
\r
266 if (lastTree != tree) {
\r
267 sortTreeAscending = true;
\r
270 sortTreeAscending = !sortTreeAscending;
\r
273 if (sortTreeAscending) {
\r
274 setOrder(align, tmp);
\r
276 setReverseOrder(align,
\r
277 vectorSubsetToArray(tmp, align.getSequences()));
\r
281 private static void addStrays(AlignmentI align, Vector seqs) {
\r
282 int nSeq = align.getHeight();
\r
284 for (int i = 0; i < nSeq; i++) {
\r
285 if (!seqs.contains(align.getSequenceAt(i))) {
\r
286 seqs.addElement(align.getSequenceAt(i));
\r
290 if (nSeq != seqs.size()) {
\r
291 System.err.println(
\r
292 "ERROR: Size still not right even after addStrays");
\r
296 public static Vector _sortByTree(SequenceNode node, Vector tmp,
\r
298 if (node == null) {
\r
302 SequenceNode left = (SequenceNode) node.left();
\r
303 SequenceNode right = (SequenceNode) node.right();
\r
305 if ((left == null) && (right == null)) {
\r
306 if (!node.isPlaceholder() && (node.element() != null)) {
\r
307 if (node.element() instanceof SequenceI) {
\r
308 if (!tmp.contains(node.element())) {
\r
309 tmp.addElement((SequenceI) node.element());
\r
316 _sortByTree(left, tmp, seqset);
\r
317 _sortByTree(right, tmp, seqset);
\r
323 // Ordering Objects
\r
324 // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in appropriate order
\r
328 * recover the order of sequences given by the safe numbering scheme introducd
\r
329 * SeqsetUtils.uniquify.
\r
331 public static void recoverOrder(SequenceI[] alignment) {
\r
332 float[] ids = new float[alignment.length];
\r
334 for (int i = 0; i < alignment.length; i++)
\r
335 ids[i] = (new Float(alignment[i].getName().substring(8))).floatValue();
\r
337 jalview.util.QuickSort.sort(ids, alignment);
\r
340 private void jbInit() throws Exception {
\r