7 ms·
> ~2.5 bit/base Given that there are four bases, i would have thought you could reliably do it in 2. What am i missing?
by twic 8y ago
> ~2.5 bit/base
Given that there are four bases, i would have thought you could reliably do it in 2. What am i missing?
- deugtniet 8y agoProbably that certain base sequences are more likely to occur together than random. If you account for this, it'll help in your compression.
- pdkl95 8y agoThat's right - the Huffman tree was built based on the base frequency of use, which actually varies depending on what type of organism you're sequencing[1]. [1] https://en.wikipedia.org/wiki/GC-content#Among-genome_variation https://en.wikipedia.org/wiki/GC-content#Among-genome_variat...
- mbreese 8y agoYou need to encode for an ambiguous base call (N). So it’s really 3 bits, but you can play with the format to encode it slightly more efficiently.
- pdkl95 8y agoAt a minimum there were two additional symbols: "N" for uNknown, where the raw sensor information - which should be a series of nice Gaussians[1 top] - was too ambiguous/low-quality for a useful basecall, but the presence of something can be inferred from the timing information[1 bottom, with "N"s in some bases] An additional unused bit pattern was reserved for future emergency additions. It used the longest bit pattern so future additions wouldn't be balanced properly, but I wanted something simple, guaranteed binary-compatibility, that could handle a sudden change in requirements. In some situations, a variation was used that included a few symbols for partial basecalls like "unknown purine" (A or G) and "unknown pyrimidine" (C or T). [1] http://image.slidesharecdn.com/binoinfo-8-141021112354-conversion-gate02/95/7-11-638.jpg http://image.slidesharecdn.com/binoinfo-8-141021112354-conve...
- twic 8y agoMakes sense, thanks. Back when i was phredding for a living, i had the luxury of just cutting off the file when the quality of the read got dodgy!
- jkbonfield 8y agoIt's hard with huffman given you need to deal with N. Realistically you'll end up with 3 bases at 2 bits, 1 and 3 and the other 3 being a prefix for everything else (N, ambiguity codes, etc), so somewhere averaging close to 2.3 bits is the norm. If N is rare though, you're better off just doing blocks of 2-bit encoding and dropping to something more complex for the rare cases. Or of course just using an arithmetic / range / ANS coder.