L'appariement approximatif de chaînes algorithmes

OK, Needleman-Wunsch(NW) est un classique de bout en bout ("global") aligneur de la littérature bio-informatique. Il était depuis longtemps disponible en tant que "align" et "align0" dans le paquet FASTA. La différence était que la version" 0 " n'était pas aussi biaisée pour éviter les dérapages, ce qui permettait souvent de favoriser des matches internes de grande qualité plus facilement. Smith-Waterman, je pense que vous êtes au courant, est un aligneur local et est la base originale de L'explosion. FASTA avait son propre aligneur local ainsi que qui était légèrement différente. Toutes ces méthodes sont essentiellement heuristiques pour estimer la distance Levenshtein pertinente à une métrique de notation pour des 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 plus raisonnablement reflétant des remplacements dans la morphologie des mots linguistiques lorsqu'elle est appliquée à la langue naturelle).

ne nous faisons pas d'illusions sur les étiquettes: Levenshtein distance, comme référencé dans la pratique au moins, est essentiellement éditer la distance et vous devez l'estimer parce qu'il n'est pas possible de le calculer généralement, et il est coûteux de calculer exactement, même dans des cas spéciaux intéressants: l'eau devient profonde rapide là, et donc nous avons 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, j'ai dû vérifier l'exactitude de l'ADN Court lit contre séquence de référence connue pour être correcte et j'ai trouvé avec quelque chose que j'ai appelé "ancré alignements".

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 chaîne de caractères N donnée se produit. Choisissez N pour que la table que vous construisez ne soit pas trop grande mais aussi pour que les substrats de longueur N ne soient pas trop communs. Pour les petits alphabets comme les bases D'ADN, il est possible de trouver un hachage parfait sur les chaînes de n caractères et faire une table et enchaîner les matches dans une liste liée à partir de chaque bin. Le les entrées de liste doivent identifier la séquence et la position de départ de la sous-chaîne qui correspond à la bin dans la liste de 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 à un certain offset K dans la chaîne de requête, les hachez, cherchez leur bin, et si la liste pour cette bin est non empty alors vous allez à travers tous les enregistrements de liste et effectuer des alignements entre la chaîne de requête et la chaîne de recherche référencée dans l'enregistrement. En faisant ces alignements, vous alignez la chaîne de requête et la chaîne de recherche à l'ancre et extraire un substrat de la chaîne de recherche qui est la même longueur que la chaîne de requête et qui contient que l'ancre au même décalage, K.

si vous choisissez une longueur d'ancrage N suffisamment longue, et un ensemble raisonnable de valeurs d'offset K (elles peuvent être étendues à travers la chaîne de requête OU être limité aux faibles compensations) vous devriez obtenir un sous-ensemble d'alignements possibles et obtiendrez souvent des gagnants plus clairs. Typiquement, vous voudrez utiliser le moins d'align0-comme l'aligneur NW.

cette méthode essaie de boost NW un peu en limitant son entrée et cela a un gain de performance parce que 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 de le gapping permet de réduire les coûts, surtout si vous savez que vous n'allez pas voir OU être intéressé par des matches de qualité moyenne.

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

dans les deux cas, permettre l'utilisation simultanée de plus d'une ancre 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 à éventuellement envoyer des chaînes se chevauchant chacune contenant un des deux ancrages à l'aligneur et puis réconcilier les alignements... ou éventuellement modifier NW pour mettre l'accent sur le maintien de vos ancrages presque intacts lors d'un alignement en utilisant la modification de pénalité lors de l'exécution de l'algorithme.

j'Espère que cela est utile ou au moins intéressant.