Algorithms for Designing Therapeutic Oligonucleotides on Pangenome Graphs

Candidate therapeutic oligonucleotide target sites with edit-distance threshold k ≤ 3 can be identified on large human pangenome subgraphs where brute-force fails to finish within 24h.

• Why it matters: Variant-aware oligonucleotide design is needed because genetic diversity can reduce binding affinity at complementary mRNA sites, risking drug development failures.
• What they did: The work models target genetic diversity as a pangenome graph and defines oligonucleotides by covering all paths within edit distance ≤ k, proving NP-hardness for minimal sets at k = 0 and coNP-completeness for verification.
• The result: Algorithmic methods on product graphs and a dynamic-programming lossless filter find feasible solutions, with the filter outperforming baselines and achieving average approximation ratio < 1.5 across over a hundred subgraphs.

AI summary of the abstract · may contain errors · not medical advice · read the paper.