← Back
Home › Systems › Biotech and life sciences

genome-pipeline

genome alignment and variant calling

BWA, GATK

SystemTechniques · 7Primitives · 23 genome-pipeline Bayesian genotype likelihoodssearch-sort · medium: Per-site genotype likelihoods from read base qualities, combined with priors to call variantsDe bruijn graph assemblysearch-sort · medium: Assemble reads by walking a k-mer de Bruijn graph; tip and bubble removalExternal merge sortsearch-sort · medium: Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.›Fm indexsearch-sort · medium: BWT plus rank structures for backward search: count and locate substrings in compressed spaceMinimizer kmer indexsearch-sort · medium: Index sequences by window minimizers of k-mers for fast seeding and chaining (minimap2)Pair hmmsearch-sort · medium: Pair hidden Markov model for read-haplotype likelihoods, vectorized forward algorithmSmith-Waterman local alignmentsearch-sort · medium: Dynamic programming that finds the highest-scoring pair of similar substrings of two sequences under a substitution score and affine gap penalties, in O(nm) time.›Swiss tabledata-structures · low: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.›Burrows-Wheeler transform (BWT)compression · low: Reversible permutation that sorts every character by the context following it, clustering equal bytes into runs; the core of bzip2 and of FM-index text search.›Rank/select bitvectorsdata-structures · low: Bitvector plus small count tables: ones before position i and position of the k-th one in O(1); Elias-Fano builds compressed sorted lists on it.›Suffix arraysearch-sort · low: Sorted array of all suffix start positions of a text; finds every occurrence of any substring by binary search, at 4-5 bytes per text byte.›SIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Seekable compressed streamcompression · low: Independently compressed blocks plus an index for random access (BGZF, seekable zstd, eStargz)Interval treedata-structures · low: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.›Floating-point errornumerics · low: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›Vcf variant normalizationsearch-sort · low: Parse VCF and left-align/trim indels so equal variants share one representationBloom filterdata-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.›Rolling hashdata-structures · low: Rabin-Karp polynomial rolling hashes and winnowing for substring fingerprints and document matchingBFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Buffer pools for zero-allocation I/Ohardware-os · low: Preallocate a fixed set of aligned I/O buffers and recycle them through a free list, so the hot path never mallocs, faults or unmaps. The bounded count doubles as back pressure.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Pattern-defeating quicksort (pdqsor…search-sort · low: Introsort successor: quicksort with adaptive pivots, linear on sorted and equal-heavy input, heapsort fallback; the unstable sort of Go and (until 1.81) Rust.›Fast hash functionsdata-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›+ 7 more primitives

Similar systems

Share the most building blocks with this one.

liquid-biopsy 25 %sequencer-instrument 19 %