home on CuriousCoding

Table of Contents Comments Prelims One-to-One One-to-All Report and Count Top-\(K\) A small rant on $τ$-micro-macro trees Ideas for simplification Replace $τ$-micro-macro tree Heavy-Light-Decomposition (HLD) for \(Count\) queries in \(O(\log n)\) time Fin…

These are notes for DSB 2023.

Table of Contents Research Proposal: Near-linear exact pairwise alignment Abstract Introduction and current state of research in the field Goals of the thesis Impact Progress to date Detailed work plan WP1: A*PA v1: initial version WP2: Visualizing aligne…

Table of Contents Complexity analysis Complexity of edit distance Complexity of affine cost alignment Comparison Implementation efficiency Band doubling for affine scores was never implemented WFA vs band doubling for affine costs Conclusion Future work T…

Table of Contents Thoughts and remarks Good Bad My programming language journey Lego mindstorms LabVIEW C++ Python Rust These are some notes on my opinions on Rust after one year of using it.

Select the algorithm to visualize Click the buttons, or click the canvas and use the indicated keys Suffix-array construction is explained here and BWT is explained here.

Table of Contents Linear programming Assumptions Idea for an algorithm This note contains some ideas about linear programming and most-orthogonal faces.

Table of Contents Notation Needleman-Wunsch: where it all begins Dijkstra/BFS: visiting fewer states Band doubling: Dijkstra, but more efficient GapCost: A first heuristic Computational volumes: an even smaller search Cheating: an oracle gave us \(g^*\) A…

Table of Contents Burrows-Wheeler Transformation (BWT) Last-to-first mapping (LF mapping) Pattern matching Visualization Bi-directional BWT These are some notes about the Burrows-Wheeler Transform (BWT), FM-index, and variants.

Some notes regarding the identity \begin{equation} \sum_{k=0}^n \binom{2k}k \binom{2n-2k}{n-k} = 4^n \end{equation} Gould has two derivations: The first, from Jensens equality, (18) in (Jensen 1902; Shijie 1303).

Table of Contents Definitions Proof of Lemma 1 TODO Proof of Lemma 2 This is a proof that Tensor Embedding (Joudaki, Rätsch, and Kahles 2020) with $ℓ^2$-norm preserves the Hamming distance.

Table of Contents Notation Small and Large suffixes Building the suffix array from a smaller one Visualization These are some notes about linear time suffix array (SA) construction algorithms (SACA’s).

Table of Contents Contest strategies Pairwise Alignment using A* Exercises Contest strategies Link to heading Preparation Thinking costs energy!

Table of Contents Motivation Parititioning A* memory by fronts Non-consistent heuristics Front indexing Tracing back the path Here is an idea to reduce the memory usage of A* by only storing one front at a time, similar to what Edlib and WFA do.

Table of Contents Motivation Summary Why is A* slow?

I made an improved version of the Oxford Bioinformatics latex template.

Table of Contents Motivation Path traceback: two strategies Observations What information is needed for path tracing A pragmatic solution Another interpretation Affine costs Conclusion Figure 1: Only the red substitutions and blue indel need to be stored…

Table of Contents Tricks with match bonus or how to fool Dijkstra’s limitations Edit graph Algorithms Potentials Multiple variants Some notes on algorithms WFA A* Extending to different cost models Affine costs Substitution matrices But not local alignment

Table of Contents Notation Naming and style This is a growing list of notation and style decisions Pesho and I made during the writing of our paper, written down so that we don’t have to spend time on it again next time.

Table of Contents Diamond transition or how technicalities can break concepts But let’s take a closer look Conclusion Diamond transition or how technicalities can break concepts Link to heading We assume the reader has some basic knowledge about pairwise…

These are some links and papers on bidirectional A* variants.

cross references: BiWFA GitHub issue It seems that getting the meeting/overlap condition of BiWFA (Marco-Sola et al. (2023), Algorithm 1 and Lemma 2.1) correct is tricky.

These are the slides Pesho Ivanov and I presented at IGGSY 2022 on Astarix and A*PA.

These are some quick notes listing papers related to A* itself and variants.

Benchmarking is harder than you think, even when taking into account this rule.

It’s not the need for faster software that motivates; it’s the mathematical discovery that needs sharing.

Table of Contents Pairwise alignment in subquadratic time Random model Algorithm Seed heuristic Match pruning Analysis Expanded states Excess errors Algorithmic complexity This post is a proof sketch to show that A* with the seed heuristic (Groot Koerkamp…

Table of Contents Gap open Gap close Symmetric alternatives Another symmetry Conclusions cross references: BiWFA GitHub issue In this post I will explore some variations of the recursion used by WFA/BiWFA for the affine version of the diagonal transition…

See also talks & slides below.

This is a growing list of ambiguous terms and their definitions.

Table of Contents Variants of pairwise alignment Cost models Alignment types A chronological overview of global pairwise alignment Algorithms in detail Classic DP algorithms Cubic algorithm of Needleman and Wunsch (1970) A quadratic DP Local alignment Aff…

Note: this post extends the concept of multiple-path pruning presented in Poole and Mackworth (2017).

Papers AStarix: Fast and Optimal Sequence-to-Graph Alignment Fast and Optimal Sequence-to-Graph Alignment Guided by Seeds AStarix is a method for aligning sequences (reads) to graphs: Input A reference sequence or graph Alignment costs \((\Delta_{match},…

Neighbour joining (NJ, paper) is a phylogeny reconstruction method.

Unweighted pair group method with arithmetic mean (UPGMA) is a phylogeny reconstruction method.

Read The F*ing Error When you complain about an error without reading it first.

Important deadlines require important procrastination.

Experiments and their analysis should be reproducible, and all data/figures in a paper should be reviewable.

Table of Contents Background $k$-mers Sketching MinHash Terminology Introduction Spaced $k$-mer Seeded Distance Improving performance Analysis Pruning false positive candidate matches Phylogeny reconstruction Running the algorithm TODO Assembly \[ \newcom…

Let’s go over some reasons for why I’m writing this blog.

Here’s the customary how I made this site using X post.

1 print("Hello, World!")

Table of Contents Spaced \(k\)-mers Minimap SPAdes MUMmer4 BLASR Bowtie 2 Patternhunter Spaced seeds improve \(k\)-mer-based metagenomic classification LoMeX Meeting notes Concepts: Mapping Map a sequence onto a reference genome/dataset Assembly Build a g…

\[ \newcommand{\vp}{\varphi} \newcommand{\A}{\mathcal A} \newcommand{\O}{\mathcal O} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\ed}{\mathrm{ed}} \newcommand{\mh}{\mathrm{mh}} \newcommand{\hash}{\mathrm{hash}} \] Here is an idea for…

Table of Contents Background $k$-mers Sketching MinHash Introduction Hamming Similarity Search Improving performance Analysis Pruning false positive candidate matches Phylogeny reconstruction Running the algorithm Assembly \[ \newcommand{\vp}{\varphi} \ne…

This post goes over some useful utilities I have been using on my Wayland system.

Related posts: Dark mode with Vimium Vimium (Github, Chromium extension) is not only a great way to navigate webpages; it’s also a great help to quickly search many webpages.

Table of Contents My aur packages Some issues I reported/fixed My aur packages Link to heading List on aur.archlinux.org bapctools-git: BAPCtools is used for developing ICPC style programming contest problems. feh-preload-next-image-git: Branch of Feh that

Backlinks: PR for Sway | AUR package sway-inhibit-fullscreen-git Once upon a time, Chromium had a bug where using $mod+f in i3 to fullscreen the Chromium window changed the window to occupy the entire screen, but didn’t actually make Chromium enter full s…

Sway has many commands for switching the active workspace and focused window.