Bin indexing system

Introduction

The binning index system used in the genome browser is a mechanism used in concert with MySQL indexes to speed up selection of MySQL rows for genome coordinate overlapping items. This type of search is sometimes called a range request. The system as first used in the genome browser is described in: "The Human Genome Browser at UCSC" Kent, et. al. Genome Research 2002.12:996-1006, see Figure 7, quote:

We settled on a binning scheme suggested by Lincoln Stein and Richard Durbin. A simple version of this scheme is shown in
Figure7. In the browser itself, we use five different sizes of bins: 128 kb, 1 Mb, 8 Mb, 64 Mb, and 512 Mb.

That initial implementation has since been enhanced by an additional level of bins to allow items of size up to 4 Gb (actually only to 2Gb given integer size limits). The new and the old system coexist together. Given an item with a chromEnd coordinate of less than or equal to 512 Mb, a bin number in the old system will be used. An item with a chromEnd coordinate greater than 512 Mb, a bin number in the new system will be used.

Since all of these bins are in sizes of powers of two, the calculation of the bin number is a simple matter of bit shifting of the chromStart and chromEnd coordinates. The C code for the bin calculation can be seen in the kent source tree in src/lib/binRange.c.

Initial implementation

Used when chromEnd is less than or equal to 536,870,912 = 2²⁹

		bin numbers		bin
level	#bins	start	end	size
0	1	0	0	512 Mb
1	8	1	8	64 Mb
2	64	9	72	8 Mb
3	512	73	584	1 Mb
4	4096	585	4680	128 kb

Extended implementation

Used when chromEnd is greater than 536,870,912 = 2²⁹ and less than 2,147,483,647 = 2³¹ - 1

		bin numbers		bin
level	#bins	start	end	size
0	1	4691	4691	2 Gb
1	8	4683	4685	512 Mb
2	64	4698	4721	64 Mb
3	512	4818	5009	8 Mb
4	4,096	5778	7313	1 Mb
5	32,768	13458	25745	128 kb

Initial implementation C code

/* This file is copyright 2002 Jim Kent, but license is hereby
 * granted for all use - public, private or commercial. */

static int binOffsets[] = {512+64+8+1, 64+8+1, 8+1, 1, 0};
#define _binFirstShift 17       /* How much to shift to get to finest bin. */
#define _binNextShift 3         /* How much to shift to get to next larger bin.

static int binFromRangeStandard(int start, int end)
/* Given start,end in chromosome coordinates assign it
 * a bin.   There's a bin for each 128k segment, for each
 * 1M segment, for each 8M segment, for each 64M segment,
 * and for each chromosome (which is assumed to be less than
 * 512M.)  A range goes into the smallest bin it will fit in. */
{
int startBin = start, endBin = end-1, i;
startBin >>= _binFirstShift;
endBin >>= _binFirstShift;
for (i=0; i<ArraySize(binOffsets); ++i)
    {
    if (startBin == endBin)
        return binOffsets[i] + startBin;
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
errAbort("start %d, end %d out of range in findBin (max is 512M)", start, end);
return 0;
}

Extended implementation C code

/* This file is copyright 2002 Jim Kent, but license is hereby
 * granted for all use - public, private or commercial. */

/* add one new level to get coverage past chrom sizes of 512 Mb
 *      effective limit is now the size of an integer since chrom start
 *      and end coordinates are always being used in int's == 2Gb-1 */
static int binOffsetsExtended[] =
        {4096+512+64+8+1, 512+64+8+1, 64+8+1, 8+1, 1, 0};

static int binFromRangeExtended(int start, int end)
/* Given start,end in chromosome coordinates assign it
 * a bin.   There's a bin for each 128k segment, for each
 * 1M segment, for each 8M segment, for each 64M segment,
 * for each 512M segment, and one top level bin for 4Gb.
 *      Note, since start and end are int's, the practical limit
 *      is up to 2Gb-1, and thus, only four result bins on the second
 *      level.
 * A range goes into the smallest bin it will fit in. */
{
int startBin = start, endBin = end-1, i;
startBin >>= _binFirstShift;
endBin >>= _binFirstShift;
for (i=0; i<ArraySize(binOffsetsExtended); ++i)
    {
    if (startBin == endBin)
        return _binOffsetOldToExtended + binOffsetsExtended[i] + startBin;
    startBin >>= _binNextShift;
    endBin >>= _binNextShift;
    }
errAbort("start %d, end %d out of range in findBin (max is 2Gb)", start, end);
return 0;
}