ddalg

为我的Python项目设计的算法和数据结构。

区间树

区间树是一种用于存储区间并允许高效地找到与给定区间或点重叠的区间的数据结构。更多内容请参阅维基百科。

实现说明

此实现使用半开区间，其中起始坐标被排除。半开区间用于例如BED基因组格式。

当前实现需要在每次插入后重建树，因此该树在用于读写模式下效率不高。

用法

• 在扩展Interval的同时实现您的自定义区间对象。需要重写两个属性
  • begin - 区间0-based（排除）起始坐标
  • end - 区间0-based（包含）结束坐标

    from ddalg.model import Interval
    
    class YourInterval(Interval):
    
      def __init__(self, begin: int, end: int):
        self._begin = begin
        self._end = end
        # anything else
    
      @property
      def begin(self):
        return self._begin
    
      @property
      def end(self):
        return self._end
    

• 创建您的区间集合并将它们存储在区间树中

  from ddalg.itree import IntervalTree
   
  itree = IntervalTree([YourInterval(0, 3), YourInterval(1, 4)])
  # ... 
  

• 查询itree
  • 使用1-based 位置

    itree.search(1)
    

    返回(0,3)

  • 使用半开区间坐标

    itree.get_overlaps(0, 1) 
    

    返回(0,3)，实际上是上述查询的相同查询

  • 对于具有最小所需覆盖率的区间

    itree.fuzzy_query(0, 1, coverage=.90)
    

    返回与查询坐标重叠>=.9的区间

  • 对于具有最小杰卡德指数的区间

    itree.jaccard_query(0, 1, min_jaccard=.90)
    

    返回与查询坐标相比杰卡德指数>=.9的区间