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