src/jalview/analysis/AlignmentSorter.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Development Version 2.4.1)
   3  * Copyright (C) 2009 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 TODO:
  28  * this class retains some global states concerning sort-order which should be
  29  * made attributes for the caller's alignment visualization. TODO: refactor to
  30  * allow a subset of selected sequences to be sorted within the context of a
  31  * whole alignment. Sort method template is: SequenceI[] tobesorted, [ input
  32  * data mapping to each tobesorted element to use ], Alignment context of
  33  * tobesorted that are to be re-ordered, boolean sortinplace, [special data - ie
  34  * seuqence to be sorted w.r.t.]) sortinplace implies that the sorted vector
  35  * resulting from applying the operation to tobesorted should be mapped back to
  36  * the original positions in alignment. Otherwise, normal behaviour is to re
  37  * order alignment so that tobesorted is sorted and grouped together starting
  38  * from the first tobesorted position in the alignment. e.g. (a,tb2,b,tb1,c,tb3
  39  * becomes a,tb1,tb2,tb3,b,c)
  40  */
  41 public class AlignmentSorter
  42 {
  43   /**
  44    * todo: refactor searches to follow a basic pattern:
  45    * (search property, last search state, current sort direction)
  46    */
  47   static boolean sortIdAscending = true;
  48
  49   static int lastGroupHash = 0;
  50
  51   static boolean sortGroupAscending = true;
  52
  53   static AlignmentOrder lastOrder = null;
  54
  55   static boolean sortOrderAscending = true;
  56
  57   static NJTree lastTree = null;
  58
  59   static boolean sortTreeAscending = true;
  60
  61   /**
  62    * last Annotation Label used by sortByScore
  63    */
  64   private static String lastSortByScore;
  65   private static boolean sortByScoreAscending = true;
  66   /**
  67    * compact representation of last arguments to SortByFeatureScore
  68    */
  69   private static String lastSortByFeatureScore;
  70   private static boolean sortByFeatureScoreAscending = true;
  71
  72   private static boolean sortLengthAscending;
  73
  74   /**
  75    * Sort by Percentage Identity w.r.t. s
  76    *
  77    * @param align
  78    *                AlignmentI
  79    * @param s
  80    *                SequenceI
  81    * @param tosort
  82    *                sequences from align that are to be sorted.
  83    */
  84   public static void sortByPID(AlignmentI align, SequenceI s,
  85           SequenceI[] tosort)
  86   {
  87     sortByPID(align,s,tosort,0,-1);
  88   }
  89   /**
  90    * Sort by Percentage Identity w.r.t. s
  91    *
  92    * @param align
  93    *                AlignmentI
  94    * @param s
  95    *                SequenceI
  96    * @param tosort
  97    *                sequences from align that are to be sorted.
  98    * @param start   start column (0 for beginning
  99    * @param end
 100    */
 101   public static void sortByPID(AlignmentI align, SequenceI s,
 102           SequenceI[] tosort,int start, int end)
 103   {
 104     int nSeq = align.getHeight();
 105
 106     float[] scores = new float[nSeq];
 107     SequenceI[] seqs = new SequenceI[nSeq];
 108
 109     for (int i = 0; i < nSeq; i++)
 110     {
 111       scores[i] = Comparison.PID(align.getSequenceAt(i)
 112               .getSequenceAsString(), s.getSequenceAsString());
 113       seqs[i] = align.getSequenceAt(i);
 114     }
 115
 116     QuickSort.sort(scores, 0, scores.length - 1, seqs);
 117
 118     setReverseOrder(align, seqs);
 119   }
 120
 121   /**
 122    * Reverse the order of the sort
 123    *
 124    * @param align
 125    *                DOCUMENT ME!
 126    * @param seqs
 127    *                DOCUMENT ME!
 128    */
 129   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
 130   {
 131     int nSeq = seqs.length;
 132
 133     int len = 0;
 134
 135     if ((nSeq % 2) == 0)
 136     {
 137       len = nSeq / 2;
 138     }
 139     else
 140     {
 141       len = (nSeq + 1) / 2;
 142     }
 143
 144     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 145     for (int i = 0; i < len; i++)
 146     {
 147       // SequenceI tmp = seqs[i];
 148       align.getSequences().setElementAt(seqs[nSeq - i - 1], i);
 149       align.getSequences().setElementAt(seqs[i], nSeq - i - 1);
 150     }
 151   }
 152
 153   /**
 154    * Sets the Alignment object with the given sequences
 155    *
 156    * @param align
 157    *                Alignment object to be updated
 158    * @param tmp
 159    *                sequences as a vector
 160    */
 161   private static void setOrder(AlignmentI align, Vector tmp)
 162   {
 163     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 164   }
 165
 166   /**
 167    * Sets the Alignment object with the given sequences
 168    *
 169    * @param align
 170    *                DOCUMENT ME!
 171    * @param seqs
 172    *                sequences as an array
 173    */
 174   public static void setOrder(AlignmentI align, SequenceI[] seqs)
 175   {
 176     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 177     Vector algn = align.getSequences();
 178     Vector tmp = new Vector();
 179
 180     for (int i = 0; i < seqs.length; i++)
 181     {
 182       if (algn.contains(seqs[i]))
 183       {
 184         tmp.addElement(seqs[i]);
 185       }
 186     }
 187
 188     algn.removeAllElements();
 189     // User may have hidden seqs, then clicked undo or redo
 190     for (int i = 0; i < tmp.size(); i++)
 191     {
 192       algn.addElement(tmp.elementAt(i));
 193     }
 194
 195   }
 196
 197   /**
 198    * Sorts by ID. Numbers are sorted before letters.
 199    *
 200    * @param align
 201    *                The alignment object to sort
 202    */
 203   public static void sortByID(AlignmentI align)
 204   {
 205     int nSeq = align.getHeight();
 206
 207     String[] ids = new String[nSeq];
 208     SequenceI[] seqs = new SequenceI[nSeq];
 209
 210     for (int i = 0; i < nSeq; i++)
 211     {
 212       ids[i] = align.getSequenceAt(i).getName();
 213       seqs[i] = align.getSequenceAt(i);
 214     }
 215
 216     QuickSort.sort(ids, seqs);
 217
 218     if (sortIdAscending)
 219     {
 220       setReverseOrder(align, seqs);
 221     }
 222     else
 223     {
 224       setOrder(align, seqs);
 225     }
 226
 227     sortIdAscending = !sortIdAscending;
 228   }
 229   /**
 230    * Sorts by sequence length
 231    *
 232    * @param align
 233    *                The alignment object to sort
 234    */
 235   public static void sortByLength(AlignmentI align)
 236   {
 237     int nSeq = align.getHeight();
 238
 239     float[] length = new float[nSeq];
 240     SequenceI[] seqs = new SequenceI[nSeq];
 241
 242     for (int i = 0; i < nSeq; i++)
 243     {
 244       seqs[i] = align.getSequenceAt(i);
 245       length[i] = (float) (seqs[i].getEnd()-seqs[i].getStart());
 246     }
 247
 248     QuickSort.sort(length, seqs);
 249
 250     if (sortLengthAscending)
 251     {
 252       setReverseOrder(align, seqs);
 253     }
 254     else
 255     {
 256       setOrder(align, seqs);
 257     }
 258
 259     sortLengthAscending = !sortLengthAscending;
 260   }
 261
 262   /**
 263    * Sorts the alignment by size of group. <br>
 264    * Maintains the order of sequences in each group by order in given alignment
 265    * object.
 266    *
 267    * @param align
 268    *                sorts the given alignment object by group
 269    */
 270   public static void sortByGroup(AlignmentI align)
 271   {
 272     // MAINTAINS ORIGNAL SEQUENCE ORDER,
 273     // ORDERS BY GROUP SIZE
 274     Vector groups = new Vector();
 275
 276     if (groups.hashCode() != lastGroupHash)
 277     {
 278       sortGroupAscending = true;
 279       lastGroupHash = groups.hashCode();
 280     }
 281     else
 282     {
 283       sortGroupAscending = !sortGroupAscending;
 284     }
 285
 286     // SORTS GROUPS BY SIZE
 287     // ////////////////////
 288     for (int i = 0; i < align.getGroups().size(); i++)
 289     {
 290       SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);
 291
 292       for (int j = 0; j < groups.size(); j++)
 293       {
 294         SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);
 295
 296         if (sg.getSize() > sg2.getSize())
 297         {
 298           groups.insertElementAt(sg, j);
 299
 300           break;
 301         }
 302       }
 303
 304       if (!groups.contains(sg))
 305       {
 306         groups.addElement(sg);
 307       }
 308     }
 309
 310     // NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER
 311     // /////////////////////////////////////////////
 312     Vector seqs = new Vector();
 313
 314     for (int i = 0; i < groups.size(); i++)
 315     {
 316       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
 317       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);
 318
 319       for (int j = 0; j < orderedseqs.length; j++)
 320       {
 321         seqs.addElement(orderedseqs[j]);
 322       }
 323     }
 324
 325     if (sortGroupAscending)
 326     {
 327       setOrder(align, seqs);
 328     }
 329     else
 330     {
 331       setReverseOrder(align,
 332               vectorSubsetToArray(seqs, align.getSequences()));
 333     }
 334   }
 335
 336   /**
 337    * Converts Vector to array. java 1.18 does not have Vector.toArray()
 338    *
 339    * @param tmp
 340    *                Vector of SequenceI objects
 341    *
 342    * @return array of Sequence[]
 343    */
 344   private static SequenceI[] vectorToArray(Vector tmp)
 345   {
 346     SequenceI[] seqs = new SequenceI[tmp.size()];
 347
 348     for (int i = 0; i < tmp.size(); i++)
 349     {
 350       seqs[i] = (SequenceI) tmp.elementAt(i);
 351     }
 352
 353     return seqs;
 354   }
 355
 356   /**
 357    * DOCUMENT ME!
 358    *
 359    * @param tmp
 360    *                DOCUMENT ME!
 361    * @param mask
 362    *                DOCUMENT ME!
 363    *
 364    * @return DOCUMENT ME!
 365    */
 366   private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)
 367   {
 368     Vector seqs = new Vector();
 369     int i,idx;
 370     boolean[] tmask = new boolean[mask.size()];
 371
 372     for (i = 0; i < mask.size(); i++)
 373     {
 374       tmask[i] = true;
 375     }
 376
 377     for (i = 0; i < tmp.size(); i++)
 378     {
 379       Object sq = tmp.elementAt(i);
 380       idx = mask.indexOf(sq);
 381       if (idx>-1 && tmask[idx])
 382       {
 383         tmask[idx] = false;
 384         seqs.addElement(sq);
 385       }
 386     }
 387
 388     for (i = 0; i < tmask.length; i++)
 389     {
 390       if (tmask[i])
 391       {
 392         seqs.addElement(mask.elementAt(i));
 393       }
 394     }
 395
 396     return vectorToArray(seqs);
 397   }
 398
 399   /**
 400    * Sorts by a given AlignmentOrder object
 401    *
 402    * @param align
 403    *                Alignment to order
 404    * @param order
 405    *                specified order for alignment
 406    */
 407   public static void sortBy(AlignmentI align, AlignmentOrder order)
 408   {
 409     // Get an ordered vector of sequences which may also be present in align
 410     Vector tmp = order.getOrder();
 411
 412     if (lastOrder == order)
 413     {
 414       sortOrderAscending = !sortOrderAscending;
 415     }
 416     else
 417     {
 418       sortOrderAscending = true;
 419     }
 420
 421     if (sortOrderAscending)
 422     {
 423       setOrder(align, tmp);
 424     }
 425     else
 426     {
 427       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 428     }
 429   }
 430
 431   /**
 432    * DOCUMENT ME!
 433    *
 434    * @param align
 435    *                alignment to order
 436    * @param tree
 437    *                tree which has
 438    *
 439    * @return DOCUMENT ME!
 440    */
 441   private static Vector getOrderByTree(AlignmentI align, NJTree tree)
 442   {
 443     int nSeq = align.getHeight();
 444
 445     Vector tmp = new Vector();
 446
 447     tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
 448
 449     if (tmp.size() != nSeq)
 450     {
 451       // TODO: JBPNote - decide if this is always an error
 452       // (eg. not when a tree is associated to another alignment which has more
 453       // sequences)
 454       if (tmp.size() < nSeq)
 455       {
 456         addStrays(align, tmp);
 457       }
 458
 459       if (tmp.size() != nSeq)
 460       {
 461         System.err.println("ERROR: tmp.size()=" + tmp.size() + " != nseq="
 462                 + nSeq + " in getOrderByTree");
 463       }
 464     }
 465
 466     return tmp;
 467   }
 468
 469   /**
 470    * Sorts the alignment by a given tree
 471    *
 472    * @param align
 473    *                alignment to order
 474    * @param tree
 475    *                tree which has
 476    */
 477   public static void sortByTree(AlignmentI align, NJTree tree)
 478   {
 479     Vector tmp = getOrderByTree(align, tree);
 480
 481     // tmp should properly permute align with tree.
 482     if (lastTree != tree)
 483     {
 484       sortTreeAscending = true;
 485       lastTree = tree;
 486     }
 487     else
 488     {
 489       sortTreeAscending = !sortTreeAscending;
 490     }
 491
 492     if (sortTreeAscending)
 493     {
 494       setOrder(align, tmp);
 495     }
 496     else
 497     {
 498       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 499     }
 500   }
 501
 502   /**
 503    * DOCUMENT ME!
 504    *
 505    * @param align
 506    *                DOCUMENT ME!
 507    * @param seqs
 508    *                DOCUMENT ME!
 509    */
 510   private static void addStrays(AlignmentI align, Vector seqs)
 511   {
 512     int nSeq = align.getHeight();
 513
 514     for (int i = 0; i < nSeq; i++)
 515     {
 516       if (!seqs.contains(align.getSequenceAt(i)))
 517       {
 518         seqs.addElement(align.getSequenceAt(i));
 519       }
 520     }
 521
 522     if (nSeq != seqs.size())
 523     {
 524       System.err
 525               .println("ERROR: Size still not right even after addStrays");
 526     }
 527   }
 528
 529   /**
 530    * DOCUMENT ME!
 531    *
 532    * @param node
 533    *                DOCUMENT ME!
 534    * @param tmp
 535    *                DOCUMENT ME!
 536    * @param seqset
 537    *                DOCUMENT ME!
 538    *
 539    * @return DOCUMENT ME!
 540    */
 541   private static Vector _sortByTree(SequenceNode node, Vector tmp,
 542           Vector seqset)
 543   {
 544     if (node == null)
 545     {
 546       return tmp;
 547     }
 548
 549     SequenceNode left = (SequenceNode) node.left();
 550     SequenceNode right = (SequenceNode) node.right();
 551
 552     if ((left == null) && (right == null))
 553     {
 554       if (!node.isPlaceholder() && (node.element() != null))
 555       {
 556         if (node.element() instanceof SequenceI)
 557         {
 558           if (!tmp.contains(node.element()))
 559           {
 560             tmp.addElement((SequenceI) node.element());
 561           }
 562         }
 563       }
 564
 565       return tmp;
 566     }
 567     else
 568     {
 569       _sortByTree(left, tmp, seqset);
 570       _sortByTree(right, tmp, seqset);
 571     }
 572
 573     return tmp;
 574   }
 575
 576   // Ordering Objects
 577   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in
 578   // appropriate order
 579   //
 580
 581   /**
 582    * recover the order of sequences given by the safe numbering scheme introducd
 583    * SeqsetUtils.uniquify.
 584    */
 585   public static void recoverOrder(SequenceI[] alignment)
 586   {
 587     float[] ids = new float[alignment.length];
 588
 589     for (int i = 0; i < alignment.length; i++)
 590     {
 591       ids[i] = (new Float(alignment[i].getName().substring(8)))
 592               .floatValue();
 593     }
 594
 595     jalview.util.QuickSort.sort(ids, alignment);
 596   }
 597
 598   /**
 599    * Sort sequence in order of increasing score attribute for annotation with a
 600    * particular scoreLabel. Or reverse if same label was used previously
 601    *
 602    * @param scoreLabel
 603    *                exact label for sequence associated AlignmentAnnotation
 604    *                scores to use for sorting.
 605    * @param alignment
 606    *                sequences to be sorted
 607    */
 608   public static void sortByAnnotationScore(String scoreLabel,
 609           AlignmentI alignment)
 610   {
 611     SequenceI[] seqs = alignment.getSequencesArray();
 612     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
 613                                                     // presence
 614     int hasScores = 0; // number of scores present on set
 615     double[] scores = new double[seqs.length];
 616     double min = 0, max = 0;
 617     for (int i = 0; i < seqs.length; i++)
 618     {
 619       AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
 620       if (scoreAnn != null)
 621       {
 622         hasScores++;
 623         hasScore[i] = true;
 624         scores[i] = scoreAnn[0].getScore(); // take the first instance of this
 625                                             // score.
 626         if (hasScores == 1)
 627         {
 628           max = min = scores[i];
 629         }
 630         else
 631         {
 632           if (max < scores[i])
 633           {
 634             max = scores[i];
 635           }
 636           if (min > scores[i])
 637           {
 638             min = scores[i];
 639           }
 640         }
 641       }
 642       else
 643       {
 644         hasScore[i] = false;
 645       }
 646     }
 647     if (hasScores == 0)
 648     {
 649       return; // do nothing - no scores present to sort by.
 650     }
 651     if (hasScores < seqs.length)
 652     {
 653       for (int i = 0; i < seqs.length; i++)
 654       {
 655         if (!hasScore[i])
 656         {
 657           scores[i] = (max + i+1.0);
 658         }
 659       }
 660     }
 661
 662     jalview.util.QuickSort.sort(scores, seqs);
 663     if (lastSortByScore != scoreLabel)
 664     {
 665       lastSortByScore = scoreLabel;
 666       setOrder(alignment, seqs);
 667     }
 668     else
 669     {
 670       setReverseOrder(alignment, seqs);
 671     }
 672   }
 673   /**
 674    * types of feature ordering:
 675    * Sort by score : average score - or total score - over all features in region
 676    * Sort by feature label text: (or if null - feature type text) - numerical or alphabetical
 677    * Sort by feature density: based on counts - ignoring individual text or scores for each feature
 678    */
 679   public static String FEATURE_SCORE="average_score";
 680   public static String FEATURE_LABEL="text";
 681   public static String FEATURE_DENSITY="density";
 682
 683   /**
 684    * sort the alignment using the features on each sequence found between start and stop with the given featureLabel (and optional group qualifier)
 685    * @param featureLabel (may not be null)
 686    * @param groupLabel (may be null)
 687    * @param start (-1 to include non-positional features)
 688    * @param stop (-1 to only sort on non-positional features)
 689    * @param alignment - aligned sequences containing features
 690    * @param method - one of the string constants FEATURE_SCORE, FEATURE_LABEL, FEATURE_DENSITY
 691    */
 692   public static void sortByFeature(String featureLabel, String groupLabel, int start, int stop,
 693           AlignmentI alignment, String method)
 694   {
 695     sortByFeature(featureLabel==null ? null : new String[] {featureLabel},
 696             groupLabel==null ? null : new String[] {groupLabel}, start, stop, alignment, method);
 697   }
 698   private static boolean containsIgnoreCase(final String lab, final String[] labs)
 699   {
 700     if (labs==null)
 701     {
 702       return true;
 703     }
 704     if (lab==null)
 705     {
 706       return false;
 707     }
 708     for (int q=0;q<labs.length;q++)
 709     {
 710       if (labs[q]!=null && lab.equalsIgnoreCase(labs[q]))
 711       {
 712         return true;
 713       }
 714     }
 715     return false;
 716   }
 717   public static void sortByFeature(String[] featureLabels, String[] groupLabels, int start, int stop,
 718           AlignmentI alignment, String method)
 719   {
 720     if (method!=FEATURE_SCORE && method!=FEATURE_LABEL && method!=FEATURE_DENSITY)
 721     {
 722       throw new Error("Implementation Error - sortByFeature method must be one of FEATURE_SCORE, FEATURE_LABEL or FEATURE_DENSITY.");
 723     }
 724     boolean ignoreScore=method!=FEATURE_SCORE;
 725     StringBuffer scoreLabel = new StringBuffer();
 726     scoreLabel.append(start+stop+method);
 727     // This doesn't quite work yet - we'd like to have a canonical ordering that can be preserved from call to call
 728     for (int i=0;featureLabels!=null && i<featureLabels.length; i++)
 729     {
 730       scoreLabel.append(featureLabels[i]==null ? "null" : featureLabels[i]);
 731     }
 732     for (int i=0;groupLabels!=null && i<groupLabels.length; i++)
 733     {
 734       scoreLabel.append(groupLabels[i]==null ? "null" : groupLabels[i]);
 735     }
 736     SequenceI[] seqs = alignment.getSequencesArray();
 737
 738     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
 739                                                     // presence
 740     int hasScores = 0; // number of scores present on set
 741     double[] scores = new double[seqs.length];
 742     int[] seqScores = new int[seqs.length];
 743     Object[] feats = new Object[seqs.length];
 744     double min = 0, max = 0;
 745     for (int i = 0; i < seqs.length; i++)
 746     {
 747       SequenceFeature[] sf = seqs[i].getSequenceFeatures();
 748       if (sf==null && seqs[i].getDatasetSequence()!=null)
 749       {
 750         sf = seqs[i].getDatasetSequence().getSequenceFeatures();
 751       }
 752       if (sf==null)
 753       {
 754         sf = new SequenceFeature[0];
 755       } else {
 756         SequenceFeature[] tmp = new SequenceFeature[sf.length];
 757         for (int s=0; s<tmp.length;s++)
 758         {
 759           tmp[s] = sf[s];
 760         }
 761         sf = tmp;
 762       }
 763       int sstart = (start==-1) ? start : seqs[i].findPosition(start);
 764       int sstop = (stop==-1) ? stop : seqs[i].findPosition(stop);
 765       seqScores[i]=0;
 766       scores[i]=0.0;
 767       int n=sf.length;
 768       for (int f=0;f<sf.length;f++)
 769       {
 770         // filter for selection criteria
 771         if (
 772         // ignore features outwith alignment start-stop positions.
 773         (sf[f].end < sstart || sf[f].begin > sstop)
 774                 ||
 775                 // or ignore based on selection criteria
 776                 (featureLabels != null && !AlignmentSorter.containsIgnoreCase(sf[f].type, featureLabels))
 777                 || (groupLabels != null
 778                         // problem here: we cannot eliminate null feature group features
 779                         && (sf[f].getFeatureGroup() != null
 780                                 && !AlignmentSorter.containsIgnoreCase(sf[f].getFeatureGroup(), groupLabels))))
 781         {
 782           // forget about this feature
 783           sf[f] = null;
 784           n--;
 785         } else {
 786           // or, also take a look at the scores if necessary.
 787           if (!ignoreScore && sf[f].getScore()!=Float.NaN)
 788           {
 789             if (seqScores[i]==0)
 790             {
 791               hasScores++;
 792             }
 793             seqScores[i]++;
 794             hasScore[i] = true;
 795             scores[i] += sf[f].getScore(); // take the first instance of this
 796                                             // score.
 797           }
 798         }
 799       }
 800       SequenceFeature[] fs;
 801       feats[i] = fs = new SequenceFeature[n];
 802       if (n>0)
 803       {
 804         n=0;
 805         for (int f=0;f<sf.length;f++)
 806         {
 807           if (sf[f]!=null)
 808           {
 809             ((SequenceFeature[]) feats[i])[n++] = sf[f];
 810           }
 811         }
 812         if (method==FEATURE_LABEL)
 813         {
 814           // order the labels by alphabet
 815           String[] labs = new String[fs.length];
 816           for (int l=0;l<labs.length; l++)
 817           {
 818             labs[l] = (fs[l].getDescription()!=null ? fs[l].getDescription() : fs[l].getType());
 819           }
 820           jalview.util.QuickSort.sort(labs, ((Object[]) feats[i]));
 821         }
 822       }
 823       if (hasScore[i])
 824       {
 825         // compute average score
 826         scores[i]/=seqScores[i];
 827         // update the score bounds.
 828         if (hasScores == 1)
 829         {
 830           max = min = scores[i];
 831         }
 832         else
 833         {
 834           if (max < scores[i])
 835           {
 836             max = scores[i];
 837           }
 838           if (min > scores[i])
 839           {
 840             min = scores[i];
 841           }
 842         }
 843       }
 844     }
 845
 846     if (method==FEATURE_SCORE)
 847     {
 848       if (hasScores == 0)
 849     {
 850       return; // do nothing - no scores present to sort by.
 851     }
 852     // pad score matrix
 853     if (hasScores < seqs.length)
 854     {
 855       for (int i = 0; i < seqs.length; i++)
 856       {
 857         if (!hasScore[i])
 858         {
 859           scores[i] = (max + 1+i);
 860         } else {
 861           int nf=(feats[i]==null) ? 0 :((SequenceFeature[]) feats[i]).length;
 862           // System.err.println("Sorting on Score: seq "+seqs[i].getName()+ " Feats: "+nf+" Score : "+scores[i]);
 863         }
 864       }
 865     }
 866
 867     jalview.util.QuickSort.sort(scores, seqs);
 868     }
 869     else
 870       if (method==FEATURE_DENSITY)
 871       {
 872
 873         // break ties between equivalent numbers for adjacent sequences by adding 1/Nseq*i on the original order
 874         double fr = 0.9/(1.0*seqs.length);
 875         for (int i=0;i<seqs.length; i++)
 876         {
 877           double nf;
 878           scores[i] = (0.05+fr*i)+(nf=((feats[i]==null) ? 0.0 :1.0*((SequenceFeature[]) feats[i]).length));
 879           // System.err.println("Sorting on Density: seq "+seqs[i].getName()+ " Feats: "+nf+" Score : "+scores[i]);
 880         }
 881         jalview.util.QuickSort.sort(scores, seqs);
 882       }
 883       else {
 884         if (method==FEATURE_LABEL)
 885         {
 886           throw new Error("Not yet implemented.");
 887         }
 888       }
 889     if (lastSortByFeatureScore ==null || !scoreLabel.toString().equals(lastSortByFeatureScore))
 890     {
 891       sortByFeatureScoreAscending = true;
 892     } else {
 893       sortByFeatureScoreAscending = !sortByFeatureScoreAscending;
 894     }
 895     if (sortByFeatureScoreAscending) {
 896       setOrder(alignment, seqs);
 897     }
 898     else
 899     {
 900       setReverseOrder(alignment, seqs);
 901     }
 902     lastSortByFeatureScore = scoreLabel.toString();
 903   }
 904
 905 }