2026-08-27T21:19:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27532 2026-08-27T06:04:08Z ddc:004 open_access

Selecting Chromosomes for Polygenic Traits: Algorithms and Complexity Zuk, Or polygenic scores combinatorial optimization genomic block selection NP-hardness semidefinite programming synthetic genomics We define and study the problem of genomic block selection for multiple complex traits. In this problem, one constructs a genome by selecting different genomic parts (e.g. chromosomes) from different source genomes. The constructed genome is associated with a vector of polygenic scores, obtained by summing the polygenic scores of the different genomic parts, and the goal is to minimize a given loss function of this vector. The problem is motivated by several emerging technologies: chromosome substitution lines in crop breeding, where chromosomal segments from wild relatives are combined to improve polygenic traits such as yield and stress tolerance; chromosome transfer between yeast strains for optimizing complex industrial phenotypes; and chromosomal transplantation technologies in mammalian cells. We suggest and study several natural loss functions relevant for both quantitative and threshold traits, and show that the problem is NP-complete even for a single trait and two copies, yet only weakly so, being pseudo-polynomially solvable for any fixed number of traits. We propose three algorithms with complementary roles: a Branch-and-Bound algorithm that returns the certified global optimum for any monotone loss, a fast Block-Coordinate-Descent (BCD) heuristic with random restarts that applies to any loss, and a semidefinite-programming (SDP) relaxation that provides a certified lower bound on the optimal loss for quadratic losses, and hence an optimality-gap bound when paired with the BCD solution - empirically tight in our experiments. Using the infinitesimal model for genetic architecture, we further derive, for linear losses, a closed-form approximation for the expected gain of block selection relative to random selection across multiple traits. On yeast-scale simulations BCD matches the certified Branch-and-Bound optimum on 100% of threshold-loss instances at 466× the speed, attains a certified optimality gap of at most ≈10% of the SDP lower bound for stabilizing-loss instances, and the realized gain roughly matches the analytic prediction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Or Zuk 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.28 urn:nbn:de:0030-drops-275325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.28 eng https://creativecommons.org/licenses/by/4.0/legalcode