From c17981672620e0b780a2338bd0c74e55cf9ddec2 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 | 38 +++++++++++++- src/jalview/util/MappingUtils.java | 82 ++++++++++++++++++++++++++---- test/jalview/util/MapListTest.java | 84 ++++++++++++++++++++++++++++++- test/jalview/util/MappingUtilsTest.java | 22 +++++++- 4 files changed, 211 insertions(+), 15 deletions(-) diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index 36fb450..c5654fb 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. @@ -308,7 +310,7 @@ public class MapList if (range.length != 2) { // throw new IllegalArgumentException(range); - System.err.println("Invalid format for fromRange " + Cache.log.error("Invalid format for fromRange " + Arrays.toString(range) + " may cause errors"); } fromLowest = Math.min(fromLowest, Math.min(range[0], range[1])); @@ -322,7 +324,7 @@ public class MapList if (range.length != 2) { // throw new IllegalArgumentException(range); - System.err.println("Invalid format for toRange " + Cache.log.error("Invalid format for toRange " + Arrays.toString(range) + " may cause errors"); } toLowest = Math.min(toLowest, Math.min(range[0], range[1])); @@ -1207,4 +1209,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 499fc6b..6294ca1 100644 --- a/src/jalview/util/MappingUtils.java +++ b/src/jalview/util/MappingUtils.java @@ -20,6 +20,13 @@ */ 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; @@ -41,13 +48,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. * @@ -835,7 +835,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; } @@ -991,7 +991,7 @@ public final class MappingUtils /* * not coded for [start1, end1, start2, end2, ...] */ - System.err.println( + Cache.log.error( "MappingUtils.removeEndPositions doesn't handle multiple ranges"); return; } @@ -1002,7 +1002,7 @@ public final class MappingUtils /* * not coded for a reverse strand range (end < start) */ - System.err.println( + Cache.log.error( "MappingUtils.removeEndPositions doesn't handle reverse strand"); return; } @@ -1037,4 +1037,66 @@ public final class MappingUtils } return result; } + + /** + * 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 71fbdfd..6bbda78 100644 --- a/test/jalview/util/MapListTest.java +++ b/test/jalview/util/MapListTest.java @@ -44,7 +44,7 @@ public class MapListTest { Cache.initLogger(); } - + @BeforeClass(alwaysRun = true) public void setUpJvOptionPane() { @@ -303,6 +303,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. */ @@ -596,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()); diff --git a/test/jalview/util/MappingUtilsTest.java b/test/jalview/util/MappingUtilsTest.java index d0269d8..0997fec 100644 --- a/test/jalview/util/MappingUtilsTest.java +++ b/test/jalview/util/MappingUtilsTest.java @@ -22,10 +22,13 @@ 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.AssertJUnit.fail; +import static org.testng.internal.junit.ArrayAsserts.assertArrayEquals; + import java.awt.Color; import java.io.IOException; import java.util.ArrayList; @@ -66,7 +69,6 @@ public class MappingUtilsTest Cache.initLogger(); } - @BeforeClass(alwaysRun = true) public void setUpJvOptionPane() { @@ -1459,4 +1461,22 @@ public class MappingUtilsTest assertEquals(0, mappedGroup.getStartRes()); assertEquals(1, mappedGroup.getEndRes()); // two columns } + + @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