BITS: Binary Interval Search
C++ Cuda C Makefile
Latest commit ecff101 Feb 3, 2017 @ryanlayer ryanlayer one sided
Failed to load latest commit information.
data initial commit Aug 15, 2012
genomes initial commit Aug 15, 2012
src one sided Feb 3, 2017
.gitignore add .gitignore Aug 15, 2012
LICENSE initial commit Aug 15, 2012
Makefile fix makefiles and README for clean install Aug 15, 2012
README.rst README update, mem fix Nov 13, 2012
bits_tests set runtime ENV for shell script Aug 16, 2012
defs.local makefile fix and lower mem attempt Oct 19, 2012



This repository contains the source code for the BITS (Binary Interval Search) algorithm developed in the Quinlan laboratory at the University of Virginia.


BITS installation requires the GNU Scientific Library (GSL) as well as NVidia GPU drivers and libraries. Below is a step-by-step tutorial for how to install the necessary drivers, SDK and libraries to run BITS on an NVidia CUDA GPU. If you have questions, email me.

Install the GNU Scientific Libraries (GSL).

  • This is typically quite simple, as one can use package managers.
    • e.g., for OS X using Homebrew: brew install gsl
    • e.g., for Ubuntu: apt-get install gsl

Download and install the CUDA toolkit.

Download and install the CUDA drivers for you system.

Download and install the CUDA SDK.

Download and install the cudapp library at: Once downloaded, do

cd cudpp_src_2.0
cmake .

*Important*: Take note of the path to which you placed cudpp, as you will need this when we update the BITS Makefile.

Update your PATH (rec. you save in .bash_profile for permanence) as follows

export PATH=/usr/local/cuda/bin:$PATH
export DYLD_LIBRARY_PATH=/usr/local/cuda/lib:$DYLD_LIBRARY_PATH

Clone the BITS repository

git clone git://

Navigate into the bits directory

cd bits
Edit the defs.cuda file in accordance with your configuration.
  • Edit the PLATFORM environment variable.
    • if OSX, set PLATFORM=darwin
    • if Linux, set PLATFORM=linux
    • if Windows, sorry this is unsupported.
  • Edit the SDK_PATH environment variable.
    • This is the installation path that you should have taken note of in step #4.
    • e.g., for OS X, this should be: SDK_PATH=/Developer/GPUComputing/
  • Edit the SDK_PATH environment variable.
    • This is the path to which you downloaded and compiled cudpp in step #5.
  • EDIT the CUDA_LIB environment variable.
    • If OS X, this should be: /usr/local/cuda/lib
    • If Linux, this should be: /usr/local/cuda/lib64

At this point, you should be ready to compile BITS


Now, you can test both the sequential and CUDA versions of the tools by running the bits_tests scripts. Also, this shell script demonstrates how to run each of the BITS tools

sh bits_tests

If all works well, you should see the following

sh bits_tests
O:72534 E:1124.853000   sd:33.680585    p:0.000999
O:72534 E:1124.081000   sd:36.552024    p:0.000999


If you want to run the BITS CUDA Monte Carlo simulation tool for a single pairwise comparison of two BED files, run the following, where -n is the number of MC iterations and -g is the name and size of each chromosome:

bin/bits_test_cuda -a a.bed -b b.bed -g chrom.sizes -n 1000

If you want to run the BITS CUDA Monte Carlo simulation tool for a _many_ pairwise comparison of multiple BED files, just create a shell script that loops over every pairwise set of files and calls the program as above. For example:

for file1 in `cat file_list.txt`
    for file2 in `cat file_list.txt`
        bin/bits_test_cuda -a $file1 -b $file2 -g chrom.sizes -n 1000

Trouble Shooting

OS X: If you get the "no CUDA-capable device is detected" after installing the drivers, try turning off "Automatic graphics switching." Go to launchpad/System Preferences/Energy Saver and uncheck Automatic graphics switching. Thanks to Stéphane Plaisance for this fix.