src/jalview/analysis/AlignmentSorter.java

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