Discussion :

[Zwiter]

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.

[ToTo13]

Bonjour,

pourquoi ne testes tu pas une recherche tabou. Ca convient parfaitement à tout ce qui est problème binaire.

[Zwiter]

Merci de ta réponse.
Je ne connais pas la recherche tabou, mais j'ai une piste pour commencer mes recherches !
Z.

[pseudocode]

C'est un problème de "Partial Set Cover", comme dans les systèmes réducteurs ?

[souviron34]

une idée serait de trier les sondes par nombre de cibles (qsort).

[Loïc B.]

Dans ce cas, (presque académique, je t'envie), j'utiliserais une optimisation par Branch & Bound.

En gros tu poses toutes les combinaisons possibles sous forme d'un arbre, et tu te rends compte que le nombre est gigantesque. Impossible de toutes les explorer ! C'est là que l'algo Branch & Bound intervient en supprimant en cours de route des pans entiers de ton arbre que l'on sait non intéressants sans l'explorer pour autant en entier.

Alors dans ton cas, ton arbre aurait une profondeur variable (mais pas vraiment en fait en formalisant bien comme il faut), et tu chercherais en fait les branches les plus courtes, ce qui s'intègre parfaitement dans cet algorithme au prix d'une petite modif.

N'hésite pas à me contacter pour plus de détails, j'adore ce type de problème.

[hlbnet]

Ton algo initial me semble bien adapté : pas excessivement long, ne parcours pas toutes les possibilités et aboutit à une solution qui devrait être en général assez bonne, même s'il n'aboutit pas obligatoirement à la meilleure solution.

En revanche, la solution que tu trouves n'est peut-être pas minimale. C'est-à-dire, qu'il se peut que certaines sondes retenues ne servent finalement à rien. Dans la solution finale, il y a peut-être des sondes qui peuvent être supprimées, sans perdre aucune cible. Ca mériterait d'être vérifié pour éventuellement affiner le résultat et obtenir une solution minimale (à défaut d'être optimale).

D'ailleurs, cela me me fait penser à un autre algo, qui est un peu l'inverse du tiens.

Au départ, on considère que toutes les sondes sont sélectionnées, donc on a bien le maximum de cibles (toutes). Ensuite, on effectue une boucle qui retire une sonde qui n'enlève pas de cible et qui contient un nombre de cible minimal.

En pseudo-code, ça donne ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Retenir à priori toutes les sondes (le maximum de cibles sont trouvées).
Tant qu'on peut enlever une sonde sans perdre de cible
        Rechercher une sonde qui peut être supprimée et qui possède le plus petit nombre de cibles.
        Supprimer cette sonde.
Fin tant que

Comme ton algo initial, il n'y a aucune garantie d'aboutir à une solution optimale. Mais la solution trouvée devrait ne pas être trop mauvaise non plus, tout en étant différente de celle que tu trouves. D'autre part, la solution trouvée par mon algo serait "minimale" dans le sens ou il est impossible de supprimer une sonde sans perdre une cible.

En fait, suivant la configuration de départ, un algo peut aboutir à un meilleur résultat que l'autre. De même, celui proposé par souviron34 est très bon aussi et abouti à une autre solution minimale (mais pas obligatoirement "optimale"), qui suivant la configuration de départ, peut être meilleure ou moins bonne que les notres.

Je pense que tu dois pouvoir "mixer" ses approches de diverses manières.

Tu peux par exemple partir d'une solution minimale (par exemple, celle rendue par mon algorithme ou bien rendue par ton algorithme après "affinage" ou bien rendue par l'algorithme de souviron34) et essayer de "dériver" une meilleure solution de la manière suivante :
1- Ajouter quelques sondes (choisies au hasard ou bien en privilégiant celles qui ont beaucoup de cibles),
2- Supprimer les sondes inutiles selon mon algorithme (celles qui contribuent le moins de cibles sont supprimées en premier).

En partant d'une solution et en faisant plusieurs essais de "raffinage" selon cette méthode (en faisant varier les sondes ajoutées à l'étape 1), tu as des chances trouver une meilleure solution. Tu peux arrêter le raffinage lorsque tu n'arrives plus à améliorer malgré N essais ou en fonction d'une durée.