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 }