Algorithmes de correspondance de chaîne approximatifs

OK, Needleman-Wunsch (NW) est un aligneur classique de bout en bout («global») de la littérature bioinformatique. Il y a longtemps, il était disponible en tant que “align” et “align0” dans le package FASTA. La différence était que la version “0” n’était pas aussi biaisée en ce qui concernait le fait d’éviter les échappatoires, ce qui permettait souvent de favoriser des matchs internes de haute qualité. Smith-Waterman, je suppose que vous êtes au courant, est un aligneur local et est la base originale de BLAST. FASTA avait son propre aligneur local qui était légèrement différent. Toutes ces méthodes sont essentiellement heuristiques pour estimer la distance de Levenshtein associée à une mésortingque de notation pour des paires de caractères individuelles (en bioinformatique, souvent donnée par Dayhoff / “PAM”, Henikoff & Henikoff ou d’autres masortingces). en morphologie des mots linguistiques lorsqu’il est appliqué au langage naturel).

Ne soyons pas précieux sur les étiquettes: la distance de Levenshtein, telle que référencée dans la pratique, est essentiellement une distance de assembly et il faut l’estimer car il est impossible de la calculer généralement, même dans des cas particuliers intéressants: y va vite, et nous avons donc des méthodes heuristiques de longue et bonne réputation.

Maintenant, en ce qui concerne votre propre problème: il y a plusieurs années, je devais vérifier l’exactitude des lectures d’ADN courtes par rapport à la 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 ensemble de chaînes de référence et de le “digérer” en trouvant tous les emplacements où se produit une sous-chaîne de N-caractères. 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 communes. Pour les petits alphabets comme les bases ADN, il est possible de créer un hachage parfait sur les chaînes de N caractères, de créer un tableau et de chaîner les correspondances dans une liste chaînée à partir de chaque corbeille. Les entrées de la liste doivent identifier la séquence et la position de départ de la sous-chaîne qui correspond à la corbeille dans laquelle elles apparaissent. Ce sont des “ancres” dans la liste des chaînes à rechercher auxquelles 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 par un certain décalage K dans la chaîne de requête, les hachez, recherchez leur corbeille et si la liste de cette corbeille est vide, parcourez tous les enregistrements de liste la chaîne de requête et la chaîne de recherche référencée dans l’enregistrement. Lorsque vous effectuez 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 suffisamment longue N 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 à des décalages bas), vous devriez obtenir un sous-ensemble d’alignements possibles. En règle générale, vous souhaiterez utiliser l’aligneur NW de type align0 moins polarisé en fin d’extrémité.

Cette méthode essaie de booster 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é d’espacement 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é médiocre.

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). de l’ordre de 10000, je cherchais donc des correspondances de sous-chaînes approximatives justifiées par une estimation de la distance de assembly en particulier). L’adaptation de cette méthodologie au langage naturel nécessite une reflection approfondie: vous perdez la taille de l’alphabet mais vous gagnez si vos chaînes de requête et de recherche ont une longueur similaire.

Quoi qu’il en soit, permettre à plus d’une ancre de différentes extrémités de la chaîne de requête d’être utilisée simultanément pourrait être utile pour filtrer les données envoyées à NW. Si vous faites cela, soyez prêt à envoyer éventuellement des chaînes qui se chevauchent, chacune contenant une des deux ancres à l’aligneur, puis à concilier les alignements … ou à modifier éventuellement NW pour que vos ancres restnt intactes lors d’un alignement utilisant une modification de pénalité lors de l’alignement. l’exécution de l’algorithme.

J’espère que c’est utile ou du moins intéressant.

Relatif à la distance de Levenstein: vous pourriez vouloir le normaliser en divisant le résultat par la longueur de la chaîne la plus longue, de sorte que vous obtenez toujours un nombre compris entre 0 et 1 et que vous puissiez comparer la distance d’une paire de chaînes way (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 les algorithmes de concordance de séquences biologiques AgreP ( entrée Wikipedia sur conventions ), FASTA et BLAST . Il s’agit de cas particuliers d’ appariement de chaînes approché , également dans le référentiel d’algorithmes Stony Brook . Si vous pouvez spécifier les différences entre les chaînes, vous pouvez probablement vous concentrer sur un algorithme personnalisé. Par exemple, aspell utilise une variante de la distance “soundlike” (soundex-metaphone) en combinaison avec une distance “clavier” pour accommoder les mauvais spellers et les mauvais typers.

Nous utilisons la méthode de distance Levenshtein pour vérifier les clients en double dans notre firebase database. Cela fonctionne assez bien.

Utilisez l’ index FM avec Backtracking, similaire à celui de l’ alignement flou Bowtie

Afin de minimiser les erreurs dues aux légères variations ou erreurs d’orthographe, j’ai utilisé l’algorithme Metaphone, puis la distance Levenshtein (mise à l’échelle 0-100 en pourcentage) sur les encodages Metaphone pour une mesure de la proximité. Cela semble avoir plutôt 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 les alignements de différentes longueurs.

Compte tenu de ce qui vous intéresse, vous pouvez obtenir des valeurs p pour votre alignement. Si vous utilisez Needleman-Wunsch, vous pouvez obtenir ces valeurs p en utilisant les statistiques de Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

BLAST peut aligner localement et les évaluer en utilisant 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 cachés pour aligner les séquences. Personnellement, je pense que cette approche est plus puissante car elle fournit également des informations de position. http://hmmer.janelia.org/