src/jalview/analysis/AlignmentSorter.java

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