Skip to main content

Algorithms and data structures for my Python projects

Project description


Algorithms and data structures for my Python projects.

Build Status

Interval tree

Interval tree is a data structure for holding intervals and to allow efficiently find intervals that overlap with given interval or point. Read more on Wikipedia.

Implementation note

This implementation uses half-open intervals, where begin coordinate is excluded. Half-open intervals are used in e.g. BED genomic format.

The current implementation needs to rebuild the tree after each insert, hence the tree is not efficient for using in read/write fashion.


  • implement your custom interval object while extending Interval. Two properties need to be overwritten:
    • begin - 0-based (excluded) begin coordinate of the interval
    • end - 0-based (included) end coordinate of the interval
      from ddalg.model import Interval
      class YourInterval(Interval):
        def __init__(self, begin: int, end: int):
          self._begin = begin
          self._end = end
          # anything else
        def begin(self):
          return self._begin
        def end(self):
          return self._end
  • create a collection of your intervals and store them in the interval tree:
    from ddalg.itree import IntervalTree
    itree = IntervalTree([YourInterval(0, 3), YourInterval(1, 4)])
    # ... 
  • query itree:
    • using 1-based position:

      returns (0,3)

    • using half-open interval coordinates:
      itree.get_overlaps(0, 1) 

      returns (0,3), effectively the same query as above

    • for intervals with minimal required coverage
      itree.fuzzy_query(0, 1, coverage=.90)

      return intervals with >=.9 overlap with respect to query coordinates

    • for intervals with minimal jaccard index
      itree.jaccard_query(0, 1, min_jaccard=.90)

      return intervals having jaccard_index>=.9 with respect to query coordinates

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

ddalg-0.0.3.post0.tar.gz (8.6 kB view hashes)

Uploaded source

Built Distribution

ddalg-0.0.3.post0-py3.6.egg (27.1 kB view hashes)

Uploaded 3 6

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page