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