3 ms·
The actual killer application of character count matching is bioinformatics. You only need four distinct characters to encode DNA, which of course, means in rea
by nonameiguess 5y ago
The actual killer application of character count matching is bioinformatics. You only need four distinct characters to encode DNA, which of course, means in reality you only need two bits, but I don't know if anyone has bothered to develop a two-bit character encoding system and instructions that can operate on them. They have come up with extremely optimized implementations that compare byte streams, though, utilizing ASCII GCTA.
- TchoBeer 5y agoexcept amino acids are encoded for with three bases, meaning that the actual character encoding system is 6 bits.
- jakobnissen 5y agoBioinformatician here. Yes, people have come up with many encoding systems: 2-bit encoding systems, 3-bit encoding systems (for N's), various encoding schemes that allows long runs of N's to be stored with little memory costs, and even reduced amino acid alphabets for e.g. 4-bit amino acid sequences. In my experience, the performance bottlenecks in bioinformatics is usually IO, parsing, de/compression and needlessly slow algorithms. You rarely get meaningful speed improvements by internally encoding the sequences one way or another (storing small fixed-size sequences in machine integers is an exception). There can be other advantages, though, like reduced memory consumption. Partly for that reason, most DNA data is just stored as gzipped text files.
- GianFabien 5y agoCould be an area to use FPGA based arrays for far greater throughput. Some recent RISC-V designs include FPGA blocks.