Discussion :

[MAROIS]

Bonjour,
je suis actuellement en stage de bio informatique et j'aurais besoin d'aide.
En fait, je dois developper un programme qui compare des sequence d'acides aminé (que l'on peut apparenter a des chaines de caractere de longueurs de 300 caracteres en moyenne) en grand nombre (quelques centaines...). Sachant qu'un autre stagiaire a deja implémenté un algorithme basique (pas mauvais mais de maniere naturelle) qui plante pour une base superieure a 25 sequences...
Mon probleme est donc de trouver un algorithme tres EFFICACE de comparaison de beaucoup de chaines de caracteres entre elles pour rechercher les similitudes, les distances entre les similitudes etc...
Donc si vous aviez quelques idées.... bah ce serait cool...
Voila, merci.

[ronan99999]

Tu peux essayer la distance d'edition

[MAROIS]

C'est a dire, c'est quoi exactement la distance d'edition ?

[nicolas581]

Je vais être rapide par manque de temps et te donner quelques pistes à explorer.
La distance d'édition est grosso modo le coût pour passer d'une chaîne à l'autre en terme de substitution, de destruction ou de de création. Chacune de ces opérations étant affectées à un coût. Souvent c(sub) = 1 et c(des) = c(creat) =0.5. Une substitution pouvant être vu comme une destruction et une création.
L'algorithme classique pour traiter ce problème est l'algorithme de Wagner et Fisher, c'est un algorithme qui est dynamique. Tout bon moteur de recherche devrait permettre de le sortir. Si les mots à comparer sont de taille l et m l'algo est de complexité O(l*m) mieux que l'ancien stagiaire ?
En espérant que ça t'aide.

PS : Peux-tu m'indiquer par MP dans quelle boîte tu fais ton stage, car c'est très intéressant, merci.

[ronan99999]

http://www.merriampark.com/ld.htm


et voili!

Je m'en suis servis pour tout à fait autre chose mais il est souvent fait référence à celle-ci en bio-inf

[MAROIS]

Je ne sais pas si ca va me servir, mais merci quand meme.
Je viens de voir mon maitre de stage et il a préfére opter pour un arbre etiqueté qui, d'apres lui, est beaucoup mieux adapté a cette demande particuliere (ce n'est en fait, pas une bete comparaison de difference entre sequence mais c'est un peu plus pointu que ce que j'avais pensé au premier abord).
Voila, sinon, pour nicolas, je ne fais pas mon stage dans une boite privé mais c'est mon université qui travaille en colaboration avec quelques laboratoires de recherche qui avait mailé une proposition de stage et a laquelle j'ai repondu.