From 3080e71dc351c70df9b01ecc58fb063de898c724 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Thu, 27 Aug 2020 15:44:45 +0100 Subject: [PATCH] JAL-3725 helper methods for computing mapped feature range overlap --- src/jalview/util/MapList.java | 48 +++++++-- src/jalview/util/MappingUtils.java | 97 ++++++++++++++---- test/jalview/util/MapListTest.java | 162 +++++++++++++++++++++++++------ test/jalview/util/MappingUtilsTest.java | 47 +++++++-- 4 files changed, 287 insertions(+), 67 deletions(-) diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index 731e976..ce78530 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -24,6 +24,8 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.List; +import jalview.bin.Cache; + /** * A simple way of bijectively mapping a non-contiguous linear range to another * non-contiguous linear range. @@ -330,9 +332,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"); + Cache.log.error("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])); @@ -345,9 +346,8 @@ public class MapList if (range.length != 2) { // throw new IllegalArgumentException(range); - System.err.println("Invalid format for toRange " - + Arrays.toString(range) - + " may cause errors"); + Cache.log.error("Invalid format for toRange " + + 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])); @@ -1134,8 +1134,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 @@ -1246,4 +1246,36 @@ public class MapList { return fromShifts.size() == 1 && toShifts.size() == 1; } + + /** + * Returns the [start, end...] positions in the range mapped from, that are + * mapped to by part or all of the given begin-end of the range mapped to. + * Returns null if begin-end does not overlap any position mapped to. + * + * @param begin + * @param end + * @return + */ + public int[] getOverlapsInFrom(final int begin, final int end) + { + int[] overlaps = MappingUtils.findOverlap(toShifts, begin, end); + + return overlaps == null ? null : locateInFrom(overlaps[0], overlaps[1]); + } + + /** + * Returns the [start, end...] positions in the range mapped to, that are + * mapped to by part or all of the given begin-end of the range mapped from. + * Returns null if begin-end does not overlap any position mapped from. + * + * @param begin + * @param end + * @return + */ + public int[] getOverlapsInTo(final int begin, final int end) + { + int[] overlaps = MappingUtils.findOverlap(fromShifts, begin, end); + + return overlaps == null ? null : locateInTo(overlaps[0], overlaps[1]); + } } diff --git a/src/jalview/util/MappingUtils.java b/src/jalview/util/MappingUtils.java index b552c21..511b9dc 100644 --- a/src/jalview/util/MappingUtils.java +++ b/src/jalview/util/MappingUtils.java @@ -20,8 +20,16 @@ */ package jalview.util; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + import jalview.analysis.AlignmentSorter; import jalview.api.AlignViewportI; +import jalview.bin.Cache; import jalview.commands.CommandI; import jalview.commands.EditCommand; import jalview.commands.EditCommand.Action; @@ -39,13 +47,6 @@ import jalview.datamodel.Sequence; import jalview.datamodel.SequenceGroup; import jalview.datamodel.SequenceI; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.HashMap; -import java.util.Iterator; -import java.util.List; -import java.util.Map; - /** * Helper methods for manipulations involving sequence mappings. * @@ -78,7 +79,7 @@ public final class MappingUtils action = action.getUndoAction(); } // TODO write this - System.err.println("MappingUtils.mapCutOrPaste not yet implemented"); + Cache.log.error("MappingUtils.mapCutOrPaste not yet implemented"); } /** @@ -546,8 +547,7 @@ public final class MappingUtils while (regions.hasNext()) { mapHiddenColumns(regions.next(), codonFrames, newHidden, - fromSequences, - toSequences, fromGapChar); + fromSequences, toSequences, fromGapChar); } return; // mappedColumns; } @@ -836,7 +836,7 @@ public final class MappingUtils { if (range.length % 2 != 0) { - System.err.println( + Cache.log.error( "Error unbalance start/end ranges: " + ranges.toString()); return 0; } @@ -965,7 +965,7 @@ public final class MappingUtils int min = Math.min(range[0], range[1]); int max = Math.max(range[0], range[1]); - + return (min <= queryRange[0] && max >= queryRange[0] && min <= queryRange[1] && max >= queryRange[1]); } @@ -980,8 +980,7 @@ public final class MappingUtils * a list of (single) [start, end] ranges * @return */ - public static void removeEndPositions(int positions, - List ranges) + public static void removeEndPositions(int positions, List ranges) { int toRemove = positions; Iterator it = new ReverseListIterator<>(ranges); @@ -993,8 +992,8 @@ public final class MappingUtils /* * not coded for [start1, end1, start2, end2, ...] */ - System.err - .println("MappingUtils.removeEndPositions doesn't handle multiple ranges"); + Cache.log.error( + "MappingUtils.removeEndPositions doesn't handle multiple ranges"); return; } @@ -1004,8 +1003,8 @@ public final class MappingUtils /* * not coded for a reverse strand range (end < start) */ - System.err - .println("MappingUtils.removeEndPositions doesn't handle reverse strand"); + Cache.log.error( + "MappingUtils.removeEndPositions doesn't handle reverse strand"); return; } if (length > toRemove) @@ -1020,4 +1019,66 @@ public final class MappingUtils } } } + + /** + * Returns the maximal start-end positions in the given (ordered) list of + * ranges which is overlapped by the given begin-end range, or null if there + * is no overlap. + * + * 
+   * Examples:
+   *   if ranges is {[4, 8], [10, 12], [16, 19]}
+   * then
+   *   findOverlap(ranges, 1, 20) == [4, 19]
+   *   findOverlap(ranges, 6, 11) == [6, 11]
+   *   findOverlap(ranges, 9, 15) == [10, 12]
+   *   findOverlap(ranges, 13, 15) == null
+   *
+ * + * @param ranges + * @param begin + * @param end + * @return + */ + protected static int[] findOverlap(List ranges, final int begin, + final int end) + { + boolean foundStart = false; + int from = 0; + int to = 0; + + /* + * traverse the ranges to find the first position (if any) >= begin, + * and the last position (if any) <= end + */ + for (int[] range : ranges) + { + if (!foundStart) + { + if (range[0] >= begin) + { + /* + * first range that starts with, or follows, begin + */ + foundStart = true; + from = Math.max(range[0], begin); + } + else if (range[1] >= begin) + { + /* + * first range that contains begin + */ + foundStart = true; + from = begin; + } + } + + if (range[0] <= end) + { + to = Math.min(end, range[1]); + } + } + + return foundStart && to >= from ? new int[] { from, to } : null; + } } diff --git a/test/jalview/util/MapListTest.java b/test/jalview/util/MapListTest.java index 86dcc39..cd6867a 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,10 +34,19 @@ 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() { JvOptionPane.setInteractiveMode(false); @@ -49,17 +56,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); @@ -294,6 +304,85 @@ public class MapListTest } /** + * Tests for method that locates the overlap of the ranges in the 'from' map + * for given range in the 'to' map + */ + @Test(groups = { "Functional" }) + public void testGetOverlapsInFrom_withIntrons() + { + /* + * Exons at positions [2, 3, 5] [6, 7, 9] [10, 12, 14] [16, 17, 18] i.e. + * 2-3, 5-7, 9-10, 12-12, 14-14, 16-18 + */ + int[] codons = { 2, 3, 5, 7, 9, 10, 12, 12, 14, 14, 16, 18 }; + int[] protein = { 11, 14 }; + MapList ml = new MapList(codons, protein, 3, 1); + + assertEquals("[2, 3, 5, 5]", + Arrays.toString(ml.getOverlapsInFrom(11, 11))); + assertEquals("[2, 3, 5, 7, 9, 9]", + Arrays.toString(ml.getOverlapsInFrom(11, 12))); + // out of range 5' : + assertEquals("[2, 3, 5, 7, 9, 9]", + Arrays.toString(ml.getOverlapsInFrom(8, 12))); + // out of range 3' : + assertEquals("[10, 10, 12, 12, 14, 14, 16, 18]", + Arrays.toString(ml.getOverlapsInFrom(13, 16))); + // out of range both : + assertEquals("[2, 3, 5, 7, 9, 10, 12, 12, 14, 14, 16, 18]", + Arrays.toString(ml.getOverlapsInFrom(1, 16))); + // no overlap: + assertNull(ml.getOverlapsInFrom(20, 25)); + } + + /** + * Tests for method that locates the overlap of the ranges in the 'to' map + * for given range in the 'from' map + */ + @Test(groups = { "Functional" }) + public void testGetOverlapsInTo_withIntrons() + { + /* + * Exons at positions [2, 3, 5] [6, 7, 9] [10, 12, 14] [17, 18, 19] i.e. + * 2-3, 5-7, 9-10, 12-12, 14-14, 17-19 + */ + int[] codons = { 2, 3, 5, 7, 9, 10, 12, 12, 14, 14, 17, 19 }; + /* + * Mapped proteins at positions 1, 3, 4, 6 in the sequence + */ + int[] protein = { 1, 1, 3, 4, 6, 6 }; + MapList ml = new MapList(codons, protein, 3, 1); + + /* + * Can't map from an unmapped position + */ + assertNull(ml.getOverlapsInTo(1, 1)); + assertNull(ml.getOverlapsInTo(4, 4)); + assertNull(ml.getOverlapsInTo(15, 16)); + + /* + * nor from a range that includes no mapped position (exon) + */ + assertNull(ml.getOverlapsInTo(15, 16)); + + // end of codon 1 maps to first peptide + assertEquals("[1, 1]", Arrays.toString(ml.getOverlapsInTo(2, 2))); + // end of codon 1 and start of codon 2 maps to first 2 peptides + assertEquals("[1, 1, 3, 3]", Arrays.toString(ml.getOverlapsInTo(3, 7))); + + // range overlaps 5' end of dna: + assertEquals("[1, 1, 3, 3]", Arrays.toString(ml.getOverlapsInTo(1, 6))); + assertEquals("[1, 1, 3, 3]", Arrays.toString(ml.getOverlapsInTo(1, 8))); + + // range overlaps 3' end of dna: + assertEquals("[6, 6]", Arrays.toString(ml.getOverlapsInTo(17, 24))); + assertEquals("[6, 6]", Arrays.toString(ml.getOverlapsInTo(16, 24))); + + // dna positions 8, 11 are intron but include end of exon 2 and start of exon 3 + assertEquals("[3, 4]", Arrays.toString(ml.getOverlapsInTo(8, 11))); + } + + /** * Tests for method that locates ranges in the 'to' map for given range in the * 'from' map. */ @@ -431,7 +520,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 +553,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 @@ -544,8 +635,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 +646,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()); @@ -581,7 +675,8 @@ public class MapListTest public void testAddMapList_sameMap() { MapList ml = new MapList(new int[] { 11, 15, 20, 25, 35, 30 }, - new int[] { 72, 22 }, 1, 3); + new int[] + { 72, 22 }, 1, 3); String before = ml.toString(); ml.addMapList(ml); assertEquals(before, ml.toString()); @@ -595,8 +690,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 +777,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 @@ -826,13 +923,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 +958,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 +976,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 +995,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 +1058,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 097ccd4..2a4693d 100644 --- a/test/jalview/util/MappingUtilsTest.java +++ b/test/jalview/util/MappingUtilsTest.java @@ -22,10 +22,23 @@ package jalview.util; import static org.testng.AssertJUnit.assertEquals; import static org.testng.AssertJUnit.assertFalse; +import static org.testng.AssertJUnit.assertNull; import static org.testng.AssertJUnit.assertSame; import static org.testng.AssertJUnit.assertTrue; +import static org.testng.internal.junit.ArrayAsserts.assertArrayEquals; + +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; @@ -46,20 +59,16 @@ 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() { JvOptionPane.setInteractiveMode(false); @@ -1284,4 +1293,22 @@ public class MappingUtilsTest assertEquals(1, ranges.size()); assertEquals(9, ranges.get(0)[1]); } + + @Test(groups = "Functional") + public void testFindOverlap() + { + List ranges = new ArrayList<>(); + ranges.add(new int[] {4, 8}); + ranges.add(new int[] {10, 12}); + ranges.add(new int[] {16, 19}); + + int[] overlap = MappingUtils.findOverlap(ranges, 5, 13); + assertArrayEquals(overlap, new int[] {5, 12}); + overlap = MappingUtils.findOverlap(ranges, -100, 100); + assertArrayEquals(overlap, new int[] {4, 19}); + overlap = MappingUtils.findOverlap(ranges, 7, 17); + assertArrayEquals(overlap, new int[] {7, 17}); + overlap = MappingUtils.findOverlap(ranges, 13, 15); + assertNull(overlap); + } } -- 1.7.10.2