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