Algorithmes de comparaison approximative de chaînes de caractères

Question

Au travail, nous avons souvent besoin de trouver une chaîne de la liste des chaînes de caractères qui est la plus proche d'une autre chaîne de caractères en entrée. Actuellement, nous utilisons l'algorithme de Needleman-Wunsch. Cet algorithme renvoie souvent un grand nombre de faux positifs (si nous fixons le score minimum trop bas), parfois il ne trouve pas de correspondance quand il le devrait (lorsque le score minimum est trop élevé) et, la plupart du temps, nous devons vérifier les résultats à la main. Nous avons pensé que nous devions essayer d'autres alternatives.

Avez-vous des expériences avec les algorithmes ? Savez-vous comment les algorithmes se comparent les uns aux autres ?

J'aimerais vraiment avoir des conseils.

PS : Nous codons en C#, mais vous ne devriez pas vous en soucier - je m'interroge sur les algorithmes en général.

---

Oh, je suis désolé d'avoir oublié de le mentionner.

Non, nous ne l'utilisons pas pour faire correspondre des données en double. Nous avons une liste de chaînes de caractères que nous recherchons - nous l'appelons search-list. Ensuite, nous devons traiter des textes provenant de diverses sources (comme les flux RSS, les sites Web, les forums, etc.) - nous extrayons des parties de ces textes (il existe des ensembles entiers de règles pour cela, mais ce n'est pas pertinent) et nous devons les comparer à la liste de recherche. Si la chaîne de caractères correspond à l'une des chaînes de caractères de la liste de recherche, nous devons effectuer un traitement supplémentaire de la chose (ce qui n'est pas non plus pertinent).

Nous ne pouvons pas effectuer la comparaison normale, car les chaînes de caractères extraites des sources extérieures comprennent, la plupart du temps, des mots supplémentaires, etc.

De toute façon, ce n'est pas pour la détection des doublons.

Answer 1

OK, Needleman-Wunsch (NW) est un aligneur classique de bout en bout ("global") issu de la littérature bioinformatique. Il y a longtemps, il était disponible sous forme de "align" et "align0" dans le paquetage FASTA. La différence était que la version "0" n'était pas aussi biaisée pour éviter le end-gapping, ce qui permettait souvent de favoriser plus facilement les correspondances internes de haute qualité. Smith-Waterman, je suppose que vous le savez, est un aligneur local et est la base originale de BLAST. FASTA avait également son propre aligneur local, qui était légèrement différent. Toutes ces méthodes sont essentiellement des méthodes heuristiques pour estimer la distance de Levenshtein pertinente pour une métrique de notation pour les paires de caractères individuelles (en bioinformatique, souvent donnée par Dayhoff/"PAM", Henikoff&Henikoff, ou d'autres matrices et généralement remplacée par quelque chose de plus simple et reflétant plus raisonnablement les remplacements dans la morphologie linguistique des mots lorsqu'elle est appliquée au langage naturel).

Ne soyons pas trop regardants sur les étiquettes : La distance de Levenshtein, telle qu'elle est référencée dans la pratique du moins, est essentiellement une distance d'édition et vous devez l'estimer parce qu'il n'est pas possible de la calculer de manière générale et qu'il est coûteux de la calculer exactement, même dans des cas particuliers intéressants : l'eau devient vite profonde dans ce cas, et nous avons donc des méthodes heuristiques de longue date et de bonne réputation.

Pour ce qui est de votre propre problème, il y a plusieurs années, j'ai dû vérifier l'exactitude de courtes lectures d'ADN par rapport à une séquence de référence connue pour être correcte et j'ai mis au point quelque chose que j'ai appelé "alignements ancrés".

L'idée est de prendre votre jeu de chaînes de référence et de le "digérer" en trouvant tous les endroits où une sous-chaîne de N caractères donnée apparaît. Choisissez N de manière à ce que le tableau que vous construisez ne soit pas trop grand, mais aussi de manière à ce que les sous-chaînes de longueur N ne soient pas trop fréquentes. Pour les petits alphabets comme les bases de l'ADN, il est possible de trouver un hachage parfait sur des chaînes de N caractères, de faire une table et d'enchaîner les correspondances dans une liste liée à partir de chaque emplacement. Les entrées de la liste doivent identifier la séquence et la position de départ de la sous-chaîne qui correspond à l'emplacement dans la liste duquel elles apparaissent. Ce sont des "points d'ancrage" dans la liste des chaînes à rechercher auxquels un alignement NW est susceptible d'être utile.

Lors du traitement d'une chaîne de requête, vous prenez les N caractères commençant à un certain décalage K dans la chaîne de requête, vous les hachurez, vous recherchez leur emplacement, et si la liste de cet emplacement n'est pas vide, vous parcourez tous les enregistrements de la liste et vous effectuez des alignements entre la chaîne de requête et la chaîne de recherche référencée dans l'enregistrement. Lors de ces alignements, vous alignez la chaîne d'interrogation et la chaîne de recherche. à l'adresse l'ancre et extraire une sous-chaîne de la chaîne de recherche qui a la même longueur que la chaîne d'interrogation et qui contient cette ancre au même décalage, K.

Si vous choisissez une longueur d'ancre N suffisamment longue, et un ensemble raisonnable de valeurs de décalage K (elles peuvent être réparties sur toute la chaîne de requête ou être limitées à des décalages faibles), vous devriez obtenir un sous-ensemble d'alignements possibles et souvent des gagnants plus clairs. Typiquement, vous voudrez utiliser l'aligneur NW, moins biaisé par les extrémités, comme align0.

Cette méthode essaie d'augmenter un peu le NW en limitant son entrée et cela a un gain de performance car vous faites moins d'alignements et ils sont plus souvent entre des séquences similaires. Une autre bonne chose à faire avec votre aligneur NW est de lui permettre d'abandonner après une certaine quantité ou longueur d'écart pour réduire les coûts, surtout si vous savez que vous ne verrez pas ou ne serez pas intéressé par des correspondances de qualité moyenne.

Enfin, cette méthode a été utilisée sur un système avec de petits alphabets, avec K limité aux 100 premières positions de la chaîne de requête et avec des chaînes de recherche beaucoup plus grandes que les requêtes (les lectures d'ADN étaient d'environ 1000 bases et les chaînes de recherche étaient de l'ordre de 10000, donc je cherchais des correspondances approximatives de sous-chaînes justifiées par une estimation de la distance d'édition spécifiquement). L'adaptation de cette méthodologie au langage naturel nécessitera une réflexion approfondie : vous perdez en taille d'alphabet mais vous gagnez si vos chaînes de requête et de recherche sont de longueur similaire.

Quoi qu'il en soit, le fait de permettre l'utilisation simultanée de plusieurs ancres provenant de différentes extrémités de la chaîne d'interrogation pourrait être utile pour filtrer davantage les données fournies à NW. Si vous faites cela, soyez prêt à envoyer des chaînes qui se chevauchent et qui contiennent chacune une des deux ancres à l'aligneur, puis à réconcilier les alignements... ou éventuellement à modifier NW pour mettre l'accent sur le fait de garder vos ancres intactes pendant un alignement en modifiant les pénalités pendant l'exécution de l'algorithme.

J'espère que cela vous sera utile ou du moins intéressant.

Answer 2

En ce qui concerne la distance de Levenstein, vous pouvez la normaliser en divisant le résultat par la longueur de la chaîne la plus longue, de manière à obtenir un nombre compris entre 0 et 1 et à pouvoir comparer la distance de deux chaînes de manière significative (l'expression L(A, B) > L(A, C), par exemple, n'a aucun sens si vous ne normalisez pas la distance).

Answer 3

Nous utilisons le distance de Levenshtein pour vérifier les doublons de clients dans notre base de données. Cela fonctionne très bien.

Answer 4

Les algorithmes alternatifs à prendre en compte sont agrep ( Entrée Wikipedia sur agrep ), FASTA et BLAST algorithmes de mise en correspondance de séquences biologiques. Il s'agit de cas particuliers de correspondance approximative de chaînes de caractères également dans le Dépôt d'algorithmes de Stony Brook . Si vous pouvez spécifier les façons dont les chaînes de caractères diffèrent les unes des autres, vous pourrez probablement vous concentrer sur un algorithme adapté. Par exemple, aspell utilise une variante de la distance "soundslike" (soundex-métaphone) en combinaison avec une distance "clavier" pour tenir compte des mauvais orthographes et des mauvais dactylographes.

Answer 5

Utilisez Index FM avec Backtracking, similaire à celui de l'article Noeud papillon aligneur flou