Algorithme d'appariement rapide des chaînes à incompatibilité k

10

Je suis à la recherche d'un algorithme d'appariement rapide de chaînes k-mismatch. Étant donné une chaîne de motif P de longueur m et une chaîne de texte T de longueur n, j'ai besoin d'un algorithme rapide (temps linéaire) pour trouver toutes les positions où P correspond à une sous-chaîne de T avec au plus k mésappariements. Ceci est différent du problème des différences k (distance d'édition). Un décalage implique que la sous-chaîne et le motif ont une lettre différente dans au plus k positions. Je n'ai vraiment besoin que de k = 1 (au plus 1 décalage), donc un algorithme rapide pour le cas spécifique de k = 1 suffira également. La taille de l'alphabet est 26 (texte anglais insensible à la casse), donc l'espace requis ne devrait pas augmenter trop rapidement avec la taille de l'alphabet (par exemple, l'algorithme FAAST, je crois, prend un espace exponentiel dans la taille de l'alphabet, et ainsi de suite). convient uniquement aux séquences de protéines et de gènes).

Une approche basée sur la programmation dynamique aura tendance à être O (mn) dans le pire des cas, ce qui sera trop lent. Je crois qu'il y a des modifications de l'algorithme de Boyer-Moore pour cela, mais je ne suis pas en mesure de mettre la main sur de tels papiers. Je n'ai pas d'abonnement pour accéder aux revues ou publications académiques, donc toutes les références devront être dans le domaine public.

J'apprécierais grandement tous les pointeurs ou références à des documents librement disponibles, ou l'algorithme lui-même pour ce problème.

Paresh
la source
2
Si le motif est fixe (mais le texte à faire varier), vous pouvez potentiellement créer un automate fini et exécuter le texte à travers cela. Il existe également des algorithmes utilisant des arbres de suffixes (généralement bons si le texte est constant et le motif varie, mais également applicables si les deux varient), vous pourrez peut-être trouver des références sur le Web. (N'ajoutant pas encore de réponse car je ne suis pas très sûr des algorithmes basés sur l'arborescence des suffixes, si quelqu'un le sait, n'hésitez pas à ignorer ce commentaire).
Aryabhata
@Aryabhata Merci! Le motif et le texte changent. Dans ce contexte, la construction d'un automate fini serait trop coûteuse, en particulier si l'on incluait la portée pour 1 incompatibilité. Quant aux arbres de suffixe / tableaux de suffixes, je ne les ai jamais utilisés et je les connais peu, mais j'avais l'impression qu'ils sont lents à construire et efficaces principalement pour une correspondance exacte. Mais j'explorerai cette option plus en détail. Tout pointeur dans cette direction ou dans toute autre direction serait très utile!
Paresh
1
Non, les arborescences de suffixes peuvent également être utilisées pour des correspondances approximatives. Au moins le wiki le prétend: en.wikipedia.org/wiki/Suffix_tree
Aryabhata

Réponses:

5

Les tableaux de suffixes peuvent être utilisés pour ce problème. Ils contiennent les positions de départ de chaque suffixe de la chaîne triées par ordre lexicographique. Même s'ils peuvent être construits naïvement dans la complexité , il existe des méthodes pour les construire dans la complexité . Voir par exemple ceci et cela . Appelons ce tableau de suffixes SA.Θ ( n )O(nlogn)Θ(n)

Une fois que le tableau de suffixes a été construit, nous devons construire un tableau LCP (Longest Common Prefix) pour le tableau de suffixes. Le tableau LCP stocke la longueur du préfixe commun le plus long entre deux préfixes consécutifs dans le tableau de suffixes (suffixes lexicographiques consécutifs). Ainsi, LCP [i] contient la longueur du préfixe commun le plus long entre SA [i] et SA [i + 1]. Ce tableau peut également être construit en temps linéaire: voir ici , ici et ici pour quelques bonnes références.

Maintenant, pour calculer la longueur de la commune le plus long préfixe à tous les deux suffixes dans l'arbre suffixe ( au lieu de suffixes consécutifs), nous avons besoin d'utiliser une RMQ structure de données. Il a été montré dans les références ci-dessus (et peut être vu facilement si le tableau est visualisé comme un arbre de suffixe), que la longueur du préfixe commun le plus long entre deux suffixes ayant des positions et ( ) dans le tableau de suffixes , peut être obtenu sous la forme . Une bonne RMQ peut prétraiter le tableau en temps ou et répondre aux requêtes de la forme dansv u < v m i n u < = k < = v - 1 L C P [ k ] L C P O ( n ) O ( n log n ) L C P [ u , v ] O ( 1 )uvu<vminu<=k<=v1LCP[k]LCPO(n)O(nlogn)LCP[u,v]O(1)temps. Voir ici pour un algorithme RMQ succint, et ici pour un bon tutoriel sur les RMQ, et la relation (et les réductions) entre LCA et RMQ. Cela a une autre belle approche alternative.

Avec ces informations, nous construisons le tableau de suffixes et les tableaux associés (comme décrit ci-dessus) pour la concaténation des deux chaînes avec un délimiteur entre les deux (comme T # P, où '#' n'apparaît dans aucune chaîne). Ensuite, nous pouvons effectuer k correspondance de chaîne de mésappariement en utilisant la méthode "kangourou". Ceci et cela expliquent la méthode kangourou dans le contexte des arbres de suffixes, mais peuvent également être directement appliqués aux tableaux de suffixes. Pour chaque index du texte , trouvez le du suffixe de commençant à et le suffixe de commençant à 0. Cela donne l'emplacement après lequel le premier décalage se produit lors de la correspondance deiTLCPTiPPavec . Soit cette longueur . Ignorez le caractère incompatible dans et et essayez de faire correspondre les chaînes restantes. Autrement dit, trouvez à nouveau le de et . Répétez cette opération jusqu'à ce que vous obteniez non-concordances ou les finitions de chaîne. Chaque est . Il existe pour chaque indice de , ce qui donne une complexité totale de .T[i]l0TPLCPT[i+l0+1]P[l0+1]kLCPO(1)O(k) LCPiTO(nk)

J'ai utilisé un RMQ plus facile à implémenter donnant une complexité totale de , ou si , mais il peut aussi être fait en comme décrit ci-dessus. Il peut y avoir d'autres méthodes directes pour ce problème, mais il s'agit d'une approche puissante et générique qui peut être appliquée à de nombreux problèmes similaires.O(nk+(n+m)log(n+m))O(nk+nlogn)m=O(n)O(nk)

Paresh
la source
Génial! J'ai une lecture sur ma liste TODO maintenant :-)
Aryabhata
Le lien siam.org dans le deuxième paragraphe est rompu, mais le document lié peut être trouvé ici epubs.siam.org/doi/pdf/10.1137/1.9781611972917.3
leecbaker
4

Ci-dessous se trouve un algorithme attendu (qui peut être étendu à d'autres , ce qui en fait ). (Je n'ai cependant pas fait les calculs pour prouver qu'il en est ainsi).O(n+m)kO(nk+m)

L'idée est similaire à l' algorithme de hachage déroulant Rabin-Karp pour les correspondances de sous-chaînes exactes.

L'idée est de séparer chaque chaîne de longueur en blocs de taille et chaque calculer la valeur de hachage pour chaque bloc de roulement (donnant valeurs de hachage) et comparer ces valeurs de hachage contre l'une à partir du motif.m2km/2k2k2k

Nous autorisons au plus disparités dans ces valeurs.k

Si plus de asymétries se produisent, nous rejetons et passons. Sinon, nous essayons de confirmer une correspondance approximative.k

Je m'attends (mise en garde: je ne l'ai pas essayé moi-même), ce sera probablement plus rapide dans la pratique, et peut-être plus facile à coder / à maintenir, que d'utiliser une approche basée sur un arbre de suffixes.

Aryabhata
la source
Besoin juste d'une clarification. Par ".. séparer chaque chaîne de longueur m en blocs de 2k de taille m / 2k chacun ...", vous voulez dire que séparer chaque sous-chaîne de longueur m en T (de longueur n) en blocs de 2k. Et ce hachage peut être calculé en O (n) par la méthode du hachage par roulement. Ensuite, la chaîne de motif sera également divisée en blocs de 2k, et les hachages correspondants seront comparés, ce qui permettra à au moins k blocs de ne pas correspondre. Si c'est le cas, alors nous pourrions potentiellement éliminer tous les cas où le nombre de discordances est supérieur à k. Ai-je bien compris?
Paresh
@Paresh: Oui, vous avez bien compris, sauf qu'il y a hachages, c'est , plutôt que . Ω ( n k ) O ( n )kΩ(nk)O(n)
Aryabhata
J'aime cette approche! Pourtant, cette approche est rapide en général, mais se dégrade en O (mnk) si le nombre de correspondances est élevé (O (n) correspondances). En gardant cela à l'esprit, j'ai maintenu deux hachages roulants, en supposant que les deux ne peuvent pas avoir de collision pour la même entrée (je ne l'ai pas fait mathématiquement car je voulais voir la vitesse). De cette façon, nous n'avons pas à vérifier une correspondance caractère par caractère si les deux hachages sont d'accord. C'est assez rapide en général, mais cela aussi est lent si le nombre de correspondances est important. Avec cela et avec la façon dont vous l'avez suggéré, c'était lent pour les gros matchs.
Paresh
Cela pourrait être rendu plus rapide dans le pire des cas si nous divisons le texte en blocs de taille au lieu de blocs . Le motif sera également divisé en blocs (+1 sinon carré parfait), et nous comparerons chacun des blocs. Ce sera plus lent que votre approche si le nombre de discordances est petit, mais je pense que cela ne devrait être que dans le pire des cas (je n'ai pas vérifié cela correctement cependant). Je n'ai pas essayé cela, mais je vais d'abord explorer les arbres / tableaux de suffixes comme vous l'avez suggéré. Ils semblent offrir de bonnes limites. Merci! m/2kmm/2k O(nkmO(nkm)
Paresh
@Paresh: Vous ne pouvez pas le voir (dans l'historique des révisions), mais j'avais initialement l' approche , mais je l'ai changée pour l'actuelle. Je pense qu'il est préférable d' utiliser . Vous calculez inutilement trop de valeurs de hachage. Bien sûr, ce qui est mieux dépend de vos données. Bien sûr, au lieu de , vous pouvez également essayer ou etc. btw, le pire des cas est pour les approches et ... m/2k2kk+1k+cΩ(nm)mm/2k2kk+1k+cΩ(nm) m/2kmm/2k
Aryabhata