Bonjour,

Je bosse dans la bioinformatique, et j'e bosse sur une puce a ADN.
Le problème est le suivant :
Je dois selectionner le plus petit nombre de sondes possibles qui fixeront toutes les sequences ADN (des cibles) en présence.

Les données :
Pour chaque sonde, j'ai le nombre de cibles qu'elle fixera.
Je connais le nombre total de cible qui est 148.
J'ai approximativement 800 000 sondes.

Mon algo actuel :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
Tant qu'on a pas recupéré les 148 cibles
    Parcourir la liste de sonde a la recherche de celle qui ajoute le plus de nouvelles cibles
    Ajouter cette sonde a la liste de sondes selectionnées
    Ajouter cette liste de cible a la liste de cible des sondes selectionnées
fin tant que
De cette sorte, je desends a 12 sondes.
Tester toutes les combinaisons de 800 000 sondes est impossible !
Mais j'ai bon espoir de trouver une piste d'algo heuristique ou stochastique qui me permettra d'augmenter ce score, grace a votre aide

Merci,
Z.