Skip to content
Augmented interval list (AIList): a novel data structure for efficient genomic interval search
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
docs
docs_jupyter
example_data add docs Jan 8, 2019
requirements Create requirements-docs.txt Apr 30, 2019
src Update Jul 16, 2019
src_AITree
src_NCList
src_py
.gitignore
LICENSE.md
Makefile Refine ... Jun 30, 2019
README.md
mkdocs.yml

README.md

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

Updates

Augmented interval list (AIList) is a new data structure for enumerating intersections between a query interval q and an interval set R. It is constructed by first sorting R as a list by the interval start coordinate, then decomposing it into a few flattened components (sublists), and then augmenting each sublist with the running maximum interval end. It nearly minimizes the search space with ignorable additional cost, and thus optimizes the interval search. A preliminary implementation of AIList showed that AIList is several times faster than interval tree, NCList and BEDTools, see ailist_paper. The complete documentation can be found at ailist_doc.

Since the first release of our ailist_paper, a new representative implementation of the ITree is developed by Dr Heng Li (Li's ITree or LITree), which showed significant improvement over other implementations of the ITree and it achieves similar efficiency of the original implementation of AIList on a few datasets. Here we re-implemented AIList by following the superior treatments of LITree on sorting and data loading (for which we are grateful to Dr Li) and updated the results for many more datasets. We also analyzed the results with emphasis on the understanding of the underline data structure differences among AIList, NCList, and ITrees.

Test results

Nine datasets in the following table are used for the test. The first 7 datasets are used in our original paper and the last two are used by LITree. They are all available here. A flat interval list (null interval list) can be treated as a simple list, so only a sinlge binary search is needed for a query. Dataset 1 is flat (1 total list with no sublist) and datasets 2 and 7 are near flat (only one sublist).

Dataset# Name(.bed) size(x1000) non-flatness
0 chainRn4 2,351 6
1 fBrain 199 1
2 exons 439 2
3 chainOrnAna1 1,957 6
4 chainVicPac2 7,684 8
5 chainXenTro3Link 50,981 7
6 chainMonDom5Link 128,187 7
7 ex-anno 1,194 2
8 ex-rna 9,945 7

The re-implemented AIList has the same size of core data members as LITree and the time for the construction and result output of AIList is almost the same as that of the LITree, so the difference is on the query speed, which is the purpose of this comparison.

The command for AIList:

time ailist dataset1.bed dataset2.bed > /dev/null

For cgranges (LITree):

time bedcov-cr dataset1.bed dataset2.bed -c >/dev/null

The first BED file is loaded into RAM and constructed as a 'database', intervals in the second file are used as queries against the 'database' as shown here for columns 2 and 3; columns 4 and 5 reverses the order of the two datasets.

Datasets AIList LITree AIList,r LITree,r
0, 1 0.441s 0.440s 0.774s 0.882s
0, 2 0.538s 0.595s 0.805s 0.940s
0, 3 2.124s 3.352s 2.598s 5.777s
0, 4 7.512s 14.102s 6.573s 11.430
0, 5 26.499s 43.498s 39.562s 1m10.207s
0, 6 50.551s 1m14.538s 1m20.744s 2m24.714s
0, 7 0.955s 1.089s 0.939s 1.052s
0, 8 3.382s 4.006s 9.430s 9.867s
7, 8 6.868s 6.967s 3.198s 3.848s
3, 6 2m20.725s 5m36.132s 1m17.778s 2m7.386s

Understanding the underline data structures of AIList and LITree

  • As an implementation of ITree, LITree (cgranges) gets the best out of the ITree data structure: 1) it gets rid of the pointers to child nodes, so it minimizes the data storage (memory); 2) it is natually balanced, so it gets rid of the separated and costy tree balancing processing; 3) cgranges sorts the whole list (array) before indexing, so it breaks down long coverage (see ailist_paper) when indexing the tree into branches and reduces the search space, and it also maintains a unique tree representation (in conventional ITree for the same set of intervals, the final tree structure is dependent on the order of the intervals being added and on the balancing processing). So cgranges is much better than other implementations of the ITree data structure. The limitation is on the underline data structure: it only partially reduces the search space.

  • The above test results show that ailist is generally faster than LITree, which is expected from their underline data structures. For flat or nearly flat datasets (#1, #2 and #7), they are close; for non-flat datasets (#0, #3, etc), AIList is significantly faster than LITree. For datasets 3 and 6, the actual query time is 105s for AIList and 296s for LITree, which accounts for a 2.8x difference in query efficiency. As a data structure aimed to minimize the search space, i.e., to reduce the search space to the level of a flat list, NCList does it completely but with heavily additional cost (extra storage, extra binary search on sub-lists, see ailist_paper), LITree achieves that partially with ignorable additional cost, and AIList does it nearly completely with ignorable cost.

Use ailist in python

A Python wrapper of the AIList c code is included in folder src_py and the search is very fast (~3 times less efficient than AIList c code). To install after cloning this repo:

cd AIList/src_py
python setup.py install

A small python program ailist_test.py is included, which can be used this way:

python ailist_test.py test1.bed test2.bed
You can’t perform that action at this time.