Selecting Chromosomes for Polygenic Traits: Algorithms and Complexity
Cet article définit et analyse le problème NP-complet de la sélection de blocs génomiques à partir de multiples génomes sources afin d'optimiser des traits polygéniques, en proposant une suite d'algorithmes — incluant un solveur de type Branch-and-Bound certifié, une heuristique rapide de descente de coordonnées par blocs, et une relaxation par programmation semi-définie — qui fournissent collectivement des solutions optimales ou quasi optimales avec des garanties théoriques et une validation empirique sur des simulations à l'échelle de la levure.