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