Projects

1 Pairwise alignment

1.1 A*PA

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, bioRxiv (outdated)
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.

1.2 PA-Bench

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

Code

2 Minimizers

2.1 Mod-minimizer

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

Blogpost, Rust code, C++ code
WABI24 Paper: PDF, bioRxiv, slides

2.2 Density lower bound

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

Blogpost, slides
Paper & Code: Work in progress.

2.3 Practical schemes for small \(k\)

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 much simpler near-optimal scheme based on open and closed syncmers. In collaboration with Daniel Liu and Giulio Ermanno Pibiri.