src/jalview/analysis/AlignmentSorter.java

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