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