[BioC] Exclude overlapping intervals
Hervé Pagès
hpages at fhcrc.org
Fri Dec 14 22:30:50 CET 2012
Hi Malcolm,
On 12/14/2012 11:24 AM, Cook, Malcolm wrote:
> Hermann, did you get the solution you needed out of this?
>
> Herve, please check out my notes below. I think you will be amused/intersted....
>
> .On 12/13/2012 12:00 PM, Cook, Malcolm wrote:
> .> Hi, yall,
> .>
> .> I'm thinking Hermann is looking where the coverage of gr is 1, like this:
> .>
> .> library(functional)
> .> lapply(coverage(gr)==1,Compose(as.vector,whichAsIRanges))
> .> $chr1
> .> NormalIRanges of length 5
> .> start end width
> .> [1] 4 10 7
> .> [2] 12 19 8
> .> [3] 45 54 10
> .> [4] 81 100 20
> .> [5] 105 200 96
> .>
> .>
> .> ... which answers the question but the data is improperly shaped.
> .>
> .> We can also think of this as where gr does not overlap itself, and the result is properly shaped, viz:
> .>> grd<-disjoin(gr)
> .>> grd[1==countOverlaps(grd,gr)]
> .> GRanges with 5 ranges and 0 metadata columns:
> .> seqnames ranges strand
> .> <Rle> <IRanges> <Rle>
> .> [1] chr1 [ 4, 10] *
> .> [2] chr1 [ 12, 19] *
> .> [3] chr1 [ 45, 54] *
> .> [4] chr1 [ 81, 100] *
> .> [5] chr1 [105, 200] *
> .> ---
> .> seqlengths:
> .> chr1
> .> NA
> .>
> .> So, which way is 'best' for performance?
> .
> .Note that the 2 solutions are not equivalent if the ranges are
> .stranded: the former will ignore the strand whereas the latter
> .will consider it. Even if the ranges are not stranded (like in
> .your example), you still need to reduce() the result of the latter
> .in order to get exactly the same set of ranges as with the former.
> .
> .2 alternatives to solution 1 with result properly shaped:
> .
> .** Sol 1b:
> .
> . irl <- IRangesList(lapply(coverage(gr) == 1L, as, "IRanges"))
> . gr1b <- as(irl, "GRanges")
> .
> .** Sol 1c (using slice):
> .
> . gr1c <- as(slice(coverage(gr), lower=1L, upper=1L), "GRanges")
> .
> .Sol 1b seems to be the fastest.
> .
>
> Herve, thanks for these observations re: stranded and the need to reduce the results of my method 1.
> In the most general case I agree, you are right, and the strand preserving method should be:
>
> grd<-disjoin(gr)
> reduce(grd[1==countOverlaps(grd,gr)])
>
> Trying to appreciate and simplify your soln1, I rewrote it as a one-liner, thusly:
>
> as(as(coverage(gr) == 1L,'IRangesList'),'GRanges')
>
> which prompts me to abstract as follows:
>
>> setAs('RleList','GRanges',
> function(from) {
> as(as(from,'IRangesList'),'GRanges')
> })
There is already a coercion method for going from RleList to GRanges
and it does something different:
> rlelist
SimpleRleList of length 3
$chr1
logical-Rle of length 1000 with 2 runs
Lengths: 4 996
Values : TRUE FALSE
$chr2
logical-Rle of length 2000 with 3 runs
Lengths: 1 1 1998
Values : FALSE TRUE FALSE
$chr3
logical-Rle of length 1500 with 3 runs
Lengths: 6 1 1493
Values : FALSE TRUE FALSE
> as(rlelist, "GRanges")
GRanges with 8 ranges and 1 metadata column:
seqnames ranges strand | score
<Rle> <IRanges> <Rle> | <logical>
[1] chr1 [1, 4] * | TRUE
[2] chr1 [5, 1000] * | FALSE
[3] chr2 [1, 1] * | FALSE
[4] chr2 [2, 2] * | TRUE
[5] chr2 [3, 2000] * | FALSE
[6] chr3 [1, 6] * | FALSE
[7] chr3 [7, 7] * | TRUE
[8] chr3 [8, 1500] * | FALSE
---
seqlengths:
chr1 chr2 chr3
1000 2000 1500
Yours is probably more useful on *logical*-RleList's but the current one
is more general because it works on any RleList.
One of the challenges of implementing a good coercion system between
the many classes we have is to pick up the "most natural" semantic
for a given coercion. However, what seems to be the "most natural"
is necessarily biased by the context and by people's use-cases and
personal backgrounds. This is a situation where use-case driven
semantic is not necessarily helping. What is more helpful for
choosing a semantic is to look at properties like:
(a) Consistency with coercion between ordinary vectors.
(b) Are two-step coercions equivalent to the corresponding 1-step
coercion? That is,
is 'as(as(x, "B"), "C")' identical to 'as(x, "C")'
for any intermediate representation "B"?
This might be hard to achieve though. For example, right
now, doing logical-RleList -> RangedData -> GRanges doesn't produce
the same as doing logical-RleList -> IRangesList -> GRanges.
(c) No-loss/reversible coercion, that is, if 'class(x)' is "A",
and "B" is a "higher-level" class than "A", coercing 'x' to
"B" should try to preserve all the information in 'x', and
coercing back to "A" should give back 'x' (maybe modulo some
reordering).
I don't think the coercion system we have in the IRanges/GenomicRanges
infrastructure with its 150+ coercion methods currently satisfies (a),
(b), (c), but I'm sure we could improve it.
I'll modify the current coercion from RleList to GRanges to treat
logical-RleList in the way you propose if nobody objects.
>
> allowing to express the problem most perspicuously like this:
>
>> as(coverage(gr) == 1L,'GRanges')
> GRanges with 5 ranges and 0 metadata columns:
> seqnames ranges strand
> <Rle> <IRanges> <Rle>
> [1] chr1 [ 4, 10] *
> [2] chr1 [ 12, 19] *
> [3] chr1 [ 45, 54] *
> [4] chr1 [ 81, 100] *
> [5] chr1 [105, 200] *
> ---
> seqlengths:
> chr1
> NA
>>
>
> Is this in the spirit? Is my SetAs making assumptions it should not?
>
> Opinions anyone?
>
>
> Oh! HEY! During this exploration, I discover to my great astonishment that `==` is not symetric at least as regards to name preservation !!!!!
Unfortunately there is no way it can be symmetric with regards to
name preservation.
Now what we should try to have is more consistency with name
preservation on ordinary vectors where the rules *seem* to be
(I couldn't find them documented in the man page for ==):
(1) The longest operand wins.
(2) In case of tie (i.e. same length), the operand with names wins.
(3) In case of tie (i.e. both have names), the left operand wins.
Note that there is no reason those rules would be only for ==, they
could apply to any vectorized binary operator that does recycling of
the shortest operand (I only checked they apply to all the basic
arithmetic and comparison operators in base R).
>
>> names(1==coverage(gr))
> NULL
>> names(coverage(gr)==1)
> [1] "chr1"
>
> Is there an explanation for this antisymetry? Is this to be expected? Should it be remedied? Is this another thread?
Clearly we are not doing (1), (2), (3) but we probably should. I'll put
this on my list.
>
> I am SURE that I am not the only one to have gotten bitten by this in the past. In fact, I think that I have run up in the past and have not realized that switch the order of the operands 'fixes' the problem.
>
> As a result of this issue, for instance, my elegant (?) abstraction won't work when the comparison is reversed and will generate CRYPTIC error messages:
>
> as(1L==coverage(gr),'GRanges')
> Error in function (classes, fdef, mtable) (from #3) :
> unable to find an inherited method for function "Rle", for signature "NULL", "missing"
>
> Prompting me to change my setAs thusly:
>
> setAs('RleList','GRanges',
> function(from) {
> if (is.null(names(from))) stop(
> '\nHey, the parameter `from` is un-named, thus the segnames of any hoped-for `GRanges` are un-assignable!\n'
> ,'Possible workaround: reverse the order of a comparison which produced `from` (if any)!\n'
> ,'Example: re-write "1L==coverage(gr)" as "coverage(gr)==1\n'
> ,'Best: fix the up-stream bug that `==` is not symetric w.r.t. names'
> )
> as(as(from,'IRangesList'),'GRanges')
> })
>
> Or, or, or?
If the RleList is not named what we usually do is create automatic
chromosome names 1, 2, 3, etc...:
> as(unname(rlelist), "GRanges")
GRanges with 8 ranges and 1 metadata column:
seqnames ranges strand | score
<Rle> <IRanges> <Rle> | <logical>
[1] 1 [1, 4] * | TRUE
[2] 1 [5, 1000] * | FALSE
[3] 2 [1, 1] * | FALSE
[4] 2 [2, 2] * | TRUE
[5] 2 [3, 2000] * | FALSE
[6] 3 [1, 6] * | FALSE
[7] 3 [7, 7] * | TRUE
[8] 3 [8, 1500] * | FALSE
---
seqlengths:
1 2 3
1000 2000 1500
Thanks for all the valuable feedback!
H.
>
> ~Malcolm
>
>
>
> .H.
> .
> .>
> .> Best,
> .>
> .> ~Malcolm
> .>
> .>
> .>> -----Original Message-----
> .>> From: bioconductor-bounces at r-project.org [mailto:bioconductor-bounces at r-project.org] On Behalf Of Hervé Pagès
> .>> Sent: Thursday, December 13, 2012 12:03 PM
> .>> To: Hermann Norpois
> .>> Cc: Michael Lawrence; bioconductor at r-project.org
> .>> Subject: Re: [BioC] Exclude overlapping intervals
> .>>
> .>> Hi Hermann,
> .>>
> .>> On 12/13/2012 09:33 AM, Hermann Norpois wrote:
> .>>> As both methods did not work ...
> .>>>
> .>>> 1) > gr[!gr %in% excluded] gr[!gr %in% excluded]
> .>>> Fehler in gr[!gr %in% excluded] :
> .>>> Fehler bei der Auswertung des Argumentes 'i' bei der Methodenauswahl
> .>>> für Funktion '[': Fehler in gr %in% excluded :
> .>>> Fehler bei der Auswertung des Argumentes 'table' bei der Methodenauswahl
> .>>> für Funktion '%in%': Fehler: Objekt 'excluded' nicht gefunden
> .>>
> .>> My limited knowledge of Goethe's tongue tells me that the 'excluded'
> .>> object was not found. Of course you need to provide a GRanges object,
> .>> call it 'excluded' or 'gr2', that contains the ranges that you want to
> .>> remove from 'gr' (based on overlaps).
> .>>
> .>> Using 'gr' itself in place of 'gr2' to remove ranges in 'gr' that
> .>> overlap with other ranges in 'gr' would not produce what you want
> .>> though, because that would exclude everything:
> .>>
> .>> > gr[!gr %in% gr]
> .>> GRanges with 0 ranges and 2 metadata columns:
> .>> seqnames ranges strand | score GC
> .>> <Rle> <IRanges> <Rle> | <integer> <numeric>
> .>> ---
> .>> seqlengths:
> .>> chr1 chr2 chr3
> .>> 1000 2000 1500
> .>>
> .>> Try this instead:
> .>>
> .>> gr[countOverlaps(gr, gr) <= 1L]
> .>>
> .>> Cheers,
> .>> H.
> .>>
> .>>>
> .>>>> setdiff (gr)
> .>>> Fehler in as.vector(x) :
> .>>> Keine Methode um diese S4 Klasse in einen Vektor zu verwandeln
> .>>>
> .>>> ... I am posting my data:
> .>>>
> .>>>> gr
> .>>> GRanges with 5 ranges and 0 metadata columns:
> .>>> seqnames ranges strand
> .>>> <Rle> <IRanges> <Rle>
> .>>> [1] chr1 [ 4, 10] *
> .>>> [2] chr1 [ 12, 19] *
> .>>> [3] chr1 [ 45, 80] *
> .>>> [4] chr1 [ 55, 100] *
> .>>> [5] chr1 [105, 200] *
> .>>> ---
> .>>> seqlengths:
> .>>> chr1
> .>>> NA
> .>>>> dput (gr)
> .>>> new("GRanges"
> .>>> , seqnames = new("Rle"
> .>>> , values = structure(1L, .Label = "chr1", class = "factor")
> .>>> , lengths = 5L
> .>>> , elementMetadata = NULL
> .>>> , metadata = list()
> .>>> )
> .>>> , ranges = new("IRanges"
> .>>> , start = c(4L, 12L, 45L, 55L, 105L)
> .>>> , width = c(7L, 8L, 36L, 46L, 96L)
> .>>> , NAMES = NULL
> .>>> , elementType = "integer"
> .>>> , elementMetadata = NULL
> .>>> , metadata = list()
> .>>> )
> .>>> , strand = new("Rle"
> .>>> , values = structure(3L, .Label = c("+", "-", "*"), class = "factor")
> .>>> , lengths = 5L
> .>>> , elementMetadata = NULL
> .>>> , metadata = list()
> .>>> )
> .>>> , elementMetadata = new("DataFrame"
> .>>> , rownames = NULL
> .>>> , nrows = 5L
> .>>> , listData = structure(list(), .Names = character(0))
> .>>> , elementType = "ANY"
> .>>> , elementMetadata = NULL
> .>>> , metadata = list()
> .>>> )
> .>>> , seqinfo = new("Seqinfo"
> .>>> , seqnames = "chr1"
> .>>> , seqlengths = NA_integer_
> .>>> , is_circular = NA
> .>>> , genome = NA_character_
> .>>> )
> .>>> , metadata = list()
> .>>> )
> .>>>
> .>>> Thanks
> .>>> Hermann
> .>>>
> .>>> 2012/12/13 Michael Lawrence <lawrence.michael at gene.com>
> .>>>
> .>>>> Something like:
> .>>>>
> .>>>> gr[!gr %in% excluded]
> .>>>>
> .>>>> Another option is setdiff() but note that will generate a new set of
> .>>>> sorted, non-overlapping, non-adjacent ("normal") ranges.
> .>>>>
> .>>>> Michael
> .>>>>
> .>>>>
> .>>>> On Thu, Dec 13, 2012 at 9:01 AM, Hermann Norpois <hnorpois at googlemail.com>wrote:
> .>>>>
> .>>>>> Hello,
> .>>>>>
> .>>>>> having a GRanges object I was looking for a function to exclude all
> .>>>>> overlapping intervals. So I get exclusively intervals that do not overlap.
> .>>>>> But I did not find a proper function. Has anybody an idea?
> .>>>>> Thanks
> .>>>>> Hermann
> .>>>>>
> .>>>>> [[alternative HTML version deleted]]
> .>>>>>
> .>>>>> _______________________________________________
> .>>>>> Bioconductor mailing list
> .>>>>> Bioconductor at r-project.org
> .>>>>> https://stat.ethz.ch/mailman/listinfo/bioconductor
> .>>>>> Search the archives:
> .>>>>> http://news.gmane.org/gmane.science.biology.informatics.conductor
> .>>>>>
> .>>>>
> .>>>>
> .>>>
> .>>> [[alternative HTML version deleted]]
> .>>>
> .>>>
> .>>>
> .>>> _______________________________________________
> .>>> Bioconductor mailing list
> .>>> Bioconductor at r-project.org
> .>>> https://stat.ethz.ch/mailman/listinfo/bioconductor
> .>>> Search the archives: http://news.gmane.org/gmane.science.biology.informatics.conductor
> .>>>
> .>>
> .>> --
> .>> Hervé Pagès
> .>>
> .>> Program in Computational Biology
> .>> Division of Public Health Sciences
> .>> Fred Hutchinson Cancer Research Center
> .>> 1100 Fairview Ave. N, M1-B514
> .>> P.O. Box 19024
> .>> Seattle, WA 98109-1024
> .>>
> .>> E-mail: hpages at fhcrc.org
> .>> Phone: (206) 667-5791
> .>> Fax: (206) 667-1319
> .>>
> .>> _______________________________________________
> .>> Bioconductor mailing list
> .>> Bioconductor at r-project.org
> .>> https://stat.ethz.ch/mailman/listinfo/bioconductor
> .>> Search the archives: http://news.gmane.org/gmane.science.biology.informatics.conductor
> .
> .--
> .Hervé Pagès
> .
> .Program in Computational Biology
> .Division of Public Health Sciences
> .Fred Hutchinson Cancer Research Center
> .1100 Fairview Ave. N, M1-B514
> .P.O. Box 19024
> .Seattle, WA 98109-1024
> .
> .E-mail: hpages at fhcrc.org
> .Phone: (206) 667-5791
> .Fax: (206) 667-1319
>
--
Hervé Pagès
Program in Computational Biology
Division of Public Health Sciences
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N, M1-B514
P.O. Box 19024
Seattle, WA 98109-1024
E-mail: hpages at fhcrc.org
Phone: (206) 667-5791
Fax: (206) 667-1319
More information about the Bioconductor
mailing list