Augmented Interval List: a novel data structure for efficient genomic interval search.

ABSTRACT:

Motivation

Genomic data is frequently stored as segments or intervals. Because this data type is so common, interval-based comparisons are fundamental to genomic analysis. As the volume of available genomic data grows, developing efficient and scalable methods for searching interval data is necessary.

Results

We present a new data structure, the Augmented Interval List (AIList), to enumerate intersections between a query interval q and an interval set R. An AIList is constructed by first sorting R as a list by the interval start coordinate, then decomposing it into a few approximately flattened components (sublists), and then augmenting each sublist with the running maximum interval end. The query time for AIList is O(log2N+n+m), where n is the number of overlaps between R a

SUBMITTER: Feng J 

PROVIDER: S-EPMC6901075 | biostudies-literature | 2019 Dec

REPOSITORIES: biostudies-literature