Projects

1 Pairwise alignment Link to heading

A*PA Link to heading

A pairwise aligner based on A*, in collaboration with Pesho Ivanov. A*PA uses A* with new heuristics to speed up global pairwise alignment. A*PA2 is much faster by using a DP-based method.

Code, slides
A*PA paper: PDF, bioRxiv, Bioinformatics (supplement separate)
A*PA2 paper: PDF, (outdated) bioRxiv, WABI/LIPIcs
Talk at CWI: 60 min recording, but unfortunately it does not show the blackboard well.
Blogposts
- Pairwise alignment history
- Computational volumes
- A*PA2, the blogpost version of the paper.
- Local doubling, an idea that didn’t make it into the final paper.

PA-Bench Link to heading

PA-Bench is a benchmarking framework for pairwise aligners, in collaboration with Daniel Liu.

Code

2 Minimizers Link to heading

Open-closed mod-minimizer Link to heading

A minimizer scheme with near-optimal density when \(k\gg w\) and good density when \(k<w\), in collaboration with Giulio Ermanno Pibiri and Daniel Liu.

Blogpost, Rust code, C++ code
WABI24 Paper: PDF, bioRxiv, WABI/LIPIcs, slides
Extended paper: The open-closed mod-minimizer: PDF, bioRxiv

Density lower bound Link to heading

A near-tight lower bound for the density of forward sampling schemes, in collaboration with Bryce Kille.

Blogpost, slides
Paper: PDF, bioRxiv, Bioinformatics
Code: minimizer implementations, ILP & analysis

Practical schemes for small \(k\) Link to heading

While the mod-minimizer is practical and near-optimal for large \(k\), the best schemes for small \(k\) are somewhat slow to compute. Here the goal is to develop a simple and near-optimal schemes.