cram and bam footers for storing key/value pairs

[sb10]

It would be very useful to be able to store arbitrary key/value pairs in the footer of both cram and bam files.

My use-case would be storing sequence checksums. The desire to have these in the footer and not the header is so that I can store these on a streamed in alignment file.

Backwards compatibility with tools that trip up on the footer could be achieved with a special argument to samtools view that emits the alignment file as-is, except for the footer.

I propose implementing a reference implementation of this in samtools, once a way of implementing a footer is suggested by responders.

[sb10]

samtools meeting discussion:
cram-only would be easiest.
footer exclusion idea not so good? Stenography solution with storing data in penultimate block would be better? Storing in fake unaligned sequence with a name starting with ~?

[sb10]

cram-only isn't ideal for my use case, because I want my seqchksums to verify the numerous bams we make in our pipelines. We don't currently deal with crams except as initial input. If we manage to re-engineer our pipelines to be all-cram, we probably won't have a backwards compatibility concern.

[jkbonfield]

We worked out one way of doing this in BAM as a transparent block of data - meaning existing BAM readers wouldn't spot it and zlib would produce zero additional output during decoding.

There are, no doubt, many ways to achieve it. Ideally we would extend the info field in gzip stream which is permitted, but not actually coded correct in many BAM implementations. More transparent would be to generate a zlib huffman table where the presence of a symbol acts as a bit of information (more if we wish to play with symbol code lengths). The data stream itself is empty, so it's pure data encoding via metadata. At a minimum that means maybe 9 bytes of information in the huffman table. Multiple blocks can be concatenated together to form arbitrary footer lengths. It's extreme solution, but it does appear to be technically possible.

For CRAM we already have the slice (or container?) key-type-value tuples in the same structure as aux blocks on reads. These were expressly designed for checksumming. Hence it's trivial to add a whole-file checksum using the same technique.

[jrandall]

Agree this would be useful, and I agree with Sendu the ability to have this in SAM/BAM as well as CRAM would be ideal. I had also been thinking about adding it to the bgzip fields, but actually it would be much better if uncompressing data did not result in losing the footer information, so I think I am strongly in favor of in-band signalling that would persist through all of the various formats. I suspect the best way to achieve might be to use some form of special read record (with no sequence and a special flag) that would tend to get ignored in the context of anything important.

[jkbonfield]

We discussed this in the office after last weeks meeting and some were against in-band methods. David (I think) raised the point that anything that modifies SAM without knowing about the special ~~~whatever fake reads (sorted to end of file by both coord and name order) would invalidate the footer, so the footer would have to somehow indicate when it is out of date (tricky as there's no generation number or similar in the header).

There is something to be said for having a system where the footer inherently gets invalidated by any command that modifies data but doesn't understand the footer. This is key for data checksums. Any bright ideas?

In the future this sort of thing can be achieved by the same type of technology for keeping .bam and .bam.bai in sync (random generated uuids that have to match), but as they don't yet exist in the header we cannot exploit them for the footer.

[sb10]

My implementation of seqchksum in samtools would calculate the checksums as it streamed through the file, and then if a footer existed, compare the checksums, and die on a (desired kind of) mismatch.

So the footer being out of date will behave the same as the sequencing data becoming corrupted, and in both cases the user must investigate and update the footer in the former case. They will immediately learn not to use the tool that isn't handling the footer correctly (or to always post-process it's output with the samtools command that force-regenerates a new footer without aborting), so I'm not sure this is an issue?

[jkbonfield]

Musings on the mechanisms.

See eg https://partners.adobe.com/public/developer/en/ps/5002.EPSF_Spec.pdf page 14.

PostScript header has items like %%BoundingBox which needs computation of all item locations. This can be complex for streams to compute upfront, so it has the option of specifying "(atend)" as the value and then include a second %%BoundingBox in a %%Trailer section.

I would like to suggest that any items we have in the footer must also appear in the header with some form of deferred or atend token to indicate their presence in the footer. This tells us which checksums we'll need to compute, if any, allowing us to be efficient where appropriate.

Consider a worked example, running fixmates on an input file.

• Open input and output files.
• Read header from input, write header to output. Input header has either @CS seq deadbeef (example; CS=checksum) or @CS seq atend.
• The usual while (seq=read(in)) {do_stuff(seq); write(out,seq);} style loop. During this we'll be computing the seq checksum, but not any other checksums as they're not in the header.
• EOF on input; fetch footer and compare checksums; set expected output checksum.
• EOF on output; automatically checks output checksum from expected value. If we didn't set an expected value then this wouldn't be done.
• Close input stream.
• Close output stream; this also automatically writes the footer from the generated checksums, although we can add an explicit footer writing API too.

The above is orthogonal to how the footer is encoded (in-band or out-of-band).

Edit: the presence of an atend header item should not mandate that it exists in the footer; the file may have been produced by something that didn't honour the footer. It is simply a request that the data may be in the footer and so must be computed.

[vadimzalunin]

@jkbonfield sorry if I misunderstood, are you suggesting to use FLG.FEXTRA?
Also is huffman table for saving space? The key/value metadata should have negligible effect on file size any way.
A secret layer sounds hack-ish to me but I can't think of anything better than extra block after EOF for footer. Given new types of SAM file header records that should be enough imo.

[yfarjoun]

It sounds like BAM and CRAM will have data that is not representable in SAM. this will make round-trip checks very difficult and as people start using this to put "real" data in, this will become a problem. I think that the data should be format agnostic, so that whatever solution we think of should have an implementation in all current data-formats, including SAM...but that's just MHO.

[dbolser]

Why can't this be done with the checksum in the header?
On 14 Mar 2016 4:08 pm, "Sendu Bala" notifications@github.com wrote:

My implementation of seqchksum in samtools would calculate the checksums
as it streamed through the file, and then if a footer existed, compare the
checksums, and die on a (desired kind of) mismatch.

So the footer being out of date will behave the same as the sequencing
data becoming corrupted, and in both cases the user must investigate and
update the footer in the former case. They will immediately learn not to
use the tool that isn't handling the footer correctly (or to always
post-process it's output with the samtools command that force-regenerates a
new footer without aborting), so I'm not sure this is an issue?

—
Reply to this email directly or view it on GitHub
#136 (comment).

[sb10]

@dbolser Because you can't then store new checksums in a streaming context.

[dbolser]

OK, but why can't you put it in when you first bake the SAM/BAM/CRAM? Is
this an issue with legacy files?
On 19 Mar 2016 8:12 am, "Sendu Bala" notifications@github.com wrote:

@dbolser https://github.com/dbolser Because you can't then store new
checksums in a streaming context.

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#136 (comment)