<commit_before>---
layout: post
title:  "Binary file parsing in bioinformatics"
date:  2016-12-23
categories:
- blog
- bioinformatics
- binary
- bam
permalink: binary-file-parsing-in-bioinformatics
---

Sometimes I like to get into the weeds of a problem that is only tangentially related to the actual problem I am trying to solve. For example, the other day I was trying to write a smallapplication to serve up  [BAM](http://www.htslib.org/doc/sam.html) alignments to a user based on a location range query. The goal of the project would be to have a server/client that conforms to the draft [GA4GH Streaming API](https://docs.google.com/document/d/1OSPfxdJ3uPoCfUVzMaekCOPF5sNEwqkJEUj-SjlECy0/edit#heading=h.a2dq86evs2ut) specification.

The goals I set out for myself where:

* Serverless environment, which means using [Amazon API Gateway](https://aws.amazon.com/api-gateway/),  [AWS Lambda](https://aws.amazon.com/lambda/) (Python runtime), and [Amazon DynamoDB](https://aws.amazon.com/dynamodb/) for the service components, and [Amazon S3](https://aws.amazon.com/s3/) for data storage
* Authenticated access to BAM files on S3
* Limit the number requests as much as possible

The tangential rabbit hole I fell into was in developing routines to parse out the data within a BAM index file into DynamoDB for easy lookup. For easier reference, below is the description of the index format pulled from the [SAM format specification](http://samtools.github.io/hts-specs/SAMv1.pdf).


![BAI binary file structure]({{site.url}}/assets/2016-12-23-binary-file-parsing-in-bioinformatics/bai_spec.png)


There are no tools that independently inspect this binary format and spit out the information into text, only tools (e.g. PICARD, samtools) that use the index for random access into BAM files. If I wanted that information I would either need to calculate the file offsets myself (as is done in the excellent [htsnexus](https://github.com/dnanexus-rnd/htsnexus)) or implement my own binary file parser for BAI files.

Since I was targeting the [Python runtime for Lambda](http://docs.aws.amazon.com/lambda/latest/dg/lambda-python-how-to-create-deployment-package.html) I found two packages that would fit the bill to define the grammer of the binary data into objects that I could easily use,  [construct](http://construct.readthedocs.io/en/latest/) and [Kaitai Struct](http://kaitai.io).

Yes, I could have used the core `struct` Python library, but I wanted a slightly higher level interface to the binary grammer. Both `construct` and `kaitai-struct` result in more readable and maintainable code, and both provide concepts for dealing with common data structures that I would have had to deal with on my own. Let's compare these methods on the binary file format for BAM index files that

## Construct

[Construct](http://construct.readthedocs.io) is "a powerful declerative parser (and builder) for binary data". The library provides primitives for common atomic constructs (e.g. different size integers) and more advanced data structures to allow for defining composite structures. You can read more about it at their site, but I think that an example is best. Let take a look at a `chunk` which is a pair of virtual file offsets in BAI files. A virtual file offset (section 4.1.1 of the SAM specification) is a tuple of locations. The first element is the location of the start of a compressed block within a BAM file (`coffset`), and the second element is the offset of an alignment within the **uncompressed** data in that block of data. Logically you encode this tuple in a 64 bit integer like so:

```
# shift coffset by 16 bits, then XOR the uoffset location<commit_msg>added baseurl to image<commit_after>---
layout: post
title:  "Binary file parsing in bioinformatics"
date:  2016-12-23
categories:
- blog
- bioinformatics
- binary
- bam
permalink: binary-file-parsing-in-bioinformatics
---

Sometimes I like to get into the weeds of a problem that is only tangentially related to the actual problem I am trying to solve. For example, the other day I was trying to write a smallapplication to serve up  [BAM](http://www.htslib.org/doc/sam.html) alignments to a user based on a location range query. The goal of the project would be to have a server/client that conforms to the draft [GA4GH Streaming API](https://docs.google.com/document/d/1OSPfxdJ3uPoCfUVzMaekCOPF5sNEwqkJEUj-SjlECy0/edit#heading=h.a2dq86evs2ut) specification.

The goals I set out for myself where:

* Serverless environment, which means using [Amazon API Gateway](https://aws.amazon.com/api-gateway/),  [AWS Lambda](https://aws.amazon.com/lambda/) (Python runtime), and [Amazon DynamoDB](https://aws.amazon.com/dynamodb/) for the service components, and [Amazon S3](https://aws.amazon.com/s3/) for data storage
* Authenticated access to BAM files on S3
* Limit the number requests as much as possible

The tangential rabbit hole I fell into was in developing routines to parse out the data within a BAM index file into DynamoDB for easy lookup. For easier reference, below is the description of the index format pulled from the [SAM format specification](http://samtools.github.io/hts-specs/SAMv1.pdf).


![BAI binary file structure]({{site.url}}/{{site.baseurl}}/assets/2016-12-23-binary-file-parsing-in-bioinformatics/bai_spec.png)


There are no tools that independently inspect this binary format and spit out the information into text, only tools (e.g. PICARD, samtools) that use the index for random access into BAM files. If I wanted that information I would either need to calculate the file offsets myself (as is done in the excellent [htsnexus](https://github.com/dnanexus-rnd/htsnexus)) or implement my own binary file parser for BAI files.

Since I was targeting the [Python runtime for Lambda](http://docs.aws.amazon.com/lambda/latest/dg/lambda-python-how-to-create-deployment-package.html) I found two packages that would fit the bill to define the grammer of the binary data into objects that I could easily use,  [construct](http://construct.readthedocs.io/en/latest/) and [Kaitai Struct](http://kaitai.io).

Yes, I could have used the core `struct` Python library, but I wanted a slightly higher level interface to the binary grammer. Both `construct` and `kaitai-struct` result in more readable and maintainable code, and both provide concepts for dealing with common data structures that I would have had to deal with on my own. Let's compare these methods on the binary file format for BAM index files that

## Construct

[Construct](http://construct.readthedocs.io) is "a powerful declerative parser (and builder) for binary data". The library provides primitives for common atomic constructs (e.g. different size integers) and more advanced data structures to allow for defining composite structures. You can read more about it at their site, but I think that an example is best. Let take a look at a `chunk` which is a pair of virtual file offsets in BAI files. A virtual file offset (section 4.1.1 of the SAM specification) is a tuple of locations. The first element is the location of the start of a compressed block within a BAM file (`coffset`), and the second element is the offset of an alignment within the **uncompressed** data in that block of data. Logically you encode this tuple in a 64 bit integer like so:

```
# shift coffset by 16 bits, then XOR the uoffset location
{'fraction_non_alphanumeric': 0.07552788305360043, 'fraction_numerical': 0.009745533297238766, 'mean_word_length': 4.547297297297297, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 12, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4737609', 'n_tokens_mistral': 2128, 'n_tokens_neox': 1988, 'n_words': 996}