src/jalview/analysis/AlignmentSorter.java

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