home on CuriousCoding

What is bioinformatics?

Table of Contents 1 A Brief History 1.1 A*PA 1.2 A*PA2 1.3 Overview 2 Problem Statement 3 Alignment types 4 Cost Models 4.1 Minimizing Cost versus Maximizing Score 5 The Classic DP Algorithms 6 Linear Memory using Divide and Conquer 7 Dijkstra’s Algorithm…

Table of Contents 1 Theory of Sampling Schemes 1.1 Introduction 1.2 Overview 1.3 Theory of sampling schemes 1.4 Notation 1.5 Types of sampling schemes 1.6 Computing the density 1.7 The density of random minimizers 1.8 Universal hitting sets 1.9 Asymptotic…

Table of Contents 1 Variants of semi-global alignment 2 Fast text searching 2.1 Skip-cost for overlap alignments 2.2 Results 3 Mapping using A*Map 3.1 Seeding 3.2 Chaining 3.3 Aligning 3.4 A*Map 3.5 Results This is Chapter 5 of my thesis (Groot Koerkamp 2…

Table of Contents 1 Introduction 1.1 Overview 2 Optimizing Compute Bound Code: Random Minimizers 2.1 Avoiding Branch Misses 2.2 SIMD: Processing In Parallel 2.3 Instruction Level Parallelism 2.4 Input Format 3 Optimizing Memory Bound Code: Minimal Perfect…

Table of Contents 1 Early idea: Bottom-up match-merging (aka BUMMer?)

1 De Bruijn graph Link to heading Consider an edge-centric De Bruijn graph, where each edge corresponds to a k-mer, and nodes are the \(k-1\) overlaps between adjacent k-mers.

Table of Contents 1 Jaccard similarity 2 Hash schemes 2.1 MinHash 2.2 $s$-mins sketch 2.3 Bottom-\(s\) sketch 2.4 FracMinHash 2.5 Bucket sketch 2.6 Mod-bucket hash (new?)

1 Warming up: A cute problem Link to heading Given a string, choose one character.

Table of Contents 1 Overview 2 Introduction - Previous reviews 3 Theory of sampling schemes 3.1 Questions 3.2 Types of schemes 3.3 Parameter regimes 3.4 Different perspectives 3.5 UHS vs minimizer scheme 3.6 (Asymptotic) bounds 3.7 Lower bounds 4 Minimizer

Table of Contents 1 Consensus 1.1 Consensus-RecSplit 2 IDEA: Consensus-PtrHash 3 Tiny pointers and optimal open addressing hash tables These are some thoughts on the Consensus-based MPHF presented in Lehmann et al. (2025), and how this could be applied to…

Table of Contents 1 Optimizing Binary Search And Interpolation Search 1.1 Problem statement 1.2 Inspiration and background 1.3 Benchmarking setup 2 Binary search 2.1 Branchless search 2.2 Explicit prefetching 2.3 Batching 2.4 A note on power-of-two array…

Table of Contents Abstract 1 Introduction 2 Related work 3 PtrHash 3.1 Overview 3.2 Construction 3.3 Bucket Assignment Functions 3.4 Remapping using CacheLineEF 4 Results 4.1 Construction 4.1.1 Bucket Functions 4.1.2 Tuning Parameters for Construction 4.1…

Table of Contents Latex Code highlighting: minted Wide figure Fit more text on a page Rust Cargo.toml workspace Release profile List exported functions Read human genome using needletail Prevent auto-vectorization Sorting Python Pretty plots Json to pivot…

Table of Contents 1 Nginx setup 2 GoAccess configuration 3 Systemd setup 4 Serving the static file 5 Serving live statistics 6 GeoIP database GoAccess (goaccess.io, github) is a tool that analyses server logs and gives real-time statistics on network traf…

Table of Contents 1 Introduction 1.1 Problem statement 1.2 Motivation 1.3 Recommended reading 1.4 Binary search and Eytzinger layout 1.5 Hugepages 1.6 A note on benchmarking 1.7 Cache lines 1.8 S-trees and B-trees 2 Optimizing find 2.1 Linear 2.2 Auto-vec…

Table of Contents Overview Detailed comments General Abstract 1.

Table of Contents Overview Detailed comments Terminology Abstract Preliminaries Methods 3.5 Transformations Results Discussion Comments on “Expected density of random minimizers” These are some (biased) comments on “Greedymini: Generating Low-Density Dna…

Table of Contents The importance of ordering Asymptotically optimal minimizers These are some (biased) comments on “When Less Is More: Sketching with Minimizers in Genomics” (Ndiaye et al. 2024).

Table of Contents 1 Suffix arrays 2 Searching methods 2.1 Naive \(O(|P|\cdot \lg_2 n)\) search 2.2 Faster \(O(|P|\cdot \lg_2 n)\) search 2.3 LCP-based \(O(|P| + \lg_2 n)\) search 3 Analysing the faster search We’ll prove that using the “faster” binary sea…

Table of Contents A note on SDSL versions Here I’ll briefly list some FM-index and related implementations around the web.

Table of Contents 1 Sampling schemes 1.1 Definitions 1.2 Miniception 1.3 Mod-minimizer 1.4 Forward scheme lower bound 1.5 Open syncmer minimizer 1.6 Open-closed minimizer 1.7 New: General mod-minimizer 1.8 Variant: Open-closed minimizer using offsets 2 Se…

Table of Contents 1 Steps 1.1 Using kwargs 2 TODOs Using PyO3 and maturin, it’s very easy to call Rust code from Python.

https://transformer-circuits.pub/2021/framework/index.html https://infini-gram.io/ https://sleepinyourhat.github.io/checklist/

Table of Contents 1 General observations 2 Heuristic track 3 Parameterized track 4 Exact track In this post I will collect some high level ideas and approaches used to solve the PACE 2024 challenge.

Table of Contents 1 Space dust 1 Space dust Link to heading What is the total mass of space dust hitting the earth during the Perseids meteor shower?

Table of Contents 1 Introduction 1.1 Results 2 Random minimizers 3 Algorithms 3.1 Problem statement Problem A: Only the set of minimizers Problem B: The minimizer of each window Problem C: Super-k-mers Which problem to solve Canonical k-mers 3.2 The naive…

Table of Contents A*PA PA-Bench Mod-minimizers There are links for my talks and posters.

Table of Contents Succinct background Definitions Lower bounds A new lower bound Discussion Post scriptum Acknowledgement The results of this post are now published in Bioinformatics: DOI, PDF: Kille, Bryce, Ragnar Groot Koerkamp, Drake McAdams, Alan Liu,…

Table of Contents 1 Sapling 2 PLA-Index 3 LISA: learned index Let’s summarize some tools for efficiently searching suffix arrays. 1 Sapling Link to heading Sapling (Kirsche, Das, and Schatz 2020) works as follows: Choose a parameter \(p\) store for each of

Popular C libraries are: divsufsort libsais Both have a ..64 variant that supports input strings longer than 2GB.

Table of Contents Summary Background Review comments DFS Supplementary methods Details of pruning Evals Discussion Code & repo Here are some thoughts on POASTA (van Dijk et al. 2024), a recent affine-cost sequence-to-DAG (POA) aligner inspired by WFA and…

Table of Contents Abstract 1 Introduction 1.1 Contributions 1.2 Previous work 1.2.1 Needleman-Wunsch 1.2.2 Graph algorithms 1.2.3 Computational volumes 1.2.4 Parallelism 1.2.5 Tools 2 Preliminaries 3 Methods 3.1 Band-doubling 3.2 Blocks 3.3 Memory 3.4 SIMD

Table of Contents Summary Main issues 1.

Table of Contents Applications Background Minimizers Density bounds Robust minimizers PASHA Miniception Closed syncmers Bd-anchors New: Mod-minimizers Experiments Conclusion Small k experiments Search methods Directed minimizer \(k=1\), \(w=2\) \(k=1\), \…

Table of Contents Overview Rust features Basics Basic syntax Expressions everywhere!

Table of Contents Paper summary Intro Prelims Related work Sparse and skew hashing Remarks Ideas \[\newcommand{\S}{\mathcal{S}}\] Paper summary Link to heading Intro Link to heading SsHash (Pibiri 2022) is a datastructure for indexing kmers.

Table of Contents Paper overview Remarks on the paper Thoughts \[ \newcommand{\A}{\mathcal{A}_\ell} \newcommand{\T}{\mathcal{T}_\ell} \] These are some notes on Bidirectional String Anchors (Loukides, Pissis, and Sweering 2023), also called bd-anchors.

Table of Contents External links The problem Initial solution: 105s First flamegraph Bytes instead of strings: 72s Manual parsing: 61s Inline hash keys: 50s Faster hash function: 41s A new flame graph Perf it is Something simple: allocating the right size:

Table of Contents NtHash Minimizers Robust minimizers Is NtHash injective on kmers?

I recently gave a talk about A*PA at CWI.

Table of Contents Notes Coloured Tree Problem Generic sparse suffix array Sparse suffix array on minimizers Discussion / TODOs Evals These are my running notes on implementing an algorithm for Longest Common Repeat using minimizers.

Table of Contents Monday Fimpera: bloom filter for kmers Progress of tools Order-preserving MPHF of minimizers Algorithmic bottlenecks in SSHash Fourier transform of the human genome?

Table of Contents Lecture 1, 14 November Resources Reader friendlyness Typical problems Lecture 2, 21 November Paragraph level expectations Flow Assignment for next week Lecture 3, 28 November Bad organization Figures References to figures Indicative vs I…

Steps: Clone https://github.com/RagnarGrootKoerkamp/BAPCtools Make an alias to the executable: 1 ln -s ~/git/BAPCtools/bin/tools.py ~/bin/bt Create a new problem: 1 2 3 cd ~/problems bt new_problem my_problem_name cd ~/problems/my_problem_name You now…

Table of Contents Questions and remarks on PTHash paper Ideas for improvement Parameters Align packed vectors to cachelines Prefetching Faster modulo operations Store dictionary \(D\) sorted using Elias-Fano coding How many bits of \(n\) and hash entropy…

Table of Contents Possible speedup?

Table of Contents Problem Input Example Discussion Found the bug Outlook The supplement (download) of the Loving, Hernandez, and Benson (2014) paper introduces a \(15\) operation version of Myers (1999) bitpacking algorithm, which uses \(16\) operations w…

Table of Contents Shortest path algorithms .. .. in general .. for circuit design Bucket queues Shortest path algorithms by Hadlock Grid graphs Strings Spouge’s computational volumes This note summarizes some papers I was reading while investigating the h…

Table of Contents Introduction Research plan Improve query performance using Heavy-Light Decomposition Add more query types Extend to non-exact suffix-prefix-overlap that allows for read errors Implement an algorithm to build string graphs, and possibly a…