X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Futil%2FMapList.java;h=b3eabae6e62b91e46a021d262a8c0bf88d1dde2e;hb=77a64be30e2b21de5688ce37a63648ad3fb1bec8;hp=2e673e0f33fc7604eafda70403dd5dbb920ed347;hpb=a9e1fa623b6f66f2e32436ea43a31180784f5044;p=jalview.git diff --git a/src/jalview/util/MapList.java b/src/jalview/util/MapList.java index 2e673e0..b3eabae 100644 --- a/src/jalview/util/MapList.java +++ b/src/jalview/util/MapList.java @@ -22,16 +22,17 @@ package jalview.util; import java.util.ArrayList; import java.util.Arrays; +import java.util.BitSet; import java.util.List; +import jalview.bin.Console; + /** * A simple way of bijectively mapping a non-contiguous linear range to another * non-contiguous linear range. * * Use at your own risk! * - * TODO: efficient implementation of private posMap method - * * TODO: test/ensure that sense of from and to ratio start position is conserved * (codon start position recovery) */ @@ -308,7 +309,7 @@ public class MapList if (range.length != 2) { // throw new IllegalArgumentException(range); - System.err.println("Invalid format for fromRange " + Console.error("Invalid format for fromRange " + Arrays.toString(range) + " may cause errors"); } fromLowest = Math.min(fromLowest, Math.min(range[0], range[1])); @@ -322,8 +323,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"); + Console.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])); @@ -406,7 +407,7 @@ public class MapList */ protected int[][] makeFromMap() { - // TODO not used - remove?? + // TODO only used for test - remove?? return posMap(fromShifts, fromRatio, toShifts, toRatio); } @@ -417,7 +418,7 @@ public class MapList */ protected int[][] makeToMap() { - // TODO not used - remove?? + // TODO only used for test - remove?? return posMap(toShifts, toRatio, fromShifts, fromRatio); } @@ -428,10 +429,10 @@ public class MapList * @return int[] { from, to pos in range }, int[range.to-range.from+1] * returning mapped position */ - private int[][] posMap(List shiftTo, int ratio, - List shiftFrom, int toRatio) + private int[][] posMap(List shiftTo, int sourceRatio, + List shiftFrom, int targetRatio) { - // TODO not used - remove?? + // TODO only used for test - remove?? int iv = 0, ivSize = shiftTo.size(); if (iv >= ivSize) { @@ -468,7 +469,8 @@ public class MapList int mp[][] = new int[to - from + 2][]; for (int i = 0; i < mp.length; i++) { - int[] m = shift(i + from, shiftTo, ratio, shiftFrom, toRatio); + int[] m = shift(i + from, shiftTo, sourceRatio, shiftFrom, + targetRatio); if (m != null) { if (i == 0) @@ -693,41 +695,6 @@ public class MapList } /** - * find series of intervals mapping from start-end in the From map. - * - * @param start - * position mapped 'to' - * @param end - * position mapped 'to' - * @return series of [start, end] ranges in sequence mapped 'from' - */ - public int[] locateInFrom(int start, int end) - { - // inefficient implementation - int fromStart[] = shiftTo(start); - // needs to be inclusive of end of symbol position - int fromEnd[] = shiftTo(end); - System.out.println("locateInFrom"); - return getIntervals(fromShifts, fromStart, fromEnd, fromRatio); - } - - /** - * find series of intervals mapping from start-end in the to map. - * - * @param start - * position mapped 'from' - * @param end - * position mapped 'from' - * @return series of [start, end] ranges in sequence mapped 'to' - */ - public int[] locateInTo(int start, int end) - { - int toStart[] = shiftFrom(start); - int toEnd[] = shiftFrom(end); - return getIntervals(toShifts, toStart, toEnd, toRatio); - } - - /** * like shift - except returns the intervals in the given vector of shifts * which were spanned in traversing fromStart to fromEnd * @@ -903,7 +870,6 @@ public class MapList */ public int getToPosition(int mpos) { - // TODO not used - remove?? int[] mp = shiftTo(mpos); if (mp != null) { @@ -913,53 +879,6 @@ public class MapList } /** - * get range of positions in To frame for the mpos word in From - * - * @param mpos - * position in From - * @return null or int[] first position in To for mpos, last position in to - * for Mpos - */ - public int[] getToWord(int mpos) - { - int[] mp = shiftTo(mpos); - if (mp != null) - { - return new int[] { mp[0], mp[0] + mp[2] * (getFromRatio() - 1) }; - } - return null; - } - - /** - * get From position in the associated reference frame for position pos in the - * associated sequence. - * - * @param pos - * @return - */ - public int getMappedPosition(int pos) - { - // TODO not used - remove?? - int[] mp = shiftFrom(pos); - if (mp != null) - { - return mp[0]; - } - return pos; - } - - public int[] getMappedWord(int pos) - { - // TODO not used - remove?? - int[] mp = shiftFrom(pos); - if (mp != null) - { - return new int[] { mp[0], mp[0] + mp[2] * (getToRatio() - 1) }; - } - return null; - } - - /** * * @return a MapList whose From range is this maplist's To Range, and vice * versa @@ -971,33 +890,6 @@ public class MapList } /** - * test for containment rather than equivalence to another mapping - * - * @param map - * to be tested for containment - * @return true if local or mapped range map contains or is contained by this - * mapping - */ - public boolean containsEither(boolean local, MapList map) - { - // TODO not used - remove? - if (local) - { - return ((getFromLowest() >= map.getFromLowest() - && getFromHighest() <= map.getFromHighest()) - || (getFromLowest() <= map.getFromLowest() - && getFromHighest() >= map.getFromHighest())); - } - else - { - return ((getToLowest() >= map.getToLowest() - && getToHighest() <= map.getToHighest()) - || (getToLowest() <= map.getToLowest() - && getToHighest() >= map.getToHighest())); - } - } - - /** * String representation - for debugging, not guaranteed not to change */ @Override @@ -1212,6 +1104,7 @@ public class MapList List toRanges = new ArrayList<>(); for (int[] range : getToRanges()) { + int fromLength = Math.abs(range[1] - range[0]) + 1; int[] transferred = map.locateInTo(range[0], range[1]); if (transferred == null || transferred.length % 2 != 0) { @@ -1222,11 +1115,21 @@ public class MapList * convert [start1, end1, start2, end2, ...] * to [[start1, end1], [start2, end2], ...] */ + int toLength = 0; for (int i = 0; i < transferred.length;) { toRanges.add(new int[] { transferred[i], transferred[i + 1] }); + toLength += Math.abs(transferred[i + 1] - transferred[i]) + 1; i += 2; } + + /* + * check we mapped the full range - if not, abort + */ + if (fromLength * map.getToRatio() != toLength * map.getFromRatio()) + { + return null; + } } return new MapList(getFromRanges(), toRanges, outFromRatio, outToRatio); @@ -1244,229 +1147,313 @@ public class MapList } /** - * Returns the [start, end, start, end, ...] ranges in the 'from' range that - * map to the given start-end in the 'to' range. Returns null if either - * {@code start} or {@code end} is not a mapped 'to' range position. + * <<<<<<< HEAD Returns the [start1, end1, start2, end2, ...] positions in the + * 'from' range that map to positions between {@code start} and {@code end} in + * the 'to' range. Note that for a reverse strand mapping this will return + * ranges with end < start. Returns null if no mapped positions are found in + * start-end. * * @param start * @param end * @return */ - public int[] locateInFrom2(int start, int end) + public int[] locateInFrom(int start, int end) { - List ranges = mapBetween(start, end, toShifts, fromShifts, - toRatio, fromRatio); - - // TODO: or just return the List and adjust calling code to match - return ranges.isEmpty() ? null : MappingUtils.rangeListToArray(ranges); + return mapPositions(start, end, toShifts, fromShifts, toRatio, + fromRatio); } /** - * Returns the [start, end, start, end, ...] ranges in the 'to' range that map - * to the given start-end in the 'from' range. Returns null if either - * {@code start} or {@code end} is not a mapped 'from' range position. + * Returns the [start1, end1, start2, end2, ...] positions in the 'to' range + * that map to positions between {@code start} and {@code end} in the 'from' + * range. Note that for a reverse strand mapping this will return ranges with + * end < start. Returns null if no mapped positions are found in start-end. * * @param start * @param end * @return */ - public int[] locateInTo2(int start, int end) + public int[] locateInTo(int start, int end) { - List ranges = mapBetween(start, end, fromShifts, toShifts, - fromRatio, toRatio); - - return ranges.isEmpty() ? null : MappingUtils.rangeListToArray(ranges); + return mapPositions(start, end, fromShifts, toShifts, fromRatio, + toRatio); } /** - * A helper method for navigating the mapping. Returns a (possibly empty) list - * of [start-end] positions in {@code ranges2} that map to positions in - * {@code ranges1} between {@code start} and {@code end}. + * Helper method that returns the [start1, end1, start2, end2, ...] positions + * in {@code targetRange} that map to positions between {@code start} and + * {@code end} in {@code sourceRange}. Note that for a reverse strand mapping + * this will return ranges with end < start. Returns null if no mapped + * positions are found in start-end. * * @param start * @param end - * @param ranges1 - * @param ranges2 - * @param wordLength1 - * @param wordLength2 + * @param sourceRange + * @param targetRange + * @param sourceWordLength + * @param targetWordLength * @return */ - final static List mapBetween(int start, int end, - List ranges1, List ranges2, int wordLength1, - int wordLength2) + final static int[] mapPositions(int start, int end, + List sourceRange, List targetRange, + int sourceWordLength, int targetWordLength) { - /* - * first traverse ranges1 and record count of mapped positions - * to any that overlap start-end - */ - List overlaps = findOverlapPositions(ranges1, start, end); - if (overlaps.isEmpty()) + if (end < start) { - return overlaps; + int tmp = end; + end = start; + start = tmp; } /* - * convert positions to equivalent 'word' positions in ranges + * traverse sourceRange and mark offsets in targetRange + * of any positions that lie in [start, end] */ - mapWords(overlaps, wordLength1, wordLength2); + BitSet offsets = getMappedOffsetsForPositions(start, end, sourceRange, + sourceWordLength, targetWordLength); /* - * walk ranges2 and record the values found at - * the offsets in 'overlaps' + * traverse targetRange and collect positions at the marked offsets */ - List mapped = new ArrayList<>(); - final int s1 = overlaps.size(); - final int s2 = ranges2.size(); - int rangeIndex = 0; - int rangeOffset = 0; - int mappedCount = 0; - - for (int i = 0 ; i < s1 ; i++) - { - /* - * for each range in overlaps, walk ranges2 and record the values - * at the offsets, advancing rangeIndex / Offset - */ - int [] mappedRange = ranges2.get(rangeIndex); - int [] overlap = overlaps.get(s1); - while (mappedCount < overlap[1]) - { - - } - } - - return mapped; + List mapped = getPositionsForOffsets(targetRange, offsets); + + // TODO: or just return the List and adjust calling code to match + return mapped.isEmpty() ? null : MappingUtils.rangeListToArray(mapped); } /** - * Converts the start-end positions (counted from zero) in the {@code ranges} - * list from one word length to another. Start-end positions are expanded if - * necessary to cover a whole word of length {@code wordLength1}. Positions - * are then divided by {@code wordLength1} and multiplied by - * {@code wordLength2} to give equivalent mapped words. - *

- * Put simply, this converts peptide residue positions to the corresponding - * codon ranges, and codons - including partial codons - to the corresponding - * peptide positions; for example + * Scans the list of {@code ranges} for any values (positions) that lie + * between start and end (inclusive), and records the offsets from + * the start of the list as a BitSet. The offset positions are converted to + * corresponding words in blocks of {@code wordLength2}. * * 

-   * [1, 10] with word lengths 3:1 converts (as if bases [0-11]) to [1, 4]
+   * For example:
+   * 1:1 (e.g. gene to CDS):
+   * ranges { [10-20], [31-40] }, wordLengthFrom = wordLength 2 = 1
+   *   for start = 1, end = 9, returns a BitSet with no bits set
+   *   for start = 1, end = 11, returns a BitSet with bits 0-1 set
+   *   for start = 15, end = 35, returns a BitSet with bits 5-15 set
+   * 1:3 (peptide to codon):
+   * ranges { [1-200] }, wordLengthFrom = 1, wordLength 2 = 3
+   *   for start = 9, end = 9, returns a BitSet with bits 24-26 set
+   * 3:1 (codon to peptide):
+   * ranges { [101-150], [171-180] }, wordLengthFrom = 3, wordLength 2 = 1
+   *   for start = 101, end = 102 (partial first codon), returns a BitSet with bit 0 set
+   *   for start = 150, end = 171 (partial 17th codon), returns a BitSet with bit 16 set
+   * 3:1 (circular DNA to peptide):
+   * ranges { [101-150], [21-30] }, wordLengthFrom = 3, wordLength 2 = 1
+   *   for start = 24, end = 40 (spans codons 18-20), returns a BitSet with bits 17-19 set
    *
* - * @param ranges - * @param wordLength1 - * @param wordLength2 + * @param start + * @param end + * @param sourceRange + * @param sourceWordLength + * @param targetWordLength * @return */ - final static void mapWords(List ranges, int wordLength1, - int wordLength2) + protected final static BitSet getMappedOffsetsForPositions(int start, + int end, List sourceRange, int sourceWordLength, + int targetWordLength) { - if (wordLength1 == 1 && wordLength2 == 1) + BitSet overlaps = new BitSet(); + int offset = 0; + final int s1 = sourceRange.size(); + for (int i = 0; i < s1; i++) { - return; // nothing to do here - } - int s = ranges.size(); - for (int i = 0; i < s; i++) - { - int[] range = ranges.get(i); + int[] range = sourceRange.get(i); + final int offset1 = offset; + int overlapStartOffset = -1; + int overlapEndOffset = -1; - /* - * expand range start to the start of a word, - * and convert to wordLength2 - */ - range[0] -= range[0] % wordLength1; - range[0] = range[0] / wordLength1 * wordLength2; + if (range[1] >= range[0]) + { + /* + * forward direction range + */ + if (start <= range[1] && end >= range[0]) + { + /* + * overlap + */ + int overlapStart = Math.max(start, range[0]); + overlapStartOffset = offset1 + overlapStart - range[0]; + int overlapEnd = Math.min(end, range[1]); + overlapEndOffset = offset1 + overlapEnd - range[0]; + } + } + else + { + /* + * reverse direction range + */ + if (start <= range[0] && end >= range[1]) + { + /* + * overlap + */ + int overlapStart = Math.max(start, range[1]); + int overlapEnd = Math.min(end, range[0]); + overlapStartOffset = offset1 + range[0] - overlapEnd; + overlapEndOffset = offset1 + range[0] - overlapStart; + } + } - /* - * similar calculation for range end, adding - * (wordLength2 - 1) for end of mapped word - */ - range[1] -= range[1] % wordLength1; - range[1] = range[1] / wordLength1 * wordLength2; - range[1] += wordLength2 - 1; + if (overlapStartOffset > -1) + { + /* + * found an overlap + */ + if (sourceWordLength != targetWordLength) + { + /* + * convert any overlap found to whole words in the target range + * (e.g. treat any partial codon overlap as if the whole codon) + */ + overlapStartOffset -= overlapStartOffset % sourceWordLength; + overlapStartOffset = overlapStartOffset / sourceWordLength + * targetWordLength; + + /* + * similar calculation for range end, adding + * (wordLength2 - 1) for end of mapped word + */ + overlapEndOffset -= overlapEndOffset % sourceWordLength; + overlapEndOffset = overlapEndOffset / sourceWordLength + * targetWordLength; + overlapEndOffset += targetWordLength - 1; + } + overlaps.set(overlapStartOffset, overlapEndOffset + 1); + } + offset += 1 + Math.abs(range[1] - range[0]); } + return overlaps; } /** - * Helper method that returns a (possibly empty) list of offsets in - * {@code ranges} to subranges that overlap {@code start-end}. The list - * returned holds counts of the number of positions traversed (inclusive) to - * reach the overlapping positions, not the overlapping values. Returns null - * if there are no overlaps. + * Returns a (possibly empty) list of the [start-end] values (positions) at + * offsets in the {@code targetRange} list that are marked by 'on' bits in the + * {@code offsets} bitset. * - * @param ranges - * @param start - * @param end + * @param targetRange + * @param offsets * @return */ - final static List findOverlapPositions(List ranges, - int start, int end) + protected final static List getPositionsForOffsets( + List targetRange, BitSet offsets) { - List positions = new ArrayList<>(); - int pos = 0; - int s = ranges.size(); - for (int i = 0; i < s; i++) + List mapped = new ArrayList<>(); + if (offsets.isEmpty()) { - int[] range = ranges.get(i); - addOverlap(positions, pos, range, start, end); - pos += 1 + Math.abs(range[1] - range[0]); + return mapped; } - return positions; + + /* + * count of positions preceding ranges[i] + */ + int traversed = 0; + + /* + * for each [from-to] range in ranges: + * - find subranges (if any) at marked offsets + * - add the start-end values at the marked positions + */ + final int toAdd = offsets.cardinality(); + int added = 0; + final int s2 = targetRange.size(); + for (int i = 0; added < toAdd && i < s2; i++) + { + int[] range = targetRange.get(i); + added += addOffsetPositions(mapped, traversed, range, offsets); + traversed += Math.abs(range[1] - range[0]) + 1; + } + return mapped; } /** - * A helper method that checks whether {@code range} overlaps - * {@code start-end}, and if so adds the positional offset of the overlap to - * {@code positions}. + * Helper method that adds any start-end subranges of {@code range} that are + * at offsets in {@code range} marked by set bits in overlaps. + * {@code mapOffset} is added to {@code range} offset positions. Returns the + * count of positions added. * - * @param positions - * a list of map offsets to add to - * @param pos - * the number of mapped positions already visited + * @param mapped + * @param mapOffset * @param range - * a from-to range (may be forward or reverse) - * @param start - * position to test for overlap in range - * @param end - * position to test for overlap in range + * @param overlaps * @return */ - final static void addOverlap(List positions, int pos, int[] range, - int start, int end) + final static int addOffsetPositions(List mapped, + final int mapOffset, final int[] range, final BitSet overlaps) { - if (range[1] >= range[0]) + final int rangeLength = 1 + Math.abs(range[1] - range[0]); + final int step = range[1] < range[0] ? -1 : 1; + int offsetStart = 0; // offset into range + int added = 0; + + while (offsetStart < rangeLength) { /* - * forward direction range + * find the start of the next marked overlap offset; + * if there is none, or it is beyond range, then finished */ - if (start <= range[1] && end >= range[0]) + int overlapStart = overlaps.nextSetBit(mapOffset + offsetStart); + if (overlapStart == -1 || overlapStart - mapOffset >= rangeLength) { /* - * overlap + * no more overlaps, or no more within range[] */ - int overlapStart = Math.max(start, range[0]); - int overlapEnd = Math.min(end, range[1]); - positions - .add(new int[] - { 1 + overlapStart - range[0], 1 + overlapEnd - range[0] }); + return added; } - } - else - { + overlapStart -= mapOffset; + /* - * reverse direction range + * end of the overlap range is just before the next clear bit; + * restrict it to end of range if necessary; + * note we may add a reverse strand range here (end < start) */ - if (start <= range[0] && end >= range[1]) - { - /* - * overlap - */ - int overlapStart = Math.max(start, range[1]); - int overlapEnd = Math.min(end, range[0]); - positions - .add(new int[] - { 1 + range[0] - overlapStart, 1 + range[0] - overlapEnd }); - } + int overlapEnd = overlaps.nextClearBit(mapOffset + overlapStart + 1); + overlapEnd = (overlapEnd == -1) ? rangeLength - 1 + : Math.min(rangeLength - 1, overlapEnd - mapOffset - 1); + int startPosition = range[0] + step * overlapStart; + int endPosition = range[0] + step * overlapEnd; + mapped.add(new int[] { startPosition, endPosition }); + offsetStart = overlapEnd + 1; + added += Math.abs(endPosition - startPosition) + 1; } + + return added; + } + + /* + * 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]); } }