Skip lists directionnelles et recherche de voisins sur hyper-cube. Applications au ``drug design''

Parmi les m\'ethodes r\'ecentes de conception de mol\'ecules pharmaceutiques, la synth\`ese combinatoire consiste comme son nom l'indique \`a synth\'etiser de fa\c con virtuelle des ensembles gigantesques de mol\'ecules \`a partir de grammaires. Mais tous les produits form\'es n'ayant pas le m\^eme int\'er\^et, \`a la synth\`ese succ\`ede g\'en\'eralement une op\'eration de regroupement des mol\'ecules par ``similarit\'e'' et taille homog\`enes. En termes algorithmiques, le probl\`eme revient alors \`a chercher des paires de points ``voisins'' sur un hyper-cube de grande dimension ---par exemple $d=1500$ pour $n=10^4$ mol\'ecules.

Les m\'ethodes classiques d'algorithmique g\'eom\'etrique (diagrammes de Vorono\" \i, box-trees, \ldots) souffrant de constantes exponentielles en la dimension, nous pr\'esenterons une solution \`a ce probl\`eme fond\'ee sur des skip lists directionnelles. Typiquement, les calculs qui en r\'esultent sont 50 fois plus rapides que ceux des algorithmes na\"\i fs ou li\'es aux r\'eseaux de neurones de type Kohonen. Nous montrerons cependant que l'analyse de ces structures de donn\'ees est reli\'ee d'une certaine fa\c con aux syst\`emes de Sperner, et donc difficile.