Discussion :

[Magy_4]

Bonjour,

Est-ce que quelqu'un connaitrais un algorithme de pourcentage de similitude. C'est-à-dire qui puisse me dire si deux fichier sont égaux et à quel taux de pourcentage. Genre le fichier a1 et 80% identique du fichier a2.

Auriez-vous un tel algo dans votre poche? Connaissez-vous un site internet en parlant clairement? J'ai déjà beaucoup cherché sans trop de résultat...

Merci d'avance

Magy_4

[Pierre-Yves VAROUX]

Tu peux regarder du côté de la distance de Levenshtein.
La distance Levenshtein est définie comme le nombre minimal de caractères qu'il faut remplacer, insérer ou effacer pour passer d'une chaine à une autre.

[victorracine]

Salut,

Si tu veux faire un programme qui soit super performant, tu devrais te renseigner du coté de la genomique. Le problème est quasiement le meme, il faut trouver les ressemblence entre 2 genomes qui sont codées avec un nombre de lettres fixées. Par exemples pour l'ADN, on a les lettres A,T,C,G; pour les proteines, on a un nombre limité d'acide aminé dont la sequence forme le code de c'elles ci. De nombreux algorithmes existent à ce sujet la, il y en a de tres tres performent car les sequences à etudier sont monumentales. Le plus performent à ma connaissance est l'algo BLAST http://www.ncbi.nlm.nih.gov/BLAST/blast_overview.html. C'est basé sur la programmation dynamique. Je ne connais pas ton niveau en programmation, mais c'est loin d'etre evidant . Je crois d'ailleur d'il en existe sur de nombreuses distrib de linux (donc surement avec les souces).

bon courage...

Vic

[Magy_4]

Merci pour vos réponses.

J'ai en effet trouver pas mal de chose dans le secteur de la bio. Mais pour ce que j'en ai besion et le temps que j'ai à disposition, je ne peux pas me lancer dedans, car comme vous l'avez dit c'est assez ardu.

Par contre j'ai été voir du côté de l'algo de la distance de Levensthein et la j'ai trouvé mon bonheur, Grâce à cet algo j'ai pu faire mes comparaisons et trouver lequel est le plus similaire.

Donc merci encore pour votre aide.

Magy_4

[Pazz]

Pas besoin d'algo génétiques ici...

Pour calculer le nombre d'insertions ou suppressions à réaliser (pas de remplacement direct), g un algo qui fait mieux que n^2 en moyenne.

je l'explique dans un post sur clubic : http://forum.clubic.com/forum2.php3?post=5755&cat=13&page=1&interface=&config=&cache=&p=1&sondage=&owntopic=&trash=&subcat=&print=

Il m'a fallu un paquet de temps pour le retrouver. Commence par le début, pke on commence sur cet algo, mais ensuite on passe à un autre (et ne tiens pas compte du tout premier post, qui parle du dernier algo traité).

NB : la dernière version que je présente est encore optimisable (je l'ai fait). Et tu dois pouvoir trouver encore mieux sur le net.

Si on accepte les remplacements directs, en général ce n'est pas très pratique. Mais c comme tu veux, c pas plus dur à coder.