src/jalview/analysis/AlignmentSorter.java

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