src/jalview/analysis/AlignmentSorter.java

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