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