Algorithms for Designing Therapeutic Oligonucleotides on Pangenome Graphs

Designing therapeutic oligonucleotides that act reliably across human genetic diversity requires more than alignment to a single reference genome. Binding affinity of an siRNA or ASO to a usually complementary site in an mRNA target molecule is one main determinant of drug efficacy. Thus, variation in sub-populations can lead to failures in drug development if this variation reduces binding affinity. We provide a first methodological step towards principled, variant-aware design of therapeutic oligonucleotides. The genetic diversity in target genes, or specific regions thereof, is represented as a pangenome graph. We define individual or small sets of suitable therapeutic oligonucleotides by their ability to cover all paths in a directed acyclic graph within a bounded edit distance <= k. Edit distance is used as an accepted proxy to the commonly used binding affinity. We formalize the resulting computational problem and provide complexity results: NP-hardness of identifying such minimal sets even for k =0, and coNP-completeness of verifying the validity of a given set of oligonucleotides. Further, we propose algorithmic approaches operating on a product graph of an automaton (an Aho-Corasick DFA or an Ukkonen DFA) and the pangenome graph, as well as a dynamic programming-based lossless filter. We evaluate the approaches on gene-specific subgraphs of human pangenome graphs and demonstrate favorable performance compared to naive brute-force computation. Our results show that candidate target sites with a threshold of k <= 3 can be identified even for large, complex graphs where the brute-force computation did not complete within 24h. We observe that the dynamic programming-based lossless filter outperforms both product-graph approaches as well as brute-force baselines while maintaining an average approximation ratio < 1.5 across more than a hundred evaluated subgraphs. We also present examples where a small set of oligonucleotides constitutes a feasible solution where no single oligonucleotide with a threshold of k <= 2 covers all paths.

Authors

Institutions

Publication Details

Journal
bioRxiv (Cold Spring Harbor Laboratory)
Published
2026-11-13
DOI
https://doi.org/10.64898/2026.11.07.764582
Primary Topic
Algorithms and Data Compression
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Algorithms for Designing Therapeutic Oligonucleotides on Pangenome Graphs

Nathalie Gocht, Nicola Cotumaccio, Alexandru M. F. Tomescu, Veli Mäkinen et al.
bioRxiv (Cold Spring Harbor Laboratory)
Algorithms and Data Compression
preprint

Algorithms for Designing Therapeutic Oligonucleotides on Pangenome Graphs

Nathalie Gocht, Nicola Cotumaccio, Alexandru M. F. Tomescu, Veli Mäkinen, Alexander Schliep
preprint en

Abstract

Designing therapeutic oligonucleotides that act reliably across human genetic diversity requires more than alignment to a single reference genome. Binding affinity of an siRNA or ASO to a usually complementary site in an mRNA target molecule is one main determinant of drug efficacy. Thus, variation in sub-populations can lead to failures in drug development if this variation reduces binding affinity. We provide a first methodological step towards principled, variant-aware design of therapeutic oligonucleotides. The genetic diversity in target genes, or specific regions thereof, is represented as a pangenome graph. We define individual or small sets of suitable therapeutic oligonucleotides by their ability to cover all paths in a directed acyclic graph within a bounded edit distance <= k. Edit distance is used as an accepted proxy to the commonly used binding affinity. We formalize the resulting computational problem and provide complexity results: NP-hardness of identifying such minimal sets even for k =0, and coNP-completeness of verifying the validity of a given set of oligonucleotides. Further, we propose algorithmic approaches operating on a product graph of an automaton (an Aho-Corasick DFA or an Ukkonen DFA) and the pangenome graph, as well as a dynamic programming-based lossless filter. We evaluate the approaches on gene-specific subgraphs of human pangenome graphs and demonstrate favorable performance compared to naive brute-force computation. Our results show that candidate target sites with a threshold of k <= 3 can be identified even for large, complex graphs where the brute-force computation did not complete within 24h. We observe that the dynamic programming-based lossless filter outperforms both product-graph approaches as well as brute-force baselines while maintaining an average approximation ratio < 1.5 across more than a hundred evaluated subgraphs. We also present examples where a small set of oligonucleotides constitutes a feasible solution where no single oligonucleotide with a threshold of k <= 2 covers all paths.

bioRxiv (Cold Spring Harbor Laboratory)
University of Helsinki (FI), Brandenburg University of Technology Cottbus-Senftenberg (DE)
Algorithms and Data Compression
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon