AbstractIntervalTree

[phaverty]

Would you be open to having an AbstractIntervalTree? I'd like to experiment with a GenomicRanges type and I'd like to inherit from AbstractIntervalTree.

[dcjones]

I'm open to this. Is there a common interface for children of AbstractIntervalTree that you have in mind?

[phaverty]

I'd like to see it implement the Set API for exact matches and also the
ranges operations from IRanges. I'm happy to submit a PR with the full set,
but this includes an Interval API that parallels the Set API with overlap
replacing equality. It also contains things like "nearest".

IRanges etc. also implement the Vector API (length, setindex, getindex,
etc.). The Vector part might not be what you had in mind. IRanges has both
a linear and a tree representation, which has some convenience/complexity
trade-offs. Importantly, it lets you map specific ranges to rows of a
DataFrame.

I submitted a few tiny PRs to IntervalTree that fill in what I thought was
missing functionality. I hope you find them useful.

Pete

---

Peter M. Haverty, Ph.D.
Genentech, Inc.
phaverty@gene.com

On Tue, Jun 9, 2015 at 7:03 AM, Daniel C. Jones notifications@github.com
wrote:

I'm open to this. Is there a common interface for children of
AbstractIntervalTree that you have in mind?

Reply to this email directly or view it on GitHub
#10 (comment)
.

[phaverty]

, but for now, I'd be stoked just to have the AbstractIntervalTree type and
to have the current IntervalTree methods switched to AbstractIntervalTree.

Pete

---

Peter M. Haverty, Ph.D.
Genentech, Inc.
phaverty@gene.com

On Tue, Jun 9, 2015 at 11:13 AM, Peter Haverty phaverty@gene.com wrote:

I'd like to see it implement the Set API for exact matches and also the
ranges operations from IRanges. I'm happy to submit a PR with the full set,
but this includes an Interval API that parallels the Set API with overlap
replacing equality. It also contains things like "nearest".

IRanges etc. also implement the Vector API (length, setindex, getindex,
etc.). The Vector part might not be what you had in mind. IRanges has both
a linear and a tree representation, which has some convenience/complexity
trade-offs. Importantly, it lets you map specific ranges to rows of a
DataFrame.

I submitted a few tiny PRs to IntervalTree that fill in what I thought was
missing functionality. I hope you find them useful.

Pete

---

Peter M. Haverty, Ph.D.
Genentech, Inc.
phaverty@gene.com

On Tue, Jun 9, 2015 at 7:03 AM, Daniel C. Jones notifications@github.com
wrote:

I'm open to this. Is there a common interface for children of
AbstractIntervalTree that you have in mind?

Reply to this email directly or view it on GitHub
#10 (comment)
.

[dcjones]

Sorry I missed your PRs. They're merged now.

A problem with implementing a Set API is that the implementation here is not a set. It's perfectly valid to insert two identical intervals. We could have getindex just return the first match in such a case, or it could return an iterator over all matching intervals.

But I wonder if a more fundamental operation isn't intersect(target::AbstractIntervalTree, query::AbstractInterval) returning an array or iterator of intervals in target that intersect query.

We might also call the base class AbstractIntervalCollection or something, since it need not be a tree.

[phaverty]

No worries on the PRs. You are welcome to ignore the ones you don't like,
of course. It's your show. Thanks for merging them.

Good point about the AbstractIntervalCollection. I've been mulling over a
GenomePosition type that would just be a vector with some metadata, so that
would fit your new supertype.

For GenomePosition (and GenomicRanges) I was thinking of converting all the
positions to genome position by adding an offset into the concatenated,
linear genome. That would give a single tree for easy intersection,
sorting, etc.. I'd keep the offsets in the object for converting back to
chr/start/stop coordinates, but I don't think one would want to do that
often, actually. I use this linear genome position thing for plotting in
the genoset package. The genome offset metadata would be immutable, and
intersect operations would require two object to have identical genome
metadata.

Yes, I agree that the intersect operation is the key operation for this
family of types.

Pete

---

Peter M. Haverty, Ph.D.
Genentech, Inc.
phaverty@gene.com

On Wed, Jun 10, 2015 at 7:40 AM, Daniel C. Jones notifications@github.com
wrote:

Sorry I missed your PRs. They're merged now.

A problem with implementing a Set API is that the implementation here is
not a set. It's perfectly valid to insert two identical intervals. We could
have getindex just return the first match in such a case, or it could
return an iterator over all matching intervals.

But I wonder if a more fundamental operation isn't intersect(target::AbstractIntervalTree,
query::AbstractInterval) returning an array or iterator of intervals in
target that intersect query.

We might also call the base class AbstractIntervalCollection or
something, since it need not be a tree.

Reply to this email directly or view it on GitHub
#10 (comment)
.

[blahah]

Just as an aside, while @dcjones has done all the (phenomenal) work on this repo, this is technically nobody's show. BioJulia is a community endeavour and we would love to have you on board @phaverty.

[phaverty]

I have released GenomicVectors which implements my idea for storing ranges along the linearized genome.