src/jalview/analysis/AlignmentSorter.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.4)
   3  * Copyright (C) 2008 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19 package jalview.analysis;
  20
  21 import java.util.*;
  22
  23 import jalview.datamodel.*;
  24 import jalview.util.*;
  25
  26 /**
  27  * Routines for manipulating the order of a multiple sequence alignment TODO:
  28  * this class retains some global states concerning sort-order which should be
  29  * made attributes for the caller's alignment visualization. TODO: refactor to
  30  * allow a subset of selected sequences to be sorted within the context of a
  31  * whole alignment. Sort method template is: SequenceI[] tobesorted, [ input
  32  * data mapping to each tobesorted element to use ], Alignment context of
  33  * tobesorted that are to be re-ordered, boolean sortinplace, [special data - ie
  34  * seuqence to be sorted w.r.t.]) sortinplace implies that the sorted vector
  35  * resulting from applying the operation to tobesorted should be mapped back to
  36  * the original positions in alignment. Otherwise, normal behaviour is to re
  37  * order alignment so that tobesorted is sorted and grouped together starting
  38  * from the first tobesorted position in the alignment. e.g. (a,tb2,b,tb1,c,tb3
  39  * becomes a,tb1,tb2,tb3,b,c)
  40  */
  41 public class AlignmentSorter
  42 {
  43   static boolean sortIdAscending = true;
  44
  45   static int lastGroupHash = 0;
  46
  47   static boolean sortGroupAscending = true;
  48
  49   static AlignmentOrder lastOrder = null;
  50
  51   static boolean sortOrderAscending = true;
  52
  53   static NJTree lastTree = null;
  54
  55   static boolean sortTreeAscending = true;
  56
  57   /**
  58    * last Annotation Label used by sortByScore
  59    */
  60   private static String lastSortByScore;
  61
  62   /**
  63    * compact representation of last arguments to SortByFeatureScore
  64    */
  65   private static String lastSortByFeatureScore;
  66
  67   /**
  68    * Sort by Percentage Identity w.r.t. s
  69    *
  70    * @param align
  71    *                AlignmentI
  72    * @param s
  73    *                SequenceI
  74    * @param tosort
  75    *                sequences from align that are to be sorted.
  76    */
  77   public static void sortByPID(AlignmentI align, SequenceI s,
  78           SequenceI[] tosort)
  79   {
  80     int nSeq = align.getHeight();
  81
  82     float[] scores = new float[nSeq];
  83     SequenceI[] seqs = new SequenceI[nSeq];
  84
  85     for (int i = 0; i < nSeq; i++)
  86     {
  87       scores[i] = Comparison.PID(align.getSequenceAt(i)
  88               .getSequenceAsString(), s.getSequenceAsString());
  89       seqs[i] = align.getSequenceAt(i);
  90     }
  91
  92     QuickSort.sort(scores, 0, scores.length - 1, seqs);
  93
  94     setReverseOrder(align, seqs);
  95   }
  96
  97   /**
  98    * Reverse the order of the sort
  99    *
 100    * @param align
 101    *                DOCUMENT ME!
 102    * @param seqs
 103    *                DOCUMENT ME!
 104    */
 105   private static void setReverseOrder(AlignmentI align, SequenceI[] seqs)
 106   {
 107     int nSeq = seqs.length;
 108
 109     int len = 0;
 110
 111     if ((nSeq % 2) == 0)
 112     {
 113       len = nSeq / 2;
 114     }
 115     else
 116     {
 117       len = (nSeq + 1) / 2;
 118     }
 119
 120     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 121     for (int i = 0; i < len; i++)
 122     {
 123       // SequenceI tmp = seqs[i];
 124       align.getSequences().setElementAt(seqs[nSeq - i - 1], i);
 125       align.getSequences().setElementAt(seqs[i], nSeq - i - 1);
 126     }
 127   }
 128
 129   /**
 130    * Sets the Alignment object with the given sequences
 131    *
 132    * @param align
 133    *                Alignment object to be updated
 134    * @param tmp
 135    *                sequences as a vector
 136    */
 137   private static void setOrder(AlignmentI align, Vector tmp)
 138   {
 139     setOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 140   }
 141
 142   /**
 143    * Sets the Alignment object with the given sequences
 144    *
 145    * @param align
 146    *                DOCUMENT ME!
 147    * @param seqs
 148    *                sequences as an array
 149    */
 150   public static void setOrder(AlignmentI align, SequenceI[] seqs)
 151   {
 152     // NOTE: DO NOT USE align.setSequenceAt() here - it will NOT work
 153     Vector algn = align.getSequences();
 154     Vector tmp = new Vector();
 155
 156     for (int i = 0; i < seqs.length; i++)
 157     {
 158       if (algn.contains(seqs[i]))
 159       {
 160         tmp.addElement(seqs[i]);
 161       }
 162     }
 163
 164     algn.removeAllElements();
 165     // User may have hidden seqs, then clicked undo or redo
 166     for (int i = 0; i < tmp.size(); i++)
 167     {
 168       algn.addElement(tmp.elementAt(i));
 169     }
 170
 171   }
 172
 173   /**
 174    * Sorts by ID. Numbers are sorted before letters.
 175    *
 176    * @param align
 177    *                The alignment object to sort
 178    */
 179   public static void sortByID(AlignmentI align)
 180   {
 181     int nSeq = align.getHeight();
 182
 183     String[] ids = new String[nSeq];
 184     SequenceI[] seqs = new SequenceI[nSeq];
 185
 186     for (int i = 0; i < nSeq; i++)
 187     {
 188       ids[i] = align.getSequenceAt(i).getName();
 189       seqs[i] = align.getSequenceAt(i);
 190     }
 191
 192     QuickSort.sort(ids, seqs);
 193
 194     if (sortIdAscending)
 195     {
 196       setReverseOrder(align, seqs);
 197     }
 198     else
 199     {
 200       setOrder(align, seqs);
 201     }
 202
 203     sortIdAscending = !sortIdAscending;
 204   }
 205
 206   /**
 207    * Sorts the alignment by size of group. <br>
 208    * Maintains the order of sequences in each group by order in given alignment
 209    * object.
 210    *
 211    * @param align
 212    *                sorts the given alignment object by group
 213    */
 214   public static void sortByGroup(AlignmentI align)
 215   {
 216     // MAINTAINS ORIGNAL SEQUENCE ORDER,
 217     // ORDERS BY GROUP SIZE
 218     Vector groups = new Vector();
 219
 220     if (groups.hashCode() != lastGroupHash)
 221     {
 222       sortGroupAscending = true;
 223       lastGroupHash = groups.hashCode();
 224     }
 225     else
 226     {
 227       sortGroupAscending = !sortGroupAscending;
 228     }
 229
 230     // SORTS GROUPS BY SIZE
 231     // ////////////////////
 232     for (int i = 0; i < align.getGroups().size(); i++)
 233     {
 234       SequenceGroup sg = (SequenceGroup) align.getGroups().elementAt(i);
 235
 236       for (int j = 0; j < groups.size(); j++)
 237       {
 238         SequenceGroup sg2 = (SequenceGroup) groups.elementAt(j);
 239
 240         if (sg.getSize() > sg2.getSize())
 241         {
 242           groups.insertElementAt(sg, j);
 243
 244           break;
 245         }
 246       }
 247
 248       if (!groups.contains(sg))
 249       {
 250         groups.addElement(sg);
 251       }
 252     }
 253
 254     // NOW ADD SEQUENCES MAINTAINING ALIGNMENT ORDER
 255     // /////////////////////////////////////////////
 256     Vector seqs = new Vector();
 257
 258     for (int i = 0; i < groups.size(); i++)
 259     {
 260       SequenceGroup sg = (SequenceGroup) groups.elementAt(i);
 261       SequenceI[] orderedseqs = sg.getSequencesInOrder(align);
 262
 263       for (int j = 0; j < orderedseqs.length; j++)
 264       {
 265         seqs.addElement(orderedseqs[j]);
 266       }
 267     }
 268
 269     if (sortGroupAscending)
 270     {
 271       setOrder(align, seqs);
 272     }
 273     else
 274     {
 275       setReverseOrder(align,
 276               vectorSubsetToArray(seqs, align.getSequences()));
 277     }
 278   }
 279
 280   /**
 281    * Converts Vector to array. java 1.18 does not have Vector.toArray()
 282    *
 283    * @param tmp
 284    *                Vector of SequenceI objects
 285    *
 286    * @return array of Sequence[]
 287    */
 288   private static SequenceI[] vectorToArray(Vector tmp)
 289   {
 290     SequenceI[] seqs = new SequenceI[tmp.size()];
 291
 292     for (int i = 0; i < tmp.size(); i++)
 293     {
 294       seqs[i] = (SequenceI) tmp.elementAt(i);
 295     }
 296
 297     return seqs;
 298   }
 299
 300   /**
 301    * DOCUMENT ME!
 302    *
 303    * @param tmp
 304    *                DOCUMENT ME!
 305    * @param mask
 306    *                DOCUMENT ME!
 307    *
 308    * @return DOCUMENT ME!
 309    */
 310   private static SequenceI[] vectorSubsetToArray(Vector tmp, Vector mask)
 311   {
 312     Vector seqs = new Vector();
 313     int i;
 314     boolean[] tmask = new boolean[mask.size()];
 315
 316     for (i = 0; i < mask.size(); i++)
 317     {
 318       tmask[i] = true;
 319     }
 320
 321     for (i = 0; i < tmp.size(); i++)
 322     {
 323       Object sq = tmp.elementAt(i);
 324
 325       if (mask.contains(sq) && tmask[mask.indexOf(sq)])
 326       {
 327         tmask[mask.indexOf(sq)] = false;
 328         seqs.addElement(sq);
 329       }
 330     }
 331
 332     for (i = 0; i < tmask.length; i++)
 333     {
 334       if (tmask[i])
 335       {
 336         seqs.addElement(mask.elementAt(i));
 337       }
 338     }
 339
 340     return vectorToArray(seqs);
 341   }
 342
 343   /**
 344    * Sorts by a given AlignmentOrder object
 345    *
 346    * @param align
 347    *                Alignment to order
 348    * @param order
 349    *                specified order for alignment
 350    */
 351   public static void sortBy(AlignmentI align, AlignmentOrder order)
 352   {
 353     // Get an ordered vector of sequences which may also be present in align
 354     Vector tmp = order.getOrder();
 355
 356     if (lastOrder == order)
 357     {
 358       sortOrderAscending = !sortOrderAscending;
 359     }
 360     else
 361     {
 362       sortOrderAscending = true;
 363     }
 364
 365     if (sortOrderAscending)
 366     {
 367       setOrder(align, tmp);
 368     }
 369     else
 370     {
 371       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 372     }
 373   }
 374
 375   /**
 376    * DOCUMENT ME!
 377    *
 378    * @param align
 379    *                alignment to order
 380    * @param tree
 381    *                tree which has
 382    *
 383    * @return DOCUMENT ME!
 384    */
 385   private static Vector getOrderByTree(AlignmentI align, NJTree tree)
 386   {
 387     int nSeq = align.getHeight();
 388
 389     Vector tmp = new Vector();
 390
 391     tmp = _sortByTree(tree.getTopNode(), tmp, align.getSequences());
 392
 393     if (tmp.size() != nSeq)
 394     {
 395       // TODO: JBPNote - decide if this is always an error
 396       // (eg. not when a tree is associated to another alignment which has more
 397       // sequences)
 398       if (tmp.size() < nSeq)
 399       {
 400         addStrays(align, tmp);
 401       }
 402
 403       if (tmp.size() != nSeq)
 404       {
 405         System.err.println("ERROR: tmp.size()=" + tmp.size() + " != nseq="
 406                 + nSeq + " in getOrderByTree");
 407       }
 408     }
 409
 410     return tmp;
 411   }
 412
 413   /**
 414    * Sorts the alignment by a given tree
 415    *
 416    * @param align
 417    *                alignment to order
 418    * @param tree
 419    *                tree which has
 420    */
 421   public static void sortByTree(AlignmentI align, NJTree tree)
 422   {
 423     Vector tmp = getOrderByTree(align, tree);
 424
 425     // tmp should properly permute align with tree.
 426     if (lastTree != tree)
 427     {
 428       sortTreeAscending = true;
 429       lastTree = tree;
 430     }
 431     else
 432     {
 433       sortTreeAscending = !sortTreeAscending;
 434     }
 435
 436     if (sortTreeAscending)
 437     {
 438       setOrder(align, tmp);
 439     }
 440     else
 441     {
 442       setReverseOrder(align, vectorSubsetToArray(tmp, align.getSequences()));
 443     }
 444   }
 445
 446   /**
 447    * DOCUMENT ME!
 448    *
 449    * @param align
 450    *                DOCUMENT ME!
 451    * @param seqs
 452    *                DOCUMENT ME!
 453    */
 454   private static void addStrays(AlignmentI align, Vector seqs)
 455   {
 456     int nSeq = align.getHeight();
 457
 458     for (int i = 0; i < nSeq; i++)
 459     {
 460       if (!seqs.contains(align.getSequenceAt(i)))
 461       {
 462         seqs.addElement(align.getSequenceAt(i));
 463       }
 464     }
 465
 466     if (nSeq != seqs.size())
 467     {
 468       System.err
 469               .println("ERROR: Size still not right even after addStrays");
 470     }
 471   }
 472
 473   /**
 474    * DOCUMENT ME!
 475    *
 476    * @param node
 477    *                DOCUMENT ME!
 478    * @param tmp
 479    *                DOCUMENT ME!
 480    * @param seqset
 481    *                DOCUMENT ME!
 482    *
 483    * @return DOCUMENT ME!
 484    */
 485   private static Vector _sortByTree(SequenceNode node, Vector tmp,
 486           Vector seqset)
 487   {
 488     if (node == null)
 489     {
 490       return tmp;
 491     }
 492
 493     SequenceNode left = (SequenceNode) node.left();
 494     SequenceNode right = (SequenceNode) node.right();
 495
 496     if ((left == null) && (right == null))
 497     {
 498       if (!node.isPlaceholder() && (node.element() != null))
 499       {
 500         if (node.element() instanceof SequenceI)
 501         {
 502           if (!tmp.contains(node.element()))
 503           {
 504             tmp.addElement((SequenceI) node.element());
 505           }
 506         }
 507       }
 508
 509       return tmp;
 510     }
 511     else
 512     {
 513       _sortByTree(left, tmp, seqset);
 514       _sortByTree(right, tmp, seqset);
 515     }
 516
 517     return tmp;
 518   }
 519
 520   // Ordering Objects
 521   // Alignment.sortBy(OrderObj) - sequence of sequence pointer refs in
 522   // appropriate order
 523   //
 524
 525   /**
 526    * recover the order of sequences given by the safe numbering scheme introducd
 527    * SeqsetUtils.uniquify.
 528    */
 529   public static void recoverOrder(SequenceI[] alignment)
 530   {
 531     float[] ids = new float[alignment.length];
 532
 533     for (int i = 0; i < alignment.length; i++)
 534     {
 535       ids[i] = (new Float(alignment[i].getName().substring(8)))
 536               .floatValue();
 537     }
 538
 539     jalview.util.QuickSort.sort(ids, alignment);
 540   }
 541
 542   /**
 543    * Sort sequence in order of increasing score attribute for annotation with a
 544    * particular scoreLabel. Or reverse if same label was used previously
 545    *
 546    * @param scoreLabel
 547    *                exact label for sequence associated AlignmentAnnotation
 548    *                scores to use for sorting.
 549    * @param alignment
 550    *                sequences to be sorted
 551    */
 552   public static void sortByAnnotationScore(String scoreLabel,
 553           AlignmentI alignment)
 554   {
 555     SequenceI[] seqs = alignment.getSequencesArray();
 556     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
 557                                                     // presence
 558     int hasScores = 0; // number of scores present on set
 559     double[] scores = new double[seqs.length];
 560     double min = 0, max = 0;
 561     for (int i = 0; i < seqs.length; i++)
 562     {
 563       AlignmentAnnotation[] scoreAnn = seqs[i].getAnnotation(scoreLabel);
 564       if (scoreAnn != null)
 565       {
 566         hasScores++;
 567         hasScore[i] = true;
 568         scores[i] = scoreAnn[0].getScore(); // take the first instance of this
 569                                             // score.
 570         if (hasScores == 1)
 571         {
 572           max = min = scores[i];
 573         }
 574         else
 575         {
 576           if (max < scores[i])
 577           {
 578             max = scores[i];
 579           }
 580           if (min > scores[i])
 581           {
 582             min = scores[i];
 583           }
 584         }
 585       }
 586       else
 587       {
 588         hasScore[i] = false;
 589       }
 590     }
 591     if (hasScores == 0)
 592     {
 593       return; // do nothing - no scores present to sort by.
 594     }
 595     if (hasScores < seqs.length)
 596     {
 597       for (int i = 0; i < seqs.length; i++)
 598       {
 599         if (!hasScore[i])
 600         {
 601           scores[i] = (max + i+1.0);
 602         }
 603       }
 604     }
 605
 606     jalview.util.QuickSort.sort(scores, seqs);
 607     if (lastSortByScore != scoreLabel)
 608     {
 609       lastSortByScore = scoreLabel;
 610       setOrder(alignment, seqs);
 611     }
 612     else
 613     {
 614       setReverseOrder(alignment, seqs);
 615     }
 616   }
 617   /**
 618    * types of feature ordering:
 619    * Sort by score : average score - or total score - over all features in region
 620    * Sort by feature label text: (or if null - feature type text) - numerical or alphabetical
 621    * Sort by feature density: based on counts - ignoring individual text or scores for each feature
 622    */
 623   public static String FEATURE_SCORE="average_score";
 624   public static String FEATURE_LABEL="text";
 625   public static String FEATURE_DENSITY="density";
 626
 627   /**
 628    * sort the alignment using the features on each sequence found between start and stop with the given featureLabel (and optional group qualifier)
 629    * @param featureLabel (may not be null)
 630    * @param groupLabel (may be null)
 631    * @param start (-1 to include non-positional features)
 632    * @param stop (-1 to only sort on non-positional features)
 633    * @param alignment - aligned sequences containing features
 634    * @param method - one of the string constants FEATURE_SCORE, FEATURE_LABEL, FEATURE_DENSITY
 635    */
 636   public static void sortByFeature(String featureLabel, String groupLabel, int start, int stop,
 637           AlignmentI alignment, String method)
 638   {
 639     sortByFeature(featureLabel==null ? null : new String[] {featureLabel},
 640             groupLabel==null ? null : new String[] {groupLabel}, start, stop, alignment, method);
 641   }
 642   private static boolean containsIgnoreCase(final String lab, final String[] labs)
 643   {
 644     if (labs==null)
 645     {
 646       return true;
 647     }
 648     if (lab==null)
 649     {
 650       return false;
 651     }
 652     for (int q=0;q<labs.length;q++)
 653     {
 654       if (labs[q]!=null && lab.equalsIgnoreCase(labs[q]))
 655       {
 656         return true;
 657       }
 658     }
 659     return false;
 660   }
 661   public static void sortByFeature(String[] featureLabels, String[] groupLabels, int start, int stop,
 662           AlignmentI alignment, String method)
 663   {
 664     if (method!=FEATURE_SCORE && method!=FEATURE_LABEL && method!=FEATURE_DENSITY)
 665     {
 666       throw new Error("Implementation Error - sortByFeature method must be one of FEATURE_SCORE, FEATURE_LABEL or FEATURE_DENSITY.");
 667     }
 668     boolean ignoreScore=method!=FEATURE_SCORE;
 669     StringBuffer scoreLabel = new StringBuffer();
 670     scoreLabel.append(start+stop+method);
 671     for (int i=0;featureLabels!=null && i<featureLabels.length; i++)
 672     {
 673       scoreLabel.append(featureLabels[i]==null ? "null" : featureLabels[i]);
 674     }
 675     for (int i=0;groupLabels!=null && i<groupLabels.length; i++)
 676     {
 677       scoreLabel.append(groupLabels[i]==null ? "null" : groupLabels[i]);
 678     }
 679     SequenceI[] seqs = alignment.getSequencesArray();
 680
 681     boolean[] hasScore = new boolean[seqs.length]; // per sequence score
 682                                                     // presence
 683     int hasScores = 0; // number of scores present on set
 684     double[] scores = new double[seqs.length];
 685     int[] seqScores = new int[seqs.length];
 686     Object[] feats = new Object[seqs.length];
 687     double min = 0, max = 0;
 688     for (int i = 0; i < seqs.length; i++)
 689     {
 690       SequenceFeature[] sf = seqs[i].getSequenceFeatures();
 691       if (sf==null && seqs[i].getDatasetSequence()!=null)
 692       {
 693         sf = seqs[i].getDatasetSequence().getSequenceFeatures();
 694       }
 695       if (sf==null)
 696       {
 697         sf = new SequenceFeature[0];
 698       } else {
 699         SequenceFeature[] tmp = new SequenceFeature[sf.length];
 700         for (int s=0; s<tmp.length;s++)
 701         {
 702           tmp[s] = sf[s];
 703         }
 704         sf = tmp;
 705       }
 706       int sstart = (start==-1) ? start : seqs[i].findPosition(start);
 707       int sstop = (stop==-1) ? stop : seqs[i].findPosition(stop);
 708       seqScores[i]=0;
 709       scores[i]=0.0;
 710       int n=sf.length;
 711       for (int f=0;f<sf.length;f++)
 712       {
 713         // filter for selection criteria
 714         if (
 715         // ignore features outwith alignment start-stop positions.
 716         (sf[f].end < sstart || sf[f].begin > sstop)
 717                 ||
 718                 // or ignore based on selection criteria
 719                 (featureLabels != null && !AlignmentSorter.containsIgnoreCase(sf[f].type, featureLabels))
 720                 || (groupLabels != null
 721                         && (sf[f].getFeatureGroup() == null
 722                                 || !AlignmentSorter.containsIgnoreCase(sf[f].getFeatureGroup(), groupLabels))))
 723         {
 724           // forget about this feature
 725           sf[f] = null;
 726           n--;
 727         } else {
 728           // or, also take a look at the scores if necessary.
 729           if (!ignoreScore && sf[f].getScore()!=Float.NaN)
 730           {
 731             if (seqScores[i]==0)
 732             {
 733               hasScores++;
 734             }
 735             seqScores[i]++;
 736             hasScore[i] = true;
 737             scores[i] += sf[f].getScore(); // take the first instance of this
 738                                             // score.
 739           }
 740         }
 741       }
 742       SequenceFeature[] fs;
 743       feats[i] = fs = new SequenceFeature[n];
 744       if (n>0)
 745       {
 746         n=0;
 747         for (int f=0;f<sf.length;f++)
 748         {
 749           if (sf[f]!=null)
 750           {
 751             ((SequenceFeature[]) feats[i])[n++] = sf[f];
 752           }
 753         }
 754         if (method==FEATURE_LABEL)
 755         {
 756           // order the labels by alphabet
 757           String[] labs = new String[fs.length];
 758           for (int l=0;l<labs.length; l++)
 759           {
 760             labs[l] = (fs[l].getDescription()!=null ? fs[l].getDescription() : fs[l].getType());
 761           }
 762           jalview.util.QuickSort.sort(labs, ((Object[]) feats[i]));
 763         }
 764       }
 765       if (hasScore[i])
 766       {
 767         // compute average score
 768         scores[i]/=seqScores[i];
 769         // update the score bounds.
 770         if (hasScores == 1)
 771         {
 772           max = min = scores[i];
 773         }
 774         else
 775         {
 776           if (max < scores[i])
 777           {
 778             max = scores[i];
 779           }
 780           if (min > scores[i])
 781           {
 782             min = scores[i];
 783           }
 784         }
 785       }
 786     }
 787
 788     if (method==FEATURE_SCORE)
 789     {
 790       if (hasScores == 0)
 791     {
 792       return; // do nothing - no scores present to sort by.
 793     }
 794     // pad score matrix
 795     if (hasScores < seqs.length)
 796     {
 797       for (int i = 0; i < seqs.length; i++)
 798       {
 799         if (!hasScore[i])
 800         {
 801           scores[i] = (max + i);
 802         }
 803       }
 804     }
 805
 806     jalview.util.QuickSort.sort(scores, seqs);
 807     }
 808     else
 809       if (method==FEATURE_DENSITY)
 810       {
 811
 812         // break ties between equivalent numbers for adjacent sequences by adding 1/Nseq*i on the original order
 813         double fr = 0.9/(1.0*seqs.length);
 814         for (int i=0;i<seqs.length; i++)
 815         {
 816           double nf;
 817           scores[i] = (0.05+fr*i)+(nf=((feats[i]==null) ? 0.0 :1.0*((SequenceFeature[]) feats[i]).length));
 818           System.err.println("Sorting on Density: seq "+seqs[i].getName()+ " Feats: "+nf+" Score : "+scores[i]);
 819         }
 820         jalview.util.QuickSort.sort(scores, seqs);
 821       }
 822       else {
 823         if (method==FEATURE_LABEL)
 824         {
 825           throw new Error("Not yet implemented.");
 826         }
 827       }
 828     if (lastSortByFeatureScore ==null || scoreLabel.equals(lastSortByFeatureScore))
 829     {
 830       setOrder(alignment, seqs);
 831     }
 832     else
 833     {
 834       setReverseOrder(alignment, seqs);
 835     }
 836     lastSortByFeatureScore = scoreLabel.toString();
 837   }
 838
 839 }