Bedtk: finding interval overlap with implicit interval tree
Heng Li, Jiazhen Rong
Abstract
SUMMARY: We present bedtk, a new toolkit for manipulating genomic intervals in the BED format. It supports sorting, merging, intersection, subtraction and the calculation of the breadth of coverage. Bedtk uses implicit interval tree, a data structure for fast interval overlap queries. It is several to tens of times faster than existing tools and tends to use less memory. AVAILABILITY AND IMPLEMENTATION: The source code is available at https://github.com/lh3/bedtk.
Topics & Concepts
Interval (graph theory)Computer scienceSortingSubtractionIntersection (aeronautics)Tree (set theory)Code (set theory)Interval treeAlgorithmTheoretical computer scienceTree structureData structureProgramming languageBinary treeArithmeticMathematicsSet (abstract data type)CombinatoricsAerospace engineeringEngineeringAlgorithms and Data CompressionMusic and Audio ProcessingEvolutionary Algorithms and Applications