hitsio: library for reading and writing hits files
Jürgen Jänes <jj374@cam.ac.uk>, Ernest Turro <et341@cam.ac.uk>

A hits file stores the read to transcript mappings and gene/transcript metadata
generated by bam2hits and used as input for mmseq. There are two formats for 
the hits file: a text-based format (bam2hits -f t) which is the default in 
mmseq versions <= 0.9.18 and a binary file format (bam2hits -f b). The binary 
file format uses significantly less disk space than the text format (~7x in 
realistic test cases).

We describe the structure of the *binary* file format. This consists of a 
sequence of fields of different types (str: for string, str_delta for 
delta-encoded string, uint: for unsigned integer). These fields are stored 
according to the following 'pseudo-code schema'.

01 str:"MMSEQ_HITSFILE"
02 uint:schema_no
03 uint:no_of_transcript_records
04 for no_of_transcript_records:
05     str:trascript_id
06     uint:transcript_effective_length
07 uint:no_of_gene_isoform_records
08 for no_of_gene_isoform_records:
09     str:gene_isoform_name
10     uint:no_of_gene_isoform_transcripts
11     for no_of_gene_isoform_transcripts:
12         str:gene_isoform_transcript
13 uint:no_of_identical_transcript_records
14 for no_of_identical_transcript_records:
15     uint:no_of_identical_transcripts_in_record
16     for no_of_identical_transcripts_in_record
17         str:identical_transcript_transcript_id
18 for <until-end-of-file>:
19     str_delta:read_id
20     uint:no_of_transcripts_to_read_id
21     for no_of_transcripts_to_read_id:
22         uint:transcript_index

- The schema_no variable on line 02 is set to '1' for the current version of 
the binary format and should be increased when the format is revised (e.g. an 
implied insert size field is added for every read=>transcript mapping).

- The uint:transcript_index field on line 22 refers to a zero-based index of 
an array of transcript_id read in at line 5, such that meaningful values are 
in the range:
    0 <= transcript_index < no_of_transcript_records

- The hits file does not contain a count of read_id records, as this is not 
known in advance when writing the first read_id.

- *uint* stands for a little endian binary representation uint32_t 
(see WRITE_UINT and READ_UINT in hitsio.cpp)

- *str* stands for a string terminated by a newline character 
(see WRITE_STR and READ_STR in hitsio.cpp)

- *str_delta* stands for a delta-encoded string value, motivated by the fact 
that sequence read identifiers are often long and contain a lot of redundant 
information. Given two successive and similar values, we count the number of 
common characters from the beginning and from the end. Successive strings are 
represented by these character counts and the non-overlapping substring.

Illustrative example:
CRIRUN_695:1:1101:1029:5416 => str:CRIRUN_695:1:1101:1029:5416
CRIRUN_695:1:1101:1030:5416 => uint:20 str:30 uint:5
CRIRUN_695:1:1101:1031:5416 => uint:21 str:1 uint:5

Formally (see also WRITE_STR_DELTA and READ_STR_DELTA in hitsio.cpp):
01 str:value
02 if value=="":
03     uint_small:no_overlappping_characters_at_beginning
04     str:non_overlapping_substring
05     uint_small:no_overlappping_characters_at_end

- Here, *uint_small* stands for an "adaptive encoding" of uint values, which 
saves space when the values saved are mostly small. Specifically, if the value 
stored is <255, it is stored as a single byte. The occurence of a larger value 
is noted by first writing a byte with the value 255 (binary: 11111111), 
followed by writing the actual value as an uint (see WRITE_UINT_SMALL and 
READ_UINT_SMALL in hitsio.cpp).

- The current hitsio implementation ignores endianness, meaning that the binary
format is not transferrable between platforms with different endianness 
(e.g. Intel and a PowerPC).

- The contents of the entire hits file is compressed with zlib via the boost 
iostreams interface, with the option Z_BEST_SPEED (reduced compression time 
for a slightly less efficient compression).
