Skip to main content

Nested containment list

Deprecation notice

While I'll continue maintaining this library I suggest you change to ruranges which is a more lightweight and faster library with many more operations than NCLS.

NCLS

Build Status PyPI version

The Nested Containment List is a datastructure for interval overlap queries, like the interval tree. It is usually an order of magnitude faster than the interval tree both for building and query lookups.

The implementation here is a revived version of the one used in the now defunct PyGr library, which died of bitrot. I have made it less memory-consuming and created wrapper functions which allows batch-querying the NCLS for further speed gains.

It was implemented to be the cornerstone of the PyRanges project, but I have made it available to the Python community as a stand-alone library. Enjoy.

Original Paper: https://academic.oup.com/bioinformatics/article/23/11/1386/199545 Cite: http://dx.doi.org/10.1093/bioinformatics/btz615

Cite

If you use this library in published research cite

http://dx.doi.org/10.1093/bioinformatics/btz615

Install

pip install ncls

Usage

from ncls import NCLS

import pandas as pd

starts = pd.Series(range(0, 5))
ends = starts + 100
ids = starts

subject_df = pd.DataFrame({"Start": starts, "End": ends}, index=ids)

print(subject_df)
#    Start  End
# 0      0  100
# 1      1  101
# 2      2  102
# 3      3  103
# 4      4  104

ncls = NCLS(starts.values, ends.values, ids.values)

# python API, slower
it = ncls.find_overlap(0, 2)
for i in it:
    print(i)
# (0, 100, 0)
# (1, 101, 1)

starts_query = pd.Series([1, 3])
ends_query = pd.Series([52, 14])
indexes_query = pd.Series([10000, 100])

query_df = pd.DataFrame({"Start": starts_query.values, "End": ends_query.values}, index=indexes_query.values)

query_df
#        Start  End
# 10000      1   52
# 100        3   14


# everything done in C/Cython; faster
l_idxs, r_idxs = ncls.all_overlaps_both(starts_query.values, ends_query.values, indexes_query.values)
l_idxs, r_idxs
# (array([10000, 10000, 10000, 10000, 10000,   100,   100,   100,   100,
#          100]), array([0, 1, 2, 3, 4, 0, 1, 2, 3, 4]))

print(query_df.loc[l_idxs])
#        Start  End
# 10000      1   52
# 10000      1   52
# 10000      1   52
# 10000      1   52
# 10000      1   52
# 100        3   14
# 100        3   14
# 100        3   14
# 100        3   14
# 100        3   14
print(subject_df.loc[r_idxs])
#    Start  End
# 0      0  100
# 1      1  101
# 2      2  102
# 3      3  103
# 4      4  104
# 0      0  100
# 1      1  101
# 2      2  102
# 3      3  103
# 4      4  104

# return intervals in python (slow/mem-consuming)
intervals = ncls.intervals()
intervals
# [(0, 100, 0), (1, 101, 1), (2, 102, 2), (3, 103, 3), (4, 104, 4)]

There is also an experimental floating point version of the NCLS called FNCLS. See the examples folder.

Benchmark

Test file of 100 million intervals (created by subsetting gencode gtf with replacement):

Library Function Time (s) Memory (GB)
bx-python build 161.7 2.5
ncls build 3.15 0.5
bx-python overlap 148.4 4.3
ncls overlap 7.2 0.5

Building is 50 times faster and overlap queries are 20 times faster. Memory usage is one fifth and one ninth.

Original paper

Alexander V. Alekseyenko, Christopher J. Lee; Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases, Bioinformatics, Volume 23, Issue 11, 1 June 2007, Pages 1386–1393, https://doi.org/10.1093/bioinformatics/btl647

Metadata

Release files for ncls 0.0.71

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for ncls 0.0.71
File Size Uploaded Provenance Actions
ncls-0.0.71.tar.gz 651.2 kB Without provenance Details for ncls-0.0.71.tar.gz

Built distributions (wheels)

Table of built distributions (wheels) for ncls 0.0.71
File Actions
ncls-0.0.71-cp312-cp312-musllinux_1_1_x86_64.whl CPython 3.12 CPython 3.12 Linux musl 1.1+ x86-64 Details for ncls-0.0.71-cp312-cp312-musllinux_1_1_x86_64.whl
ncls-0.0.71-cp312-cp312-musllinux_1_1_i686.whl CPython 3.12 CPython 3.12 Linux musl 1.1+ x86-32 Details for ncls-0.0.71-cp312-cp312-musllinux_1_1_i686.whl
ncls-0.0.71-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl CPython 3.12 CPython 3.12 Linux glibc 2.17+ x86-64 Details for ncls-0.0.71-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
ncls-0.0.71-cp312-cp312-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl CPython 3.12 CPython 3.12 Linux glibc 2.12+ x86-32, Linux glibc 2.17+ x86-32 Details for ncls-0.0.71-cp312-cp312-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl
ncls-0.0.71-cp312-cp312-macosx_11_0_arm64.whl CPython 3.12 CPython 3.12 macOS 11.0+ ARM64 Details for ncls-0.0.71-cp312-cp312-macosx_11_0_arm64.whl
ncls-0.0.71-cp311-cp311-musllinux_1_1_x86_64.whl CPython 3.11 CPython 3.11 Linux musl 1.1+ x86-64 Details for ncls-0.0.71-cp311-cp311-musllinux_1_1_x86_64.whl
ncls-0.0.71-cp311-cp311-musllinux_1_1_i686.whl CPython 3.11 CPython 3.11 Linux musl 1.1+ x86-32 Details for ncls-0.0.71-cp311-cp311-musllinux_1_1_i686.whl
ncls-0.0.71-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl CPython 3.11 CPython 3.11 Linux glibc 2.17+ x86-64 Details for ncls-0.0.71-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
ncls-0.0.71-cp311-cp311-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl CPython 3.11 CPython 3.11 Linux glibc 2.17+ x86-32, Linux glibc 2.12+ x86-32 Details for ncls-0.0.71-cp311-cp311-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl
ncls-0.0.71-cp311-cp311-macosx_11_0_arm64.whl CPython 3.11 CPython 3.11 macOS 11.0+ ARM64 Details for ncls-0.0.71-cp311-cp311-macosx_11_0_arm64.whl

Total release size: 25.5 MB

Release files / ncls-0.0.71.tar.gz

Download URL ncls-0.0.71.tar.gz
Size 651.2 kB
Tags Source
SHA-256 checksum
How to use checksums
6aab15b42511dcf606d809cde4652db4f2086391f8db6079c03eaf8610f37bfc
BLAKE2b-256 checksum
How to use checksums
eb690622c51819e36f51a1f28b21ca7f2d973ddb81d3bdf807c23181c90f07e2
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp312-cp312-musllinux_1_1_x86_64.whl

Download URL ncls-0.0.71-cp312-cp312-musllinux_1_1_x86_64.whl
Size 2.9 MB
Tags CPython 3.12 Linux musl 1.1+ x86-64
SHA-256 checksum
How to use checksums
86fe7bbbd9682cd1b6bcc976008e1cf8229d7baf0529a7dc73ae83d8a7cad366
BLAKE2b-256 checksum
How to use checksums
0b4b1f449c3f92977fd39f8fcadc6bc907cb6d758f8750b86878bd6d09ecd228
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp312-cp312-musllinux_1_1_i686.whl

Download URL ncls-0.0.71-cp312-cp312-musllinux_1_1_i686.whl
Size 2.7 MB
Tags CPython 3.12 Linux musl 1.1+ x86-32
SHA-256 checksum
How to use checksums
ce01095c90491943fae0188dca9bdd04492a1ae80dc1258a85ebe8f6d431c160
BLAKE2b-256 checksum
How to use checksums
f57975d525818850d6de1e21f7edd6357bb5c5d54eb41a56e3d5bbad615afd36
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL ncls-0.0.71-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size 2.9 MB
Tags CPython 3.12 Linux glibc 2.17+ x86-64
SHA-256 checksum
How to use checksums
054f494b5c6ef314ebf75fd83cc95ac5b0d404221584f6808c3be61189c2ed16
BLAKE2b-256 checksum
How to use checksums
ce6c2baffb0d373806d9c494904bc23cc66dde42e0db2613a2ec07410beaaadb
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp312-cp312-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl

Download URL ncls-0.0.71-cp312-cp312-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Size 2.8 MB
Tags CPython 3.12 Linux glibc 2.12+ x86-32 Linux glibc 2.17+ x86-32
SHA-256 checksum
How to use checksums
686018cf6ef983ff81eedae35224a525f2422ad03f2e13e128875473ec3bcf33
BLAKE2b-256 checksum
How to use checksums
1a2724b0773f1f0216c4a0c813cca4922cc39562010acd55bcce93ca5c525bfb
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp312-cp312-macosx_11_0_arm64.whl

Download URL ncls-0.0.71-cp312-cp312-macosx_11_0_arm64.whl
Size 1.0 MB
Tags CPython 3.12 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
3628c74bc0d93c9876b9b1fa8cfb168b3940a5467dae9b366a39f33f2cb44b11
BLAKE2b-256 checksum
How to use checksums
194c3c50d33bd14fcf6aa75bc05c1b6d6e75f80d457917d6fe29e73789e9cf8f
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp311-cp311-musllinux_1_1_x86_64.whl

Download URL ncls-0.0.71-cp311-cp311-musllinux_1_1_x86_64.whl
Size 2.9 MB
Tags CPython 3.11 Linux musl 1.1+ x86-64
SHA-256 checksum
How to use checksums
6408682ffc3f7a5a251a4719dd30f20423908ff26fb5223da668fc63aff85c2d
BLAKE2b-256 checksum
How to use checksums
df9390fadddd3e973a89c3b0fc1b2a6864ceff7877e7c93fad3ae1beb2b89836
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp311-cp311-musllinux_1_1_i686.whl

Download URL ncls-0.0.71-cp311-cp311-musllinux_1_1_i686.whl
Size 2.8 MB
Tags CPython 3.11 Linux musl 1.1+ x86-32
SHA-256 checksum
How to use checksums
8fe3ac0d760d00f5edc66a23e929548cbb017bfeb021cbef236e212911a811ef
BLAKE2b-256 checksum
How to use checksums
e5932c40556edcdbe0728019de77e36ba91942dacdf32b5f456b6a7ce36118af
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL ncls-0.0.71-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size 2.9 MB
Tags CPython 3.11 Linux glibc 2.17+ x86-64
SHA-256 checksum
How to use checksums
27ff407a2e3ca32ab376e75e4c1b1592d6472eaca22c859ee3c5def7c35198ea
BLAKE2b-256 checksum
How to use checksums
a60ba5ec96c7b569acd13417a1c8be7e8d0a664daea57260b78e9abb126a9bae
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp311-cp311-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl

Download URL ncls-0.0.71-cp311-cp311-manylinux_2_12_i686.manylinux2010_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Size 2.8 MB
Tags CPython 3.11 Linux glibc 2.12+ x86-32 Linux glibc 2.17+ x86-32
SHA-256 checksum
How to use checksums
9be3bc73a1f1a97e6fa4428bd883543d21b57a32c311c0620dd3d4f03c2e42fb
BLAKE2b-256 checksum
How to use checksums
2d28c2ae824d95e2326b918c0cfb9369d7c98f1349272af3b4afc10a37e15ec0
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Release files / ncls-0.0.71-cp311-cp311-macosx_11_0_arm64.whl

Download URL ncls-0.0.71-cp311-cp311-macosx_11_0_arm64.whl
Size 1.0 MB
Tags CPython 3.11 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
83c80d43aa62e293e010b4eebccc6337bf4d1e1ce19d084975acc6ece639a5ad
BLAKE2b-256 checksum
How to use checksums
13a4db4241535f87df77530257520e8b844c40d8a989977dab601ba7471a3c22
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.16

Security for ncls 0.0.71

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

0.0.71 This release

11 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page