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.bin.Jalview;
  26 import jalview.datamodel.AlignmentAnnotation;
  27 import jalview.datamodel.AlignmentI;
  28 import jalview.datamodel.AlignmentOrder;
  29 import jalview.datamodel.SequenceFeature;
  30 import jalview.datamodel.SequenceGroup;
  31 import jalview.datamodel.SequenceI;
  32 import jalview.datamodel.SequenceNode;
  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   public static AlignmentSorter getInstance()
  71   {
  72     Jalview j = Jalview.getInstance();
  73     return (j.alignmentSorter == null
  74             ? j.alignmentSorter = new AlignmentSorter()
  75             : j.alignmentSorter);
  76   }
  77
  78   /*
  79    * todo: refactor searches to follow a basic pattern: (search property, last
  80    * search state, current sort direction)
  81    */
  82   boolean sortIdAscending = true;
  83
  84   int lastGroupHash = 0;
  85
  86   boolean sortGroupAscending = true;
  87
  88   AlignmentOrder lastOrder = null;
  89
  90   boolean sortOrderAscending = true;
  91
  92   TreeModel lastTree = null;
  93
  94   boolean sortTreeAscending = true;
  95
  96
  97   /**
  98    * last Annotation Label used for sort by Annotation score
  99    */
 100   private String lastSortByAnnotation;
 101
 102   /**
 103    * string hash of last arguments to sortByFeature (sort order toggles if this
 104    * is unchanged between sorts)
 105    */
 106   private String sortByFeatureCriteria;
 107
 108   private boolean sortByFeatureAscending = true;
 109
 110   private boolean sortLengthAscending;
 111
 112   /**
 113    * Sorts sequences in the alignment by Percentage Identity with the given
 114    * reference sequence, sorting the highest identity to the top
 115    *
 116    * @param align
 117    *          AlignmentI
 118    * @param s
 119    *          SequenceI
 120    * @param end
 121    */
 122   public static void sortByPID(AlignmentI align, SequenceI s)
 123   {
 124     int nSeq = align.getHeight();
 125
 126     float[] scores = new float[nSeq];
 127     SequenceI[] seqs = new SequenceI[nSeq];
 128     String refSeq = s.getSequenceAsString();
 129
 130     SimilarityParams pidParams = new SimilarityParams(true, true, true,
 131             true);
 132     for (int i = 0; i < nSeq; i++)
 133     {
 134       scores[i] = (float) PIDModel.computePID(
 135               align.getSequenceAt(i).getSequenceAsString(), refSeq,
 136               pidParams);
 137       seqs[i] = align.getSequenceAt(i);
 138     }
 139
 140     QuickSort.sort(scores, seqs);
 141
 142     setReverseOrder(align, seqs);
 143   }
 144
 145   /**
 146    * Reverse the order of the sort
 147    *
 148    * @param align
 149    *          DOCUMENT ME!
 150    * @param seqs
 151    *          DOCUMENT ME!
 152    */
 153   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
 154   {
 155     int nSeq = seqs.length;
 156
 157     int len = 0;
 158
 159     if ((nSeq % 2) == 0)
 160     {
 161       len = nSeq / 2;
 162     }
 163     else
 164     {
 165       len = (nSeq + 1) / 2;
 166     }
 167
 168     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 169     List<SequenceI> asq = align.getSequences();
 170     synchronized (asq)
 171     {
 172       for (int i = 0; i < len; i++)
 173       {
 174         // SequenceI tmp = seqs[i];
 175         asq.set(i, seqs[nSeq - i - 1]);
 176         asq.set(nSeq - i - 1, seqs[i]);
 177       }
 178     }
 179   }
 180
 181   /**
 182    * Sets the Alignment object with the given sequences
 183    *
 184    * @param align
 185    *          Alignment object to be updated
 186    * @param tmp
 187    *          sequences as a vector
 188    */
 189   private static void setOrder(AlignmentI align, List<SequenceI> tmp)
 190   {
 191     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 192   }
 193
 194   /**
 195    * Sets the Alignment object with the given sequences
 196    *
 197    * @param align
 198    *          DOCUMENT ME!
 199    * @param seqs
 200    *          sequences as an array
 201    */
 202   public static void setOrder(AlignmentI align, SequenceI[] seqs)
 203   {
 204     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 205     List<SequenceI> algn = align.getSequences();
 206     synchronized (algn)
 207     {
 208       List<SequenceI> tmp = new ArrayList<>();
 209
 210       for (int i = 0; i < seqs.length; i++)
 211       {
 212         if (algn.contains(seqs[i]))
 213         {
 214           tmp.add(seqs[i]);
 215         }
 216       }
 217
 218       algn.clear();
 219       // User may have hidden seqs, then clicked undo or redo
 220       for (int i = 0; i < tmp.size(); i++)
 221       {
 222         algn.add(tmp.get(i));
 223       }
 224     }
 225   }
 226
 227   /**
 228    * Sorts by ID. Numbers are sorted before letters.
 229    *
 230    * @param align
 231    *          The alignment object to sort
 232    */
 233   public static void sortByID(AlignmentI align)
 234   {
 235     int nSeq = align.getHeight();
 236
 237     String[] ids = new String[nSeq];
 238     SequenceI[] seqs = new SequenceI[nSeq];
 239
 240     for (int i = 0; i < nSeq; i++)
 241     {
 242       ids[i] = align.getSequenceAt(i).getName();
 243       seqs[i] = align.getSequenceAt(i);
 244     }
 245
 246     QuickSort.sort(ids, seqs);
 247
 248     AlignmentSorter as = getInstance();
 249     if (as.sortIdAscending)
 250     {
 251       setReverseOrder(align, seqs);
 252     }
 253     else
 254     {
 255       setOrder(align, seqs);
 256     }
 257
 258     as.sortIdAscending = !as.sortIdAscending;
 259   }
 260
 261   /**
 262    * Sorts by sequence length
 263    *
 264    * @param align
 265    *          The alignment object to sort
 266    */
 267   public static void sortByLength(AlignmentI align)
 268   {
 269     int nSeq = align.getHeight();
 270
 271     float[] length = new float[nSeq];
 272     SequenceI[] seqs = new SequenceI[nSeq];
 273
 274     for (int i = 0; i < nSeq; i++)
 275     {
 276       seqs[i] = align.getSequenceAt(i);
 277       length[i] = (seqs[i].getEnd() - seqs[i].getStart());
 278     }
 279
 280     QuickSort.sort(length, seqs);
 281
 282     AlignmentSorter as = getInstance();
 283
 284     if (as.sortLengthAscending)
 285     {
 286       setReverseOrder(align, seqs);
 287     }
 288     else
 289     {
 290       setOrder(align, seqs);
 291     }
 292
 293     as.sortLengthAscending = !as.sortLengthAscending;
 294   }
 295
 296   /**
 297    * Sorts the alignment by size of group. <br>
 298    * Maintains the order of sequences in each group by order in given alignment
 299    * object.
 300    *
 301    * @param align
 302    *          sorts the given alignment object by group
 303    */
 304   public static void sortByGroup(AlignmentI align)
 305   {
 306     // MAINTAINS ORIGNAL SEQUENCE ORDER,
 307     // ORDERS BY GROUP SIZE
 308     List<SequenceGroup> groups = new ArrayList<>();
 309
 310     AlignmentSorter as = getInstance();
 311
 312     if (groups.hashCode() != as.lastGroupHash)
 313     {
 314       as.sortGroupAscending = true;
 315       as.lastGroupHash = groups.hashCode();
 316     }
 317     else
 318     {
 319       as.sortGroupAscending = !as.sortGroupAscending;
 320     }
 321
 322     // SORTS GROUPS BY SIZE
 323     // ////////////////////
 324     for (SequenceGroup sg : align.getGroups())
 325     {
 326       for (int j = 0; j < groups.size(); j++)
 327       {
 328         SequenceGroup sg2 = groups.get(j);
 329
 330         if (sg.getSize() > sg2.getSize())
 331         {
 332           groups.add(j, sg);
 333
 334           break;
 335         }
 336       }
 337
 338       if (!groups.contains(sg))
 339       {
 340         groups.add(sg);
 341       }
 342     }
 343
 344     // NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER
 345     // /////////////////////////////////////////////
 346     List<SequenceI> seqs = new ArrayList<>();
 347
 348     for (int i = 0; i < groups.size(); i++)
 349     {
 350       SequenceGroup sg = groups.get(i);
 351       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);
 352
 353       for (int j = 0; j < orderedseqs.length; j++)
 354       {
 355         seqs.add(orderedseqs[j]);
 356       }
 357     }
 358
 359     if (as.sortGroupAscending)
 360     {
 361       setOrder(align, seqs);
 362     }
 363     else
 364     {
 365       setReverseOrder(align,
 366               vectorSubsetToArray(seqs, align.getSequences()));
 367     }
 368   }
 369
 370   /**
 371    * Select sequences in order from tmp that is present in mask, and any
 372    * remaining sequences in mask not in tmp
 373    *
 374    * @param tmp
 375    *          thread safe collection of sequences
 376    * @param mask
 377    *          thread safe collection of sequences
 378    *
 379    * @return intersect(tmp,mask)+intersect(complement(tmp),mask)
 380    */
 381   private static SequenceI[] vectorSubsetToArray(List<SequenceI> tmp,
 382           List<SequenceI> mask)
 383   {
 384     // or?
 385     // tmp2 = tmp.retainAll(mask);
 386     // return tmp2.addAll(mask.removeAll(tmp2))
 387
 388     ArrayList<SequenceI> seqs = new ArrayList<>();
 389     int i, idx;
 390     boolean[] tmask = new boolean[mask.size()];
 391
 392     for (i = 0; i < mask.size(); i++)
 393     {
 394       tmask[i] = true;
 395     }
 396
 397     for (i = 0; i < tmp.size(); i++)
 398     {
 399       SequenceI sq = tmp.get(i);
 400       idx = mask.indexOf(sq);
 401       if (idx > -1 && tmask[idx])
 402       {
 403         tmask[idx] = false;
 404         seqs.add(sq);
 405       }
 406     }
 407
 408     for (i = 0; i < tmask.length; i++)
 409     {
 410       if (tmask[i])
 411       {
 412         seqs.add(mask.get(i));
 413       }
 414     }
 415
 416     return seqs.toArray(new SequenceI[seqs.size()]);
 417   }
 418
 419   /**
 420    * Sorts by a given AlignmentOrder object
 421    *
 422    * @param align
 423    *          Alignment to order
 424    * @param order
 425    *          specified order for alignment
 426    */
 427   public static void sortBy(AlignmentI align, AlignmentOrder order)
 428   {
 429     // Get an ordered vector of sequences which may also be present in align
 430     List<SequenceI> tmp = order.getOrder();
 431
 432     AlignmentSorter as = getInstance();
 433
 434     if (as.lastOrder == order)
 435     {
 436       as.sortOrderAscending = !as.sortOrderAscending;
 437     }
 438     else
 439     {
 440       as.sortOrderAscending = true;
 441     }
 442
 443     if (as.sortOrderAscending)
 444     {
 445       setOrder(align, tmp);
 446     }
 447     else
 448     {
 449       setReverseOrder(align,
 450               vectorSubsetToArray(tmp, align.getSequences()));
 451     }
 452   }
 453
 454   /**
 455    * DOCUMENT ME!
 456    *
 457    * @param align
 458    *          alignment to order
 459    * @param tree
 460    *          tree which has
 461    *
 462    * @return DOCUMENT ME!
 463    */
 464   private static List<SequenceI> getOrderByTree(AlignmentI align,
 465           TreeModel tree)
 466   {
 467     int nSeq = align.getHeight();
 468
 469     List<SequenceI> tmp = new ArrayList<>();
 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.println("WARNING: tmp.size()=" + tmp.size() + " != nseq="
 486                 + nSeq
 487                 + " in getOrderByTree - tree contains sequences not in alignment");
 488       }
 489     }
 490
 491     return tmp;
 492   }
 493
 494   /**
 495    * Sorts the alignment by a given tree
 496    *
 497    * @param align
 498    *          alignment to order
 499    * @param tree
 500    *          tree which has
 501    */
 502   public static void sortByTree(AlignmentI align, TreeModel tree)
 503   {
 504     List<SequenceI> tmp = getOrderByTree(align, tree);
 505
 506     AlignmentSorter as = getInstance();
 507
 508     // tmp should properly permute align with tree.
 509     if (as.lastTree != tree)
 510     {
 511       as.sortTreeAscending = true;
 512       as.lastTree = tree;
 513     }
 514     else
 515     {
 516       as.sortTreeAscending = !as.sortTreeAscending;
 517     }
 518
 519     if (as.sortTreeAscending)
 520     {
 521       setOrder(align, tmp);
 522     }
 523     else
 524     {
 525       setReverseOrder(align,
 526               vectorSubsetToArray(tmp, align.getSequences()));
 527     }
 528   }
 529
 530   /**
 531    * DOCUMENT ME!
 532    *
 533    * @param align
 534    *          DOCUMENT ME!
 535    * @param tmp
 536    *          DOCUMENT ME!
 537    */
 538   private static void addStrays(AlignmentI align, List<SequenceI> tmp)
 539   {
 540     int nSeq = align.getHeight();
 541
 542     for (int i = 0; i < nSeq; i++)
 543     {
 544       if (!tmp.contains(align.getSequenceAt(i)))
 545       {
 546         tmp.add(align.getSequenceAt(i));
 547       }
 548     }
 549
 550     if (nSeq != tmp.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 List<SequenceI> _sortByTree(SequenceNode node,
 570           List<SequenceI> tmp, 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.add((SequenceI) 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
 694     AlignmentSorter as = getInstance();
 695
 696     if (as.lastSortByAnnotation != scoreLabel)
 697     {
 698       as.lastSortByAnnotation = scoreLabel;
 699       setOrder(alignment, seqs);
 700     }
 701     else
 702     {
 703       setReverseOrder(alignment, seqs);
 704     }
 705   }
 706
 707   /**
 708    * Sort sequences by feature score or density, optionally restricted by
 709    * feature types, feature groups, or alignment start/end positions.
 710    * <p>
 711    * If the sort is repeated for the same combination of types and groups, sort
 712    * order is reversed.
 713    *
 714    * @param featureTypes
 715    *          a list of feature types to include (or null for all)
 716    * @param groups
 717    *          a list of feature groups to include (or null for all)
 718    * @param startCol
 719    *          start column position to include (base zero)
 720    * @param endCol
 721    *          end column position to include (base zero)
 722    * @param alignment
 723    *          the alignment to be sorted
 724    * @param method
 725    *          either "average_score" or "density" ("text" not yet implemented)
 726    */
 727   public static void sortByFeature(List<String> featureTypes,
 728           List<String> groups, final int startCol, final int endCol,
 729           AlignmentI alignment, String method)
 730   {
 731     if (method != FEATURE_SCORE && method != FEATURE_LABEL
 732             && method != FEATURE_DENSITY)
 733     {
 734       String msg = String
 735               .format("Implementation Error - sortByFeature method must be either '%s' or '%s'",
 736                       FEATURE_SCORE, FEATURE_DENSITY);
 737       System.err.println(msg);
 738       return;
 739     }
 740
 741     flipFeatureSortIfUnchanged(method, featureTypes, groups, startCol, endCol);
 742
 743     SequenceI[] seqs = alignment.getSequencesArray();
 744
 745     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
 746     // presence
 747     int hasScores = 0; // number of scores present on set
 748     double[] scores = new double[seqs.length];
 749     int[] seqScores = new int[seqs.length];
 750     Object[][] feats = new Object[seqs.length][];
 751     double min = 0d;
 752     double max = 0d;
 753
 754     for (int i = 0; i < seqs.length; i++)
 755     {
 756       /*
 757        * get sequence residues overlapping column region
 758        * and features for residue positions and specified types
 759        */
 760       String[] types = featureTypes == null ? null : featureTypes
 761               .toArray(new String[featureTypes.size()]);
 762       List<SequenceFeature> sfs = seqs[i].findFeatures(startCol + 1,
 763               endCol + 1, types);
 764
 765       seqScores[i] = 0;
 766       scores[i] = 0.0;
 767
 768       Iterator<SequenceFeature> it = sfs.listIterator();
 769       while (it.hasNext())
 770       {
 771         SequenceFeature sf = it.next();
 772
 773         /*
 774          * accept all features with null or empty group, otherwise
 775          * check group is one of the currently visible groups
 776          */
 777         String featureGroup = sf.getFeatureGroup();
 778         if (groups != null && featureGroup != null
 779                 && !"".equals(featureGroup)
 780                 && !groups.contains(featureGroup))
 781         {
 782           it.remove();
 783         }
 784         else
 785         {
 786           float score = sf.getScore();
 787           if (FEATURE_SCORE.equals(method) && !Float.isNaN(score))
 788           {
 789             if (seqScores[i] == 0)
 790             {
 791               hasScores++;
 792             }
 793             seqScores[i]++;
 794             hasScore[i] = true;
 795             scores[i] += score;
 796             // take the first instance of this score // ??
 797           }
 798         }
 799       }
 800
 801       feats[i] = sfs.toArray(new SequenceFeature[sfs.size()]);
 802       if (!sfs.isEmpty())
 803       {
 804         if (method == FEATURE_LABEL)
 805         {
 806           // order the labels by alphabet (not yet implemented)
 807           String[] labs = new String[sfs.size()];
 808           for (int l = 0; l < sfs.size(); l++)
 809           {
 810             SequenceFeature sf = sfs.get(l);
 811             String description = sf.getDescription();
 812             labs[l] = (description != null ? description : sf.getType());
 813           }
 814           QuickSort.sort(labs, feats[i]);
 815         }
 816       }
 817       if (hasScore[i])
 818       {
 819         // compute average score
 820         scores[i] /= seqScores[i];
 821         // update the score bounds.
 822         if (hasScores == 1)
 823         {
 824           min = scores[i];
 825           max = min;
 826         }
 827         else
 828         {
 829           max = Math.max(max, scores[i]);
 830           min = Math.min(min, scores[i]);
 831         }
 832       }
 833     }
 834
 835     boolean doSort = false;
 836
 837     if (FEATURE_SCORE.equals(method))
 838     {
 839       if (hasScores == 0)
 840       {
 841         return; // do nothing - no scores present to sort by.
 842       }
 843       // pad score matrix
 844       if (hasScores < seqs.length)
 845       {
 846         for (int i = 0; i < seqs.length; i++)
 847         {
 848           if (!hasScore[i])
 849           {
 850             scores[i] = (max + 1 + i);
 851           }
 852           else
 853           {
 854             // int nf = (feats[i] == null) ? 0
 855             // : ((SequenceFeature[]) feats[i]).length;
 856             // // System.err.println("Sorting on Score: seq " +
 857             // seqs[i].getName()
 858             // + " Feats: " + nf + " Score : " + scores[i]);
 859           }
 860         }
 861       }
 862       doSort = true;
 863     }
 864     else if (FEATURE_DENSITY.equals(method))
 865     {
 866       for (int i = 0; i < seqs.length; i++)
 867       {
 868         int featureCount = feats[i] == null ? 0
 869                 : ((SequenceFeature[]) feats[i]).length;
 870         scores[i] = featureCount;
 871         // System.err.println("Sorting on Density: seq "+seqs[i].getName()+
 872         // " Feats: "+featureCount+" Score : "+scores[i]);
 873       }
 874       doSort = true;
 875     }
 876     if (doSort)
 877     {
 878       QuickSort.sortByDouble(scores, seqs, getInstance().sortByFeatureAscending);
 879     }
 880     setOrder(alignment, seqs);
 881   }
 882
 883   /**
 884    * Builds a string hash of criteria for sorting, and if unchanged from last
 885    * time, reverse the sort order
 886    *
 887    * @param method
 888    * @param featureTypes
 889    * @param groups
 890    * @param startCol
 891    * @param endCol
 892    */
 893   protected static void flipFeatureSortIfUnchanged(String method,
 894           List<String> featureTypes, List<String> groups,
 895           final int startCol, final int endCol)
 896   {
 897     StringBuilder sb = new StringBuilder(64);
 898     sb.append(startCol).append(method).append(endCol);
 899     if (featureTypes != null)
 900     {
 901       Collections.sort(featureTypes);
 902       sb.append(featureTypes.toString());
 903     }
 904     if (groups != null)
 905     {
 906       Collections.sort(groups);
 907       sb.append(groups.toString());
 908     }
 909     String scoreCriteria = sb.toString();
 910
 911     /*
 912      * if resorting on the same criteria, toggle sort order
 913      */
 914     AlignmentSorter as = getInstance();
 915     if (as.sortByFeatureCriteria == null
 916             || !scoreCriteria.equals(as.sortByFeatureCriteria))
 917     {
 918       as.sortByFeatureAscending = true;
 919     }
 920     else
 921     {
 922       as.sortByFeatureAscending = !as.sortByFeatureAscending;
 923     }
 924     as.sortByFeatureCriteria = scoreCriteria;
 925   }
 926
 927 }