test/jalview/analysis/AnnotationSorterTest.java

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