test/jalview/analysis/AnnotationSorterTest.java

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