Coding agents improve DNA barcode sets with edit distance codes
Coding Agents for Coding Theory
Information TheoryArtificial IntelligenceMachine Learning
Summary
The authors explored using a language model coding agent to tackle hard problems in coding theory, specifically finding sets of four-letter words like DNA barcodes that differ sufficiently from each other. They let the agent write code to check and search for these sets while a human chose the problem and verified results. Using classical symmetry restrictions, they found bigger sets than previously known, improving best known codes of a certain length and edit distance. The study also highlighted common errors in verifying intermediate results that can mislead further searches, showing that carefully checking only final answers is not enough.
What this means in practice
- •For bioinformatics developers: Create larger DNA barcode libraries that minimize confusion by maximizing sequence differences, improving species identification tools.
- •For error correction system engineers: Use enhanced code construction methods to design codes that keep codewords far apart by edit distance, aiding sequence-based communication error detection.
Authors
Abraham Yeung
Abstract
We spent five weeks using an LLM coding agent on open problems in coding theory: finding large sets of four-letter words, such as DNA barcodes, that stay far apart in edit distance. The agent wrote the verifiers and search code; a human chose the problem and set the verification protocol. Restricting the search to codes with a prescribed symmetry, a classical technique, shrank the problem about fourfold and raised the best known code of length 6 and minimum edit distance 3 from 114 to 120 words ($E_4(6,3) \geq 120$). The same pipeline improved twelve further lower bounds at lengths 6 to 9 and distances 3 to 6. We give the failures equal space. Our own search stopped at 116 and recorded the last symmetry class as topping out at 112; a second agent session, running the same search with a better operator, found the 120. A later verdict that the method did not carry over to length 7 was wrong for the same reason, and an earlier instance cost three weeks. Each time, an intermediate result was written down, never rechecked, and treated as a fact that ruled out further search. Checking final outputs, as our protocol required, does not catch such errors.