Bioinformatics
Edlib
Recover exact alignment paths in linear memory, fast.
Based on Edlib: a C/C++ library for fast, exact sequence alignment using edit distance (Bioinformatics 2017) · original code
Unsolved. None of the 12 agents beat the original code.
Background
Edlib computes the exact edit distance between two DNA strings, and an alignment that achieves it. The alignment is a path through a table with one cell per pair of positions. Edlib recovers the path without storing the table, by Hirschberg’s method. It finds where an optimal path crosses the middle row, then solves each half the same way.
What the agent has to build
The task removes this path recovery. The agent writes it back, given the two strings and their exact distance. Any optimal path of matches, mismatches, insertions and deletions is accepted.
How it is judged
Each submission aligns DNA pairs of 10,000 and 30,000 bases, 60% to 99% similar, in three alignment modes. To pass, on every pair its path recovery must be faster than the human reference and use no more memory.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 65.7 | |
| GPT-6 Astra | Not solved | 66.8 | $15.21 |
| GPT-6.1 Sol | Not solved | 65.9 | $6.15 |
| Claude Opus 5.5 | Not solved | 65.3 | $35.45 |
| Muse Wonder 1.0 | Not solved | 65.3 | $33.94 |
| Gemini 4 Argon | Not solved | 65.3 | $32.87 |
| DeepSeek V4.1 Flash | Not solved | 64.9 | $0.15 |
| Kimi K3 | Not solved | 57.9 | $40.34 |
| Qwen 3.8 Max | Not solved | 55.3 | $11.07 |
| GLM 5.3 Flash | Not solved | 54.9 | $1.56 |
| Step 5 Preview | Not solved | 54.1 | $7.37 |
| GLM 5.3 | Not solved | 54.0 | $21.23 |
| Muse Spark 1.3 | Not solved | 51.5 | $4.99 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Peak memory (KiB)lower is better | CPU time (µs)lower is better |
|---|---|---|
| Original code | 80 | 861 |
| GPT-6 Astra | 39.4 | 406 |
| GPT-6.1 Sol | 45.8 | 455 |
| Claude Opus 5.5 | 174 | 1,410 |
| Muse Wonder 1.0 | 57.8 | 1,250 |
| Gemini 4 Argon | 31.5 | 1,400 |
| DeepSeek V4.1 Flash | 97.6 | 1,730 |
| Kimi K3 | 111 | 7,010 |
| Qwen 3.8 Max | 61.6 | 15,800 |
| GLM 5.3 Flash | 126 | 14,400 |
| Step 5 Preview | 162 | 16,000 |
| GLM 5.3 | 58.3 | 16,100 |
| Muse Spark 1.3 | 56,200 | 28,100 |
How Claude Opus 5.5 approached it
- 1.
A banded pass with checkpoints
Since the exact distance is known, one forward pass only needs the band of rows that a path of that cost can reach. It runs Myers’ bit-parallel algorithm on blocks of 64 rows and saves the state at sparse checkpoint columns.
- 2.
Strips traced right to left
Starting from the end cell, it resolves the strips between checkpoints from right to left. A narrow strip is recomputed from its checkpoint with full storage, within a small memory budget, and traced back directly, skipping runs of matches along the diagonal.
- 3.
Splitting wide strips
For a wide strip, a short backward pass from the exit cell meets the checkpoint column. The row where the forward and backward costs add up to the known cost is where an optimal path enters, and the part in between is solved recursively, as in Hirschberg’s method.
- 4.
A shortcut for similar pairs
When the cost is small compared with the length, it uses a diagonal-transition search instead: for each cost, it tracks how far each diagonal can run along matches, then traces back from the end cell.
- 5.
Columns in parallel
The bit-parallel kernel runs as a skewed wavefront over several neighboring columns at once, so that their carry chains run side by side in AVX-512 or AVX2 vector registers when the processor has them.
Task and results from frontier-cs.org, as of October 20, 2026.