Algorithmes approximatifs de correspondance de chaînes
https://stackoverflow.com/questions/49263
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ici, au travail, nous avons souvent besoin de trouver une chaîne dans la liste des chaînes qui correspond le plus à une autre chaîne d'entrée.Actuellement, nous utilisons l’algorithme Needleman-Wunsch.L'algorithme renvoie souvent beaucoup de faux positifs (si nous fixons le score minimum trop bas), parfois il ne trouve pas de correspondance alors qu'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 devrions essayer d'autres alternatives.
Avez-vous des expériences avec les algorithmes ?Savez-vous comment les algorithmes se comparent les uns aux autres ?
J'apprécierais vraiment quelques conseils.
PS :Nous codons en C#, mais vous ne devriez pas vous en soucier – je pose des questions 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 que nous recherchons – nous l’appelons liste de recherche.Et puis 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 complets de règles pour cela, mais cela n'a pas d'importance) et nous devons faire correspondre ceux contre la liste de recherche.Si la chaîne correspond à l'une des chaînes de la liste de recherche, nous devons effectuer un traitement ultérieur de la chose (ce qui n'est pas non plus pertinent).
Nous ne pouvons pas effectuer la comparaison normale, car les chaînes extraites des sources externes incluent la plupart du temps des mots supplémentaires, etc.
Quoi qu'il en soit, ce n'est pas pour la détection des doublons.
La solution
OK, Needleman-Wunsch (NW) est un aligneur classique de bout en bout (« global ») issu de la littérature bioinformatique.Il était disponible depuis longtemps sous les noms "align" et "align0" dans le package FASTA.La différence était que la version "0" n'était pas aussi biaisée pour éviter les écarts de fin, 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 constitue la base originale de BLAST.FASTA avait également son propre aligneur local, légèrement différent.Toutes ces méthodes sont essentiellement heuristiques pour estimer la distance de Levenshtein pertinente pour une métrique de notation pour des paires de caractères individuelles (en bioinformatique, souvent données par Dayhoff/"PAM", Henikoff&Henikoff, ou d'autres matrices et généralement remplacées 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 précieux avec 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 car il n'est pas réalisable de la calculer en général, et il est coûteux de la calculer exactement, même dans des cas particuliers intéressants :l'eau y devient vite profonde, et nous disposons ainsi de méthodes heuristiques de longue et bonne réputation.
Maintenant, concernant 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 trouvé 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 recherchant tous les emplacements où apparaît une sous-chaîne de N caractères donnée.Choisissez N pour que la table que vous construisez ne soit pas trop grande mais aussi pour que les sous-chaînes de longueur N ne soient pas trop courantes.Pour les petits alphabets comme les bases ADN, il est possible de créer un hachage parfait sur des chaînes de N caractères, de créer un tableau et d'enchaîner les correspondances dans une liste chaînée à partir de chaque bac.Les entrées de liste doivent identifier la séquence et la position de départ de la sous-chaîne qui correspond au bac dans la liste duquel elles apparaissent.Ce sont des "ancres" dans la liste des chaînes à rechercher pour lesquelles 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, les hachez, recherchez leur bac, et si la liste de ce bac n'est pas vide, vous parcourez tous les enregistrements de la liste et effectuez des alignements entre la chaîne de requête et la chaîne de recherche référencées dans l'enregistrement.Lors de ces alignements, vous alignez la chaîne de requête et la chaîne de recherche à l'ancre et extrayez une sous-chaîne de la chaîne de recherche qui a la même longueur que la chaîne de requête et qui contient cette ancre au même décalage, K.
Si vous choisissez une longueur d'ancrage N suffisamment longue et un ensemble raisonnable de valeurs de décalage K (elles peuvent être réparties sur la chaîne de requête ou être limitées à de faibles décalages), vous devriez obtenir un sous-ensemble d'alignements possibles et obtiendrez souvent des gagnants plus clairs.En règle générale, vous souhaiterez utiliser l'aligneur NW de type align0, moins biaisé aux extrémités.
Cette méthode tente d'augmenter un peu NW en limitant son entrée, ce qui entraîne un gain de performances car vous effectuez moins d'alignements et ils se font 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 n'allez pas voir ou être 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 quelque 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 sur l'ordre de 10 000, je cherchais donc des correspondances approximatives de sous-chaînes justifiées par une estimation de la distance d'édition spécifiquement).Adapter cette méthodologie au langage naturel nécessitera une réflexion approfondie :vous perdez en taille de l'alphabet mais vous gagnez si vos chaînes de requête et vos chaînes de recherche sont de longueur similaire.
Quoi qu’il en soit, permettre l’utilisation simultanée de plusieurs ancres provenant de différentes extrémités de la chaîne de requête pourrait être utile pour filtrer davantage les données transmises à NW.Si vous faites cela, soyez prêt à envoyer éventuellement des chaînes qui se chevauchent contenant chacune l'une des deux ancres à l'aligneur, puis à réconcilier les alignements...ou éventuellement modifier davantage NW pour mettre l'accent sur le maintien de vos ancres en grande partie intactes lors d'un alignement en utilisant une modification de pénalité pendant l'exécution de l'algorithme.
J'espère que cela sera utile ou du moins intéressant.
Autres conseils
En rapport avec la distance de Levenstein :vous souhaiterez peut-être le normaliser en divisant le résultat par la longueur de la chaîne la plus longue, afin que vous obteniez toujours un nombre compris entre 0 et 1 et que vous puissiez comparer la distance d'une paire de chaînes de manière significative (l'expression L( A, B) > L(A, C) - par exemple - n'a de sens que si vous normalisez la distance).
Les algorithmes alternatifs à examiner sont d'accord (Entrée Wikipédia sur l'accord), FASTA et BLAST algorithmes d’appariement de séquences biologiques.Ce sont des cas particuliers de correspondance de chaîne approximative, également dans le Dépôt d'algorithmes de Stony Brook.Si vous pouvez spécifier en quoi les chaînes diffèrent les unes des autres, vous pourriez probablement vous concentrer sur un algorithme personnalisé.Par exemple, aspell utilise une variante de distance « sonore » (soundex-métaphone) en combinaison avec une distance « clavier » pour s'adapter aussi bien aux mauvais orthographes qu'aux mauvais dactylographes.
Nous utilisons le Distance de Levenshtein méthode pour vérifier les clients en double dans notre base de données.Cela fonctionne plutôt bien.
Utiliser Indice FM avec Backtracking, similaire à celui de Noeud papillon aligneur flou
Afin de minimiser les discordances dues à de légères variations ou erreurs d'orthographe, j'ai utilisé l'algorithme Metaphone, puis la distance de Levenshtein (mise à l'échelle de 0 à 100 en pourcentage) sur les encodages Metaphone pour une mesure de proximité.Cela semble avoir assez bien fonctionné.
Pour développer la réponse de Cd-MaN, il semble que vous soyez confronté à un problème de normalisation.Il n'est pas évident de savoir comment gérer les scores entre des alignements de longueurs variables.
Compte tenu de ce qui vous intéresse, vous souhaiterez peut-être obtenir des valeurs p pour votre alignement.Si vous utilisez Needleman-Wunsch, vous pouvez obtenir ces valeurs p à l'aide des statistiques de Karlin-Altschul. http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
BLAST pourra aligner localement et les évaluer à l’aide de ces statistiques.Si vous êtes préoccupé par la vitesse, ce serait un bon outil à utiliser.
Une autre option consiste à utiliser HMMER.HMMER utilise des modèles de Markov profilés cachés pour aligner les séquences.Personnellement, je pense que c'est une approche plus puissante puisqu'elle fournit également des informations de position. http://hmmer.janelia.org/
J'avais l'habitude de travailler avec certaines des données les plus sales que vous puissiez trouver.Une moyenne d'environ 5 000 lignes de données (équivalentes à des centaines de milliers de dollars) à mettre en correspondance était totalement épuisante.Ma première expérience avec la correspondance floue était un algorithme de M. Excel écrit en VBA.Il y avait certains problèmes de cohérence dans la mesure où les choses que je m'attendais à être à zéro pour cent ne l'étaient pas et les choses qui étaient d'environ 60 pour cent ressemblaient plus à 90 pour cent.J'ai donc déménagé à Levenshtein, puis plus tard à Damerau-Levenshtein.Il s'agissait d'une amélioration majeure mais assez lente dans Excel.Ensuite, je suis passé à Jaro-Winkler, mais je l'ai rapidement abandonné peu de temps après.Finalement, en 2016, j'ai écrit le mien (basé sur n-gram) et je l'ai affiné au cours des 2 années suivantes.Aujourd'hui, c'est un module complémentaire appelé Flookup ;vous pouvez l'obtenir sur Google Sheets et voir comment il résiste.
