From df140c55ea500ff056e0602de542c13515ed1b55 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Thu, 24 Sep 2020 11:55:20 +0100 Subject: [PATCH] JAL-3751 only merge strictly contiguous ranges of mappings --- src/jalview/util/MapList.java | 77 +++--------- test/jalview/util/MapListTest.java | 200 ++++++++++++++----------------- test/jalview/util/MappingUtilsTest.java | 27 +++-- 3 files changed, 124 insertions(+), 180 deletions(-) diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index 731e976..36fb450 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -209,8 +209,7 @@ public class MapList /** * Constructor given from and to ranges as [start1, end1, start2, end2,...]. - * If any end is equal to the next start, the ranges will be merged. There is - * no validation check that the ranges do not overlap each other. + * There is no validation check that the ranges do not overlap each other. * * @param from * contiguous regions as [start1, end1, start2, end2, ...] @@ -228,7 +227,6 @@ public class MapList this.toRatio = toRatio; fromLowest = Integer.MAX_VALUE; fromHighest = Integer.MIN_VALUE; - int added = 0; for (int i = 0; i < from.length; i += 2) { @@ -238,36 +236,16 @@ public class MapList */ fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1])); fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1])); - if (added > 0 && from[i] == fromShifts.get(added - 1)[1]) - { - /* - * this range starts where the last ended - just extend it - */ - fromShifts.get(added - 1)[1] = from[i + 1]; - } - else - { - fromShifts.add(new int[] { from[i], from[i + 1] }); - added++; - } + fromShifts.add(new int[] { from[i], from[i + 1] }); } toLowest = Integer.MAX_VALUE; toHighest = Integer.MIN_VALUE; - added = 0; for (int i = 0; i < to.length; i += 2) { toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1])); toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1])); - if (added > 0 && to[i] == toShifts.get(added - 1)[1]) - { - toShifts.get(added - 1)[1] = to[i + 1]; - } - else - { - toShifts.add(new int[] { to[i], to[i + 1] }); - added++; - } + toShifts.add(new int[] { to[i], to[i + 1] }); } } @@ -330,9 +308,8 @@ public class MapList if (range.length != 2) { // throw new IllegalArgumentException(range); - System.err.println( - "Invalid format for fromRange " + Arrays.toString(range) - + " may cause errors"); + System.err.println("Invalid format for fromRange " + + Arrays.toString(range) + " may cause errors"); } fromLowest = Math.min(fromLowest, Math.min(range[0], range[1])); fromHighest = Math.max(fromHighest, Math.max(range[0], range[1])); @@ -346,8 +323,7 @@ public class MapList { // throw new IllegalArgumentException(range); System.err.println("Invalid format for toRange " - + Arrays.toString(range) - + " may cause errors"); + + Arrays.toString(range) + " may cause errors"); } toLowest = Math.min(toLowest, Math.min(range[0], range[1])); toHighest = Math.max(toHighest, Math.max(range[0], range[1])); @@ -357,6 +333,16 @@ public class MapList /** * Consolidates a list of ranges so that any contiguous ranges are merged. * This assumes the ranges are already in start order (does not sort them). + *

+ * The main use case for this method is when mapping cDNA sequence to its + * protein product, based on CDS feature ranges which derive from spliced + * exons, but are contiguous on the cDNA sequence. For example + * 

+   *   CDS 1-20  // from exon1
+   *   CDS 21-35 // from exon2
+   *   CDS 36-71 // from exon3
+   * 'coalesce' to range 1-71
+   *
* * @param ranges * @return the same list (if unchanged), else a new merged list, leaving the @@ -384,27 +370,6 @@ public class MapList first = false; continue; } - if (range[0] == lastRange[0] && range[1] == lastRange[1]) - { - // drop duplicate range - changed = true; - continue; - } - - /* - * drop this range if it lies within the last range - */ - if ((lastDirection == 1 && range[0] >= lastRange[0] - && range[0] <= lastRange[1] && range[1] >= lastRange[0] - && range[1] <= lastRange[1]) - || (lastDirection == -1 && range[0] <= lastRange[0] - && range[0] >= lastRange[1] - && range[1] <= lastRange[0] - && range[1] >= lastRange[1])) - { - changed = true; - continue; - } int direction = range[1] >= range[0] ? 1 : -1; @@ -415,11 +380,7 @@ public class MapList boolean sameDirection = range[1] == range[0] || direction == lastDirection; boolean extending = range[0] == lastRange[1] + lastDirection; - boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0] - && range[0] <= lastRange[1]) - || (lastDirection == -1 && range[0] <= lastRange[0] - && range[0] >= lastRange[1]); - if (sameDirection && (overlapping || extending)) + if (sameDirection && extending) { lastRange[1] = range[1]; changed = true; @@ -1134,8 +1095,8 @@ public class MapList } /** - * A helper method that returns true unless at least one range has start > end. - * Behaviour is undefined for a mixture of forward and reverse ranges. + * A helper method that returns true unless at least one range has start > + * end. Behaviour is undefined for a mixture of forward and reverse ranges. * * @param ranges * @return diff --git a/test/jalview/util/MapListTest.java b/test/jalview/util/MapListTest.java index 86dcc39..71fbdfd 100644 --- a/test/jalview/util/MapListTest.java +++ b/test/jalview/util/MapListTest.java @@ -27,8 +27,6 @@ import static org.testng.AssertJUnit.assertSame; import static org.testng.AssertJUnit.assertTrue; import static org.testng.internal.junit.ArrayAsserts.assertArrayEquals; -import jalview.gui.JvOptionPane; - import java.util.ArrayList; import java.util.Arrays; import java.util.List; @@ -36,9 +34,17 @@ import java.util.List; import org.testng.annotations.BeforeClass; import org.testng.annotations.Test; +import jalview.bin.Cache; +import jalview.gui.JvOptionPane; + public class MapListTest { - + @BeforeClass(alwaysRun = true) + public void setUp() + { + Cache.initLogger(); + } + @BeforeClass(alwaysRun = true) public void setUpJvOptionPane() { @@ -49,17 +55,20 @@ public class MapListTest @Test(groups = { "Functional" }) public void testSomething() { - MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, new int[] { - 51, 1 }, 1, 3); + MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, + new int[] + { 51, 1 }, 1, 3); MapList ml1 = new MapList(new int[] { 1, 3, 17, 4 }, - new int[] { 51, 1 }, 1, 3); + new int[] + { 51, 1 }, 1, 3); MapList ml2 = new MapList(new int[] { 1, 60 }, new int[] { 1, 20 }, 3, 1); // test internal consistency int to[] = new int[51]; testMap(ml, 1, 60); - MapList mldna = new MapList(new int[] { 2, 2, 6, 8, 12, 16 }, new int[] - { 1, 3 }, 3, 1); + MapList mldna = new MapList(new int[] { 2, 2, 6, 8, 12, 16 }, + new int[] + { 1, 3 }, 3, 1); int[] frm = mldna.locateInFrom(1, 1); testLocateFrom(mldna, 1, 1, new int[] { 2, 2, 6, 7 }); testMap(mldna, 1, 3); @@ -431,7 +440,8 @@ public class MapListTest List ranges = new ArrayList<>(); ranges.add(new int[] { 2, 3 }); ranges.add(new int[] { 5, 6 }); - assertEquals("[2, 3, 5, 6]", Arrays.toString(MapList.getRanges(ranges))); + assertEquals("[2, 3, 5, 6]", + Arrays.toString(MapList.getRanges(ranges))); } /** @@ -463,7 +473,8 @@ public class MapListTest assertEquals(6, ml2.getToHighest()); assertEquals("{[2, 3], [5, 7], [9, 10], [12, 12], [14, 14], [16, 18]}", prettyPrint(ml2.getFromRanges())); - assertEquals("{[1, 1], [3, 4], [6, 6]}", prettyPrint(ml2.getToRanges())); + assertEquals("{[1, 1], [3, 4], [6, 6]}", + prettyPrint(ml2.getToRanges())); /* * reverse direction @@ -478,22 +489,23 @@ public class MapListTest } /** - * Test constructor can merge consecutive ranges + * Test constructor used to merge consecutive ranges but now just leaves them + * as supplied (JAL-3751) */ @Test(groups = { "Functional" }) public void testConstructor_mergeRanges() { - int[] codons = { 2, 3, 3, 7, 9, 10, 12, 12, 14, 14, 16, 17 }; - int[] protein = { 1, 1, 1, 3, 6, 6 }; + int[] codons = { 2, 3, 3, 7, 9, 10, 12, 12, 13, 14, 16, 17 }; + int[] protein = { 1, 1, 2, 3, 6, 6 }; MapList ml = new MapList(codons, protein, 3, 1); assertEquals(3, ml.getFromRatio()); assertEquals(2, ml.getFromLowest()); assertEquals(17, ml.getFromHighest()); assertEquals(1, ml.getToLowest()); assertEquals(6, ml.getToHighest()); - assertEquals("{[2, 7], [9, 10], [12, 12], [14, 14], [16, 17]}", + assertEquals("{[2, 3], [3, 7], [9, 10], [12, 12], [13, 14], [16, 17]}", prettyPrint(ml.getFromRanges())); - assertEquals("{[1, 3], [6, 6]}", prettyPrint(ml.getToRanges())); + assertEquals("{[1, 1], [2, 3], [6, 6]}", prettyPrint(ml.getToRanges())); } /** @@ -544,8 +556,9 @@ public class MapListTest @Test(groups = { "Functional" }) public void testToString() { - MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, new int[] { - 51, 1 }, 1, 3); + MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, + new int[] + { 51, 1 }, 1, 3); String s = ml.toString(); assertEquals("[ [1, 5] [10, 15] [25, 20] ] 1:3 to [ [51, 1] ]", s); } @@ -554,14 +567,16 @@ public class MapListTest public void testAddMapList() { MapList ml = new MapList(new int[] { 11, 15, 20, 25, 35, 30 }, - new int[] { 72, 22 }, 1, 3); + new int[] + { 72, 22 }, 1, 3); assertEquals(11, ml.getFromLowest()); assertEquals(35, ml.getFromHighest()); assertEquals(22, ml.getToLowest()); assertEquals(72, ml.getToHighest()); - MapList ml2 = new MapList(new int[] { 2, 4, 37, 40 }, new int[] { 12, - 17, 78, 83, 88, 96 }, 1, 3); + MapList ml2 = new MapList(new int[] { 2, 4, 37, 40 }, + new int[] + { 12, 17, 78, 83, 88, 96 }, 1, 3); ml.addMapList(ml2); assertEquals(2, ml.getFromLowest()); assertEquals(40, ml.getFromHighest()); @@ -595,8 +610,8 @@ public class MapListTest MapList ml = new MapList(new int[] { 11, 15 }, new int[] { 72, 58 }, 1, 3); - MapList ml2 = new MapList(new int[] { 15, 16 }, new int[] { 58, 53 }, - 1, 3); + MapList ml2 = new MapList(new int[] { 15, 16 }, new int[] { 58, 53 }, 1, + 3); ml.addMapList(ml2); assertEquals("[ [11, 16] ] 1:3 to [ [72, 53] ]", ml.toString()); } @@ -682,13 +697,15 @@ public class MapListTest public void testIsFromForwardStrand() { // [3-9] declares forward strand - MapList ml = new MapList(new int[] { 2, 2, 3, 9, 12, 11 }, new int[] { - 20, 11 }, 1, 1); + MapList ml = new MapList(new int[] { 2, 2, 3, 9, 12, 11 }, + new int[] + { 20, 11 }, 1, 1); assertTrue(ml.isFromForwardStrand()); // [11-5] declares reverse strand ([13-14] is ignored) ml = new MapList(new int[] { 2, 2, 11, 5, 13, 14 }, - new int[] { 20, 11 }, 1, 1); + new int[] + { 20, 11 }, 1, 1); assertFalse(ml.isFromForwardStrand()); // all single position ranges - defaults to forward strand @@ -698,7 +715,7 @@ public class MapListTest } /** - * Test the method that merges a list of ranges where possible + * Test the method that merges contiguous ranges */ @Test(groups = { "Functional" }) public void testCoalesceRanges() @@ -720,101 +737,57 @@ public class MapListTest // merging in forward direction: ranges.clear(); ranges.add(new int[] { 1, 3 }); - ranges.add(new int[] { 4, 5 }); - ranges.add(new int[] { 5, 5 }); - ranges.add(new int[] { 5, 7 }); + ranges.add(new int[] { 4, 5 }); // contiguous + ranges.add(new int[] { 5, 5 }); // overlap! + ranges.add(new int[] { 6, 7 }); // contiguous List merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 1, 7 }, merged.get(0)); + assertEquals(2, merged.size()); + assertArrayEquals(new int[] { 1, 5 }, merged.get(0)); + assertArrayEquals(new int[] { 5, 7 }, merged.get(1)); // verify input list is unchanged assertEquals(4, ranges.size()); assertArrayEquals(new int[] { 1, 3 }, ranges.get(0)); assertArrayEquals(new int[] { 4, 5 }, ranges.get(1)); assertArrayEquals(new int[] { 5, 5 }, ranges.get(2)); - assertArrayEquals(new int[] { 5, 7 }, ranges.get(3)); + assertArrayEquals(new int[] { 6, 7 }, ranges.get(3)); // merging in reverse direction: ranges.clear(); ranges.add(new int[] { 7, 5 }); - ranges.add(new int[] { 5, 4 }); - ranges.add(new int[] { 4, 4 }); - ranges.add(new int[] { 3, 1 }); + ranges.add(new int[] { 5, 4 }); // overlap + ranges.add(new int[] { 4, 4 }); // overlap + ranges.add(new int[] { 3, 1 }); // contiguous merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 7, 1 }, merged.get(0)); + assertEquals(3, merged.size()); + assertArrayEquals(new int[] { 7, 5 }, merged.get(0)); + assertArrayEquals(new int[] { 5, 4 }, merged.get(1)); + assertArrayEquals(new int[] { 4, 1 }, merged.get(2)); // merging with switches of direction: ranges.clear(); ranges.add(new int[] { 1, 3 }); - ranges.add(new int[] { 4, 5 }); - ranges.add(new int[] { 5, 5 }); - ranges.add(new int[] { 6, 6 }); + ranges.add(new int[] { 4, 5 }); // contiguous + ranges.add(new int[] { 5, 5 }); // overlap + ranges.add(new int[] { 6, 6 }); // contiguous ranges.add(new int[] { 12, 10 }); - ranges.add(new int[] { 9, 8 }); - ranges.add(new int[] { 8, 8 }); - ranges.add(new int[] { 7, 7 }); + ranges.add(new int[] { 9, 8 }); // contiguous + ranges.add(new int[] { 8, 8 }); // overlap + ranges.add(new int[] { 7, 7 }); // contiguous merged = MapList.coalesceRanges(ranges); - assertEquals(2, merged.size()); - assertArrayEquals(new int[] { 1, 6 }, merged.get(0)); - assertArrayEquals(new int[] { 12, 7 }, merged.get(1)); - } - - /** - * Test the method that merges a list of ranges where possible - */ - @Test(groups = { "Functional" }) - public void testCoalesceRanges_withOverlap() - { - List ranges = new ArrayList<>(); - ranges.add(new int[] { 1, 3 }); - ranges.add(new int[] { 2, 5 }); - - /* - * [2, 5] should extend [1, 3] - */ - List merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); + assertEquals(4, merged.size()); assertArrayEquals(new int[] { 1, 5 }, merged.get(0)); - - /* - * a subsumed interval should be dropped - */ - ranges.clear(); - ranges.add(new int[] { 1, 6 }); - ranges.add(new int[] { 2, 4 }); - merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 1, 6 }, merged.get(0)); - + assertArrayEquals(new int[] { 5, 6 }, merged.get(1)); + assertArrayEquals(new int[] { 12, 8 }, merged.get(2)); + assertArrayEquals(new int[] { 8, 7 }, merged.get(3)); + + // 'subsumed' ranges are preserved ranges.clear(); - ranges.add(new int[] { 1, 5 }); - ranges.add(new int[] { 1, 6 }); + ranges.add(new int[] { 10, 30 }); + ranges.add(new int[] { 15, 25 }); merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 1, 6 }, merged.get(0)); - - /* - * merge duplicate ranges - */ - ranges.clear(); - ranges.add(new int[] { 1, 3 }); - ranges.add(new int[] { 1, 3 }); - merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 1, 3 }, merged.get(0)); - - /* - * reverse direction - */ - ranges.clear(); - ranges.add(new int[] { 9, 5 }); - ranges.add(new int[] { 9, 4 }); - ranges.add(new int[] { 8, 3 }); - ranges.add(new int[] { 3, 2 }); - ranges.add(new int[] { 1, 0 }); - merged = MapList.coalesceRanges(ranges); - assertEquals(1, merged.size()); - assertArrayEquals(new int[] { 9, 0 }, merged.get(0)); + assertEquals(2, merged.size()); + assertArrayEquals(new int[] { 10, 30 }, merged.get(0)); + assertArrayEquals(new int[] { 15, 25 }, merged.get(1)); } /** @@ -826,13 +799,15 @@ public class MapListTest /* * simple 1:1 plus 1:1 forwards */ - MapList ml1 = new MapList(new int[] { 3, 4, 8, 12 }, new int[] { 5, 8, - 11, 13 }, 1, 1); + MapList ml1 = new MapList(new int[] { 3, 4, 8, 12 }, + new int[] + { 5, 8, 11, 13 }, 1, 1); assertEquals("{[3, 4], [8, 12]}", prettyPrint(ml1.getFromRanges())); assertEquals("{[5, 8], [11, 13]}", prettyPrint(ml1.getToRanges())); - MapList ml2 = new MapList(new int[] { 1, 50 }, new int[] { 40, 45, 70, - 75, 90, 127 }, 1, 1); + MapList ml2 = new MapList(new int[] { 1, 50 }, + new int[] + { 40, 45, 70, 75, 90, 127 }, 1, 1); assertEquals("{[1, 50]}", prettyPrint(ml2.getFromRanges())); assertEquals("{[40, 45], [70, 75], [90, 127]}", prettyPrint(ml2.getToRanges())); @@ -859,7 +834,8 @@ public class MapListTest */ ml1 = new MapList(new int[] { 1, 50 }, new int[] { 70, 119 }, 1, 1); ml2 = new MapList(new int[] { 1, 500 }, - new int[] { 1000, 901, 600, 201 }, 1, 1); + new int[] + { 1000, 901, 600, 201 }, 1, 1); compound = ml1.traverse(ml2); assertEquals(1, compound.getFromRatio()); @@ -876,8 +852,8 @@ public class MapListTest * 1:1 plus 1:3 should result in 1:3 */ ml1 = new MapList(new int[] { 1, 30 }, new int[] { 11, 40 }, 1, 1); - ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 50, 91, 340 }, - 1, 3); + ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 50, 91, 340 }, 1, + 3); compound = ml1.traverse(ml2); assertEquals(1, compound.getFromRatio()); @@ -895,8 +871,8 @@ public class MapListTest * 3:1 plus 1:1 should result in 3:1 */ ml1 = new MapList(new int[] { 1, 30 }, new int[] { 11, 20 }, 3, 1); - ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 15, 91, 175 }, - 1, 1); + ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 15, 91, 175 }, 1, + 1); compound = ml1.traverse(ml2); assertEquals(3, compound.getFromRatio()); @@ -958,8 +934,8 @@ public class MapListTest } /** - * Test that method that inspects for the (first) forward or reverse 'to' range. - * Single position ranges are ignored. + * Test that method that inspects for the (first) forward or reverse 'to' + * range. Single position ranges are ignored. */ @Test(groups = { "Functional" }) public void testIsToForwardsStrand() diff --git a/test/jalview/util/MappingUtilsTest.java b/test/jalview/util/MappingUtilsTest.java index dd789d6..cfb2563 100644 --- a/test/jalview/util/MappingUtilsTest.java +++ b/test/jalview/util/MappingUtilsTest.java @@ -26,7 +26,18 @@ import static org.testng.AssertJUnit.assertSame; import static org.testng.AssertJUnit.assertTrue; import static org.testng.AssertJUnit.fail; +import java.awt.Color; +import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Iterator; +import java.util.List; + +import org.testng.annotations.BeforeClass; +import org.testng.annotations.Test; + import jalview.api.AlignViewportI; +import jalview.bin.Cache; import jalview.commands.EditCommand; import jalview.commands.EditCommand.Action; import jalview.commands.EditCommand.Edit; @@ -47,18 +58,14 @@ import jalview.io.FileFormat; import jalview.io.FileFormatI; import jalview.io.FormatAdapter; -import java.awt.Color; -import java.io.IOException; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Iterator; -import java.util.List; - -import org.testng.annotations.BeforeClass; -import org.testng.annotations.Test; - public class MappingUtilsTest { + @BeforeClass(alwaysRun = true) + public void setUp() + { + Cache.initLogger(); + } + @BeforeClass(alwaysRun = true) public void setUpJvOptionPane() -- 1.7.10.2