src/jalview/analysis/AlignmentSorter.java

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