Comment calculer l'alignement de séquence multiple pour les chaînes de texte
j'écris un programme qui doit calculer un alignement de séquence multiple d'un ensemble de chaînes de caractères. Je pensais faire ça en Python, mais je pourrais utiliser un logiciel externe ou un autre langage si c'est plus pratique. Les données ne sont pas particulièrement importantes, Je n'ai pas d'exigences de performance élevées et je peux tolérer des approximations (i.e. J'ai juste besoin de trouver un assez bon alignement). Le seul problème, c'est que les chaînes sont régulièrement cordes (ie. Des chaînes UTF-8 potentiellement avec des lignées qui devraient être traitées comme un caractère régulier); ce ne sont pas des séquences D'ADN ou des séquences de protéines.
je peux trouver des tonnes d'outils et d'informations pour les cas habituels en bioinformatique avec des formats de fichiers compliqués spécifiques et une foule de fonctionnalités dont je n'ai pas besoin, mais il est étonnamment difficile de trouver des logiciels, des bibliothèques ou du code d'exemple pour le cas simple des chaînes. Je pourrais probablement réimplémenter tout l'un des nombreux algorithmes pour résoudre ce problème ou encoder ma chaîne L'ADN, mais il doit y avoir un meilleur moyen. Connaissez-vous des solutions?
Merci!
4 réponses
- la façon La plus simple pour aligner plusieurs séquences est de faire un certain nombre d'alignements.
d'abord obtenir des scores de similarité par paire pour chaque paire et stocker ces scores. C'est la partie la plus coûteuse du processus. Choisissez la paire qui a le meilleur score de similarité et faites cet alignement. Choisissez maintenant la séquence qui correspondaient le mieux à l'une des séquences de la série de séquences alignées, et d'aligner l'ensemble cohérent sur la base de paires d'alignement. Répétez jusqu'à ce que toutes les séquences soient entrées.
quand vous alignez une séquence sur les séquences alignées, (d'après une l'alignement par paires), lorsque vous insérez un l'écart dans la séquence qui est déjà en l'ensemble, vous insérez des lacunes dans le même place dans toutes les séquences de l'alignement définir.
Lafrasu a suggéré l'algorithme SequneceMatcher () à utiliser pour l'alignement par paires des chaînes UTF-8. Ce que j'ai décrit vous donne une assez indolore, raisonnablement manière décente de prolonger de plusieurs séquences.
dans le cas où vous êtes intéressé, c'est l'équivalent de construire de petits ensembles de séquences alignées et de les aligner sur leur meilleure paire. Il donne exactement le même résultat, mais il s'agit d'une mise en œuvre plus simple.
vous cherchez quelque chose de rapide et sale, comme dans le suivant?
from difflib import SequenceMatcher
a = "dsa jld lal"
b = "dsajld kll"
c = "dsc jle kal"
d = "dsd jlekal"
ss = [a,b,c,d]
s = SequenceMatcher()
for i in range(len(ss)):
x = ss[i]
s.set_seq1(x)
for j in range(i+1,len(ss)):
y = ss[j]
s.set_seq2(y)
print
print s.ratio()
print s.get_matching_blocks()
j'ai récemment écrit un script python qui exécute L'algorithme de Smith-Waterman (qui est ce qui est utilisé pour générer des alignements de séquence locale gapped pour des séquences D'ADN ou de protéines). Ce n'est certainement pas l'implémentation la plus rapide, car je ne l'ai pas optimisé pour la vitesse du tout (pas mon goulot d'étranglement pour le moment), mais cela fonctionne et ne se soucie pas de l'identité de chaque personnage dans les chaînes. Je pourrais le poster ici ou vous envoyer les fichiers si c'est le genre de chose que vous cherchez pour.
MAFFT la version 7.120 + supporte l'alignement de texte multiple. L'entrée est de la forme format FASTA mais avec le texte LATIN1 au lieu des séquences et la sortie est alignée format FASTA. Une fois installé, il est facile à exécuter:
mafft --text input_text.fa > output_alignment.fa
bien que le MAFFT soit un outil mature pour l'alignement des séquences biologiques, le mode d'alignement du texte en est au stade de développement, avec des plans futurs incluant l'autorisation de matrices de notation définies par l'utilisateur. Vous pouvez voir plus de détails la documentation.