HSX Format

TABLE OF CONTENTS

• Introduction
• File Specification
• Hash Function
• Example

Introduction

HSX is a binary file format for indexing (or listing) DNA sequences in other files, allowing fast random access to those sequences. The format was created as part of the LASTZ project, providing a means to input selected sequences from several short read files into a single run of LASTZ.

This document is provided for users interested in creating HSX files with programs of their own design.

The HSX file contains a sequence index array and an associated hash table. Each sequence index entry includes the sequence's name, length, and a reference to the location of the sequence's data in some other file. This array can be accessed either sequentially or via the hash table. Note that the names in the index file do not have to match the original names or headers in the sequence files.

Sequence entries are ordered by the hashes of their names. Conceptually, the hash table groups the sequences into buckets of sequences with the same hash. For each bucket, the table gives the location in the sequence index of the first sequence in that bucket. Hash collisions are resolved by scanning subsequent index entries for the remaining sequences in the bucket.

There is also a file table, which allows a single index file to cover sequences from multiple sequence files of varying formats. However, currently LASTZ only supports indexing of files in FASTA format.

File Specification

The file is stored in a binary format described by the table below. It can be written on either a big-endian or little-endian machine; programs reading the file determine the byte order of multi-byte fields by examining the magic number at the start of the file.

Hash Function

The code for the underlying hash function is shown below, written in C. The hash bucket for sequence name NAME is computed by

    bucket = hassock_hash(NAME,strlen(NAME)) % HLEN;

This hash function is a variant of Austin Appleby's MurmurHash2. The primary differences are that it has the seed hardwired and scans the input data in the reverse order (this is not structly true, since the non-multiple-of-four leftover bytes are handled slightly differently). It is also endian-neutral.

    #include <stdint.h>

    uint32_t hassock_hash (const void* key, uint32_t len)
        {
        const uint32_t seed = 0x5C3FC4D3;
        const uint32_t m    = 0x87C10417;
        const uint8_t* data = ((const uint8_t*) key) + len;
        const uint8_t* stop = ((const uint8_t*) key) + 4;
        uint32_t       h, k;

        h = seed ^ len;
        while (data >= stop)
            {
            k  = *(--data);
            k |= *(--data) << 8;
            k |= *(--data) << 16;
            k |= *(--data) << 24;
            k *= m;
            k ^= k >> 24;
            k *= m;
            h *= m;
            h ^= k;
            len -= 4;
            }
        switch (len)
            {
            case 3: h ^= *(--data) << 16;
            case 2: h ^= *(--data) << 8;
            case 1: h ^= *(--data);
                    h *= m;
            }
        h ^= h >> 13;
        h *= m;
        h ^= h >> 15;
        return h;
        }

Example

In this example, we have 10 sequences from 3 fasta files, indexed by a single HSX file. We first show the fasta files, then show a field-by-field hex dump of the corresponding HSX file. For demonstration purposes, the HSX file was created with only 5 buckets. Typical HSX files will deal with more sequences, more files, and have more buckets.

hsxexA.fa contains five sequences:

    >HSXEXA_785
    TAACGGCAATCTTTGGTAGACCTATTGGTCATATCATGAAATTGAAGGAT
    AATTATTGCCATAAAGTTTTTCACGTTACTATCTTTGCCTCGCAATGAAT
    AAAATATTCTTAGGGCTACTTTGTAACCTTGCAGAC
    >HSXEXA_88K
    TTAATTACTCGCATGATCTTTCAAGATCTTTACCGTTCACACAATTTCTC
    GAACACTCAGTA
    >HSXEXA_DNQ
    CAGTGTACAAAATAAACTATTAACTATATGTAGATAGATACATAGAGACA
    AAACGGGTAGCATCTAGTATCCTGACTGCGCATTGTGGGGTGTCGCTTCT
    AAGTACCCGAAATGAGCGT
    >HSXEXA_LRW
    TTAAGTACATTCAGATCCATCATGGTTTCGGAAGCTAATGGGAAAAGGGG
    TACAGAATACAACACCTAGTTGATACGATAGTTAGTTTTTTA
    >HSXEXA_R9V
    TATAGTGCGTGTATGACCAATATTACGATGATCGTGACGCCATAGGGTCA
    TATTCCTTAATATGTAAATATGAAGGTA

hsxexB.fa contains four sequences:

    >HSXEXB_6YF
    AAGAGTTCTTACGGCAATAACAAAATGATGCTGTATCCTAGTAACAGGAA
    CGAACCATTCGCTTCTGTGTTCTATACAGAAGAAACCAGACTCGCTAAAC
    A
    >HSXEXB_WCV
    AATTAGTCTATTAAGGACTATATGTTTACAAGGATGGTAGTCCTAACGGA
    ATTGATACCAATAGGTGGCACTTACCGTAGCTAGGTAGATCGCCCTACTA
    CACCAGCTCAGCCATCTTGCCCCGCCAACT
    >HSXEXB_YKU
    GTCAACAGGTTTTCGGACTGGTGGCTTTCCTGATTTGATATTCAAAGGAA
    ATTAGGGTAAGGACTTTGAGTTGTCATAGAATTCAATTTCGGGCTCCGTC
    CATCACCTCGT
    >HSXEXB_YV1
    GGTGATGTTGTGAATATCACTGTCATGAAGGTCTCCTTCGGCCGCCTTAA
    TCATCATCATAAGTTTCACCATGGTAAAATGAATTAGCCCCAAGCT

hsxexC.fa contains three sequences:

    >HSXEXC_4ZL
    CACATCACATTGGTTGTTCATCCATATAATTATTTCCCATAAACTTTAAG
    AGCTCGGCTGGCCATACGTACTGACTAGCTTAGCCCCTAACTAATCGGCC
    ACAGCGATAGTACA
    >HSXEXC_936
    TGGTTTTTAGAGTCCGTGGAGCCTCTCAGCCACACTGGGTTCGGGAAGTT
    TCAGGCAAGTCCTACCTGTAA
    >HSXEXC_GWD
    CTAATCTGGGCTTGGGTCTGAACTCGCCCATGAGGAGGTAAGCAAACCAA
    TAAATTCGGGTATGGCGGTCTTTATTATGCTTAAGGAACGGAACAA

The twelve sequence names are hashed into separate buckets, and sorted within buckets, like this:

Here is the complete HSX file, byte-by-byte: