# 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.

## 2 Minimizers

### 2.1 Mod-minimizer

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

### 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**: PDF, bioRxiv**Code**: minimizer implementations, ILP & analysis

### 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.

## 3 High throughput bioinformatics

### 3.1 PTRHash

Fast and small minimal perfect hash function:

### 3.2 Fast random minimizers

A 10x faster implementation of random minimizers.

### 3.3 One Billion Row Challenge

While not bioinformatics, this is a popular post: