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.