test/jalview/analysis/AnnotationSorterTest.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 static org.testng.AssertJUnit.assertEquals;
  24
  25 import jalview.analysis.AnnotationSorter.SequenceAnnotationOrder;
  26 import jalview.datamodel.Alignment;
  27 import jalview.datamodel.AlignmentAnnotation;
  28 import jalview.datamodel.Sequence;
  29 import jalview.datamodel.SequenceI;
  30
  31 import java.util.ArrayList;
  32 import java.util.List;
  33 import java.util.Random;
  34
  35 import org.testng.annotations.BeforeMethod;
  36 import org.testng.annotations.Test;
  37
  38 public class AnnotationSorterTest
  39 {
  40   private static final int NUM_SEQS = 6;
  41
  42   private static final int NUM_ANNS = 7;
  43
  44   private static final String SS = "secondary structure";
  45
  46   AlignmentAnnotation[] anns = new AlignmentAnnotation[0];
  47
  48   Alignment al = null;
  49
  50   /*
  51    * Set up 6 sequences and 7 annotations.
  52    */
  53   @BeforeMethod(alwaysRun = true)
  54   public void setUp()
  55   {
  56     al = buildAlignment(NUM_SEQS);
  57     anns = buildAnnotations(NUM_ANNS);
  58   }
  59
  60   /**
  61    * Construct an array of numAnns annotations
  62    *
  63    * @param numAnns
  64    *
  65    * @return
  66    */
  67   protected AlignmentAnnotation[] buildAnnotations(int numAnns)
  68   {
  69     List<AlignmentAnnotation> annlist = new ArrayList<AlignmentAnnotation>();
  70     for (int i = 0; i < numAnns; i++)
  71     {
  72       AlignmentAnnotation ann = new AlignmentAnnotation(SS + i, "", 0);
  73       annlist.add(ann);
  74     }
  75     return annlist.toArray(anns);
  76   }
  77
  78   /**
  79    * Make an alignment with numSeqs sequences in it.
  80    *
  81    * @param numSeqs
  82    *
  83    * @return
  84    */
  85   private Alignment buildAlignment(int numSeqs)
  86   {
  87     SequenceI[] seqs = new Sequence[numSeqs];
  88     for (int i = 0; i < numSeqs; i++)
  89     {
  90       seqs[i] = new Sequence("Sequence" + i, "axrdkfp");
  91     }
  92     return new Alignment(seqs);
  93   }
  94
  95   /**
  96    * Test sorting by annotation type (label) within sequence order, including
  97    * <ul>
  98    * <li>annotations with no sequence reference - sort to end keeping mutual
  99    * ordering</li>
 100    * <li>annotations with sequence ref = sort in sequence order</li>
 101    * <li>multiple annotations for same sequence ref - sort by label
 102    * non-case-specific</li>
 103    * <li>annotations with reference to sequence not in alignment - treat like no
 104    * sequence ref</li>
 105    * </ul>
 106    */
 107   @Test(groups = { "Functional" })
 108   public void testSortBySequenceAndType_autocalcLast()
 109   {
 110     // @formatter:off
 111     anns[0].sequenceRef = al.getSequenceAt(1); anns[0].label = "label0";
 112     anns[1].sequenceRef = al.getSequenceAt(3); anns[1].label = "structure";
 113     anns[2].sequenceRef = al.getSequenceAt(3); anns[2].label = "iron";
 114     anns[3].autoCalculated = true;             anns[3].label = "Quality";
 115     anns[4].autoCalculated = true;             anns[4].label = "Consensus";
 116     anns[5].sequenceRef = al.getSequenceAt(0); anns[5].label = "label5";
 117     anns[6].sequenceRef = al.getSequenceAt(3); anns[6].label = "IRP";
 118     // @formatter:on
 119
 120     AnnotationSorter testee = new AnnotationSorter(al, false);
 121     testee.sort(anns, SequenceAnnotationOrder.SEQUENCE_AND_LABEL);
 122     assertEquals("label5", anns[0].label); // for sequence 0
 123     assertEquals("label0", anns[1].label); // for sequence 1
 124     assertEquals("iron", anns[2].label); // sequence 3 /iron
 125     assertEquals("IRP", anns[3].label); // sequence 3/IRP
 126     assertEquals("structure", anns[4].label); // sequence 3/structure
 127     assertEquals("Quality", anns[5].label); // autocalc annotations
 128     assertEquals("Consensus", anns[6].label); // retain ordering
 129   }
 130
 131   /**
 132    * Variant with autocalculated annotations sorting to front
 133    */
 134   @Test(groups = { "Functional" })
 135   public void testSortBySequenceAndType_autocalcFirst()
 136   {
 137     // @formatter:off
 138     anns[0].sequenceRef = al.getSequenceAt(1); anns[0].label = "label0";
 139     anns[1].sequenceRef = al.getSequenceAt(3); anns[1].label = "structure";
 140     anns[2].sequenceRef = al.getSequenceAt(3); anns[2].label = "iron";
 141     anns[3].autoCalculated = true;             anns[3].label = "Quality";
 142     anns[4].autoCalculated = true;             anns[4].label = "Consensus";
 143     anns[5].sequenceRef = al.getSequenceAt(0); anns[5].label = "label5";
 144     anns[6].sequenceRef = al.getSequenceAt(3); anns[6].label = "IRP";
 145     // @formatter:on
 146
 147     AnnotationSorter testee = new AnnotationSorter(al, true);
 148     testee.sort(anns, SequenceAnnotationOrder.SEQUENCE_AND_LABEL);
 149     assertEquals("Quality", anns[0].label); // autocalc annotations
 150     assertEquals("Consensus", anns[1].label); // retain ordering
 151     assertEquals("label5", anns[2].label); // for sequence 0
 152     assertEquals("label0", anns[3].label); // for sequence 1
 153     assertEquals("iron", anns[4].label); // sequence 3 /iron
 154     assertEquals("IRP", anns[5].label); // sequence 3/IRP
 155     assertEquals("structure", anns[6].label); // sequence 3/structure
 156   }
 157
 158   /**
 159    * Test sorting by annotation type (label) within sequence order, including
 160    * <ul>
 161    * <li>annotations with no sequence reference - sort to end keeping mutual
 162    * ordering</li>
 163    * <li>annotations with sequence ref = sort in sequence order</li>
 164    * <li>multiple annotations for same sequence ref - sort by label
 165    * non-case-specific</li>
 166    * <li>annotations with reference to sequence not in alignment - treat like no
 167    * sequence ref</li>
 168    * </ul>
 169    */
 170   @Test(groups = { "Functional" })
 171   public void testSortByTypeAndSequence_autocalcLast()
 172   {
 173     // @formatter:off
 174     anns[0].sequenceRef = al.getSequenceAt(1); anns[0].label = "label0";
 175     anns[1].sequenceRef = al.getSequenceAt(3); anns[1].label = "structure";
 176     anns[2].sequenceRef = al.getSequenceAt(3); anns[2].label = "iron";
 177     anns[3].autoCalculated = true;             anns[3].label = "Quality";
 178     anns[4].autoCalculated = true;             anns[4].label = "Consensus";
 179     anns[5].sequenceRef = al.getSequenceAt(0); anns[5].label = "IRON";
 180     anns[6].sequenceRef = al.getSequenceAt(2); anns[6].label = "Structure";
 181     // @formatter:on
 182
 183     AnnotationSorter testee = new AnnotationSorter(al, false);
 184     testee.sort(anns, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
 185     assertEquals("IRON", anns[0].label); // IRON / sequence 0
 186     assertEquals("iron", anns[1].label); // iron / sequence 3
 187     assertEquals("label0", anns[2].label); // label0 / sequence 1
 188     assertEquals("Structure", anns[3].label); // Structure / sequence 2
 189     assertEquals("structure", anns[4].label); // structure / sequence 3
 190     assertEquals("Quality", anns[5].label); // autocalc annotations
 191     assertEquals("Consensus", anns[6].label); // retain ordering
 192   }
 193
 194   /**
 195    * Variant of test with autocalculated annotations sorted to front
 196    */
 197   @Test(groups = { "Functional" })
 198   public void testSortByTypeAndSequence_autocalcFirst()
 199   {
 200     // @formatter:off
 201     anns[0].sequenceRef = al.getSequenceAt(1); anns[0].label = "label0";
 202     anns[1].sequenceRef = al.getSequenceAt(3); anns[1].label = "structure";
 203     anns[2].sequenceRef = al.getSequenceAt(3); anns[2].label = "iron";
 204     anns[3].autoCalculated = true;             anns[3].label = "Quality";
 205     anns[4].autoCalculated = true;             anns[4].label = "Consensus";
 206     anns[5].sequenceRef = al.getSequenceAt(0); anns[5].label = "IRON";
 207     anns[6].sequenceRef = al.getSequenceAt(2); anns[6].label = "Structure";
 208     // @formatter:on
 209
 210     AnnotationSorter testee = new AnnotationSorter(al, true);
 211     testee.sort(anns, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
 212     assertEquals("Quality", anns[0].label); // autocalc annotations
 213     assertEquals("Consensus", anns[1].label); // retain ordering
 214     assertEquals("IRON", anns[2].label); // IRON / sequence 0
 215     assertEquals("iron", anns[3].label); // iron / sequence 3
 216     assertEquals("label0", anns[4].label); // label0 / sequence 1
 217     assertEquals("Structure", anns[5].label); // Structure / sequence 2
 218     assertEquals("structure", anns[6].label); // structure / sequence 3
 219   }
 220
 221   /**
 222    * Variant of test with autocalculated annotations sorted to front but
 223    * otherwise no change.
 224    */
 225   @Test(groups = { "Functional" })
 226   public void testNoSort_autocalcFirst()
 227   {
 228     // @formatter:off
 229     anns[0].sequenceRef = al.getSequenceAt(1); anns[0].label = "label0";
 230     anns[1].sequenceRef = al.getSequenceAt(3); anns[1].label = "structure";
 231     anns[2].sequenceRef = al.getSequenceAt(3); anns[2].label = "iron";
 232     anns[3].autoCalculated = true;             anns[3].label = "Quality";
 233     anns[4].autoCalculated = true;             anns[4].label = "Consensus";
 234     anns[5].sequenceRef = al.getSequenceAt(0); anns[5].label = "IRON";
 235     anns[6].sequenceRef = al.getSequenceAt(2); anns[6].label = "Structure";
 236     // @formatter:on
 237
 238     AnnotationSorter testee = new AnnotationSorter(al, true);
 239     testee.sort(anns, SequenceAnnotationOrder.NONE);
 240     assertEquals("Quality", anns[0].label); // autocalc annotations
 241     assertEquals("Consensus", anns[1].label); // retain ordering
 242     assertEquals("label0", anns[2].label);
 243     assertEquals("structure", anns[3].label);
 244     assertEquals("iron", anns[4].label);
 245     assertEquals("IRON", anns[5].label);
 246     assertEquals("Structure", anns[6].label);
 247   }
 248
 249   @Test(groups = { "Functional" })
 250   public void testSort_timingPresorted()
 251   {
 252     testTiming_presorted(50, 100);
 253     testTiming_presorted(500, 1000);
 254     testTiming_presorted(5000, 10000);
 255   }
 256
 257   /**
 258    * Test timing to sort annotations already in the sort order.
 259    *
 260    * @param numSeqs
 261    * @param numAnns
 262    */
 263   private void testTiming_presorted(final int numSeqs, final int numAnns)
 264   {
 265     Alignment alignment = buildAlignment(numSeqs);
 266     AlignmentAnnotation[] annotations = buildAnnotations(numAnns);
 267
 268     /*
 269      * Set the annotations presorted by label
 270      */
 271     Random r = new Random();
 272     final SequenceI[] sequences = alignment.getSequencesArray();
 273     for (int i = 0; i < annotations.length; i++)
 274     {
 275       SequenceI randomSequenceRef = sequences[r.nextInt(sequences.length)];
 276       annotations[i].sequenceRef = randomSequenceRef;
 277       annotations[i].label = "label" + i;
 278     }
 279     long startTime = System.currentTimeMillis();
 280     AnnotationSorter testee = new AnnotationSorter(alignment, false);
 281     testee.sort(annotations, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
 282     long endTime = System.currentTimeMillis();
 283     final long elapsed = endTime - startTime;
 284     System.out.println("Timing test for presorted " + numSeqs
 285             + " sequences and " + numAnns + " annotations took " + elapsed
 286             + "ms");
 287   }
 288
 289   /**
 290    * Timing tests for sorting randomly sorted annotations for various sizes.
 291    */
 292   @Test(groups = { "Functional" })
 293   public void testSort_timingUnsorted()
 294   {
 295     testTiming_unsorted(50, 100);
 296     testTiming_unsorted(500, 1000);
 297     testTiming_unsorted(5000, 10000);
 298   }
 299
 300   /**
 301    * Generate annotations randomly sorted with respect to sequences, and time
 302    * sorting.
 303    *
 304    * @param numSeqs
 305    * @param numAnns
 306    */
 307   private void testTiming_unsorted(final int numSeqs, final int numAnns)
 308   {
 309     Alignment alignment = buildAlignment(numSeqs);
 310     AlignmentAnnotation[] annotations = buildAnnotations(numAnns);
 311
 312     /*
 313      * Set the annotations in random order with respect to the sequences
 314      */
 315     Random r = new Random();
 316     final SequenceI[] sequences = alignment.getSequencesArray();
 317     for (int i = 0; i < annotations.length; i++)
 318     {
 319       SequenceI randomSequenceRef = sequences[r.nextInt(sequences.length)];
 320       annotations[i].sequenceRef = randomSequenceRef;
 321       annotations[i].label = "label" + i;
 322     }
 323     long startTime = System.currentTimeMillis();
 324     AnnotationSorter testee = new AnnotationSorter(alignment, false);
 325     testee.sort(annotations, SequenceAnnotationOrder.SEQUENCE_AND_LABEL);
 326     long endTime = System.currentTimeMillis();
 327     final long elapsed = endTime - startTime;
 328     System.out.println("Timing test for unsorted " + numSeqs
 329             + " sequences and " + numAnns + " annotations took " + elapsed
 330             + "ms");
 331   }
 332
 333   /**
 334    * Timing test for sorting annotations with a limited range of types (labels).
 335    */
 336   @Test(groups = { "Functional" })
 337   public void testSort_timingSemisorted()
 338   {
 339     testTiming_semiSorted(50, 100);
 340     testTiming_semiSorted(500, 1000);
 341     testTiming_semiSorted(5000, 10000);
 342   }
 343
 344   /**
 345    * Mimic 'semi-sorted' annotations:
 346    * <ul>
 347    * <li>set up in sequence order, with randomly assigned labels from a limited
 348    * range</li>
 349    * <li>sort by label and sequence order, report timing</li>
 350    * <li>resort by sequence and label, report timing</li>
 351    * <li>resort by label and sequence, report timing</li>
 352    * </ul>
 353    *
 354    * @param numSeqs
 355    * @param numAnns
 356    */
 357   private void testTiming_semiSorted(final int numSeqs, final int numAnns)
 358   {
 359     Alignment alignment = buildAlignment(numSeqs);
 360     AlignmentAnnotation[] annotations = buildAnnotations(numAnns);
 361
 362     String[] labels = new String[] { "label1", "label2", "label3",
 363         "label4", "label5", "label6" };
 364
 365     /*
 366      * Set the annotations in sequence order with randomly assigned labels.
 367      */
 368     Random r = new Random();
 369     final SequenceI[] sequences = alignment.getSequencesArray();
 370     for (int i = 0; i < annotations.length; i++)
 371     {
 372       SequenceI sequenceRef = sequences[i % sequences.length];
 373       annotations[i].sequenceRef = sequenceRef;
 374       annotations[i].label = labels[r.nextInt(labels.length)];
 375     }
 376     long startTime = System.currentTimeMillis();
 377     AnnotationSorter testee = new AnnotationSorter(alignment, false);
 378     testee.sort(annotations, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
 379     long endTime = System.currentTimeMillis();
 380     long elapsed = endTime - startTime;
 381     System.out.println("Sort by label for semisorted " + numSeqs
 382             + " sequences and " + numAnns + " annotations took " + elapsed
 383             + "ms");
 384
 385     // now resort by sequence
 386     startTime = System.currentTimeMillis();
 387     testee.sort(annotations, SequenceAnnotationOrder.SEQUENCE_AND_LABEL);
 388     endTime = System.currentTimeMillis();
 389     elapsed = endTime - startTime;
 390     System.out.println("Resort by sequence for semisorted " + numSeqs
 391             + " sequences and " + numAnns + " annotations took " + elapsed
 392             + "ms");
 393
 394     // now resort by label
 395     startTime = System.currentTimeMillis();
 396     testee.sort(annotations, SequenceAnnotationOrder.LABEL_AND_SEQUENCE);
 397     endTime = System.currentTimeMillis();
 398     elapsed = endTime - startTime;
 399     System.out.println("Resort by label for semisorted " + numSeqs
 400             + " sequences and " + numAnns + " annotations took " + elapsed
 401             + "ms");
 402   }
 403 }