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
- Nathalie Gocht
- Nicola Cotumaccio (ORCID: https://orcid.org/0000-0002-1402-5298)
- Alexandru M. F. Tomescu (ORCID: https://orcid.org/0000-0002-2351-5002)
- Veli Mäkinen (ORCID: https://orcid.org/0000-0003-4454-1493)
- Alexander Schliep (ORCID: https://orcid.org/0000-0002-3555-3188)
Institutions
- University of Helsinki (FI)
- Brandenburg University of Technology Cottbus-Senftenberg (DE)
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