Alignement de séquence avec pénalité arbitraire de gap

Question

Je veux aligner deux séquences d'ADN de manière optimale, mais j'ai la fonction de pénalité de gap de longueur L, que si L est un multiple de 3, la pénalité est un * L pour une constante une. Si L n'est pas un multiple de 3, alors la pénalité est b * L pour une constante b.

Je suis supposé concevoir un algorithme O (n * m), où n et m sont des longueurs de séquences d'ADN, qui trouvent l'alignement optimal. Mais la partie délicate à ce sujet est que je dois garder une trace de la taille de l'écart qu'il étend. Par exemple, si j'ai deux lacunes contiguës et que je prolonge un intervalle, je devrais mettre à jour le score par L - b (L-1), mais je n'ai pas pu formuler correctement les sous-problèmes. J'ai pensé à introduire un nouveau paramètre L pour "deviner" la longueur de l'écart final, mais cela dépasserait facilement O (n * m). Y a-t-il un moyen de formuler ces sous-problèmes efficacement?

Toute observation clé serait grandement appréciée.

Answer 1

Pouvez-vous clarifier ce que vous entendez par espaces contigus? Si je vous comprends bien, un exemple d'alignement de votre scénario ressemblerait à ceci: AAATTTGGGAA ---- CCCGG AAATTTCGGAA ----- GCGG Cependant, y compris les écarts correspondants sur les deux brins ne fait rien. L'alignement ci-dessus est identique à celui-ci: AAATTTGGGAACCCGG AAATTTCGGAA-GCGG Une pénalité d'écart ne devrait être pertinente que pour un seul brin à un moment donné. Pour évaluer comment la modification des paramètres d'alignement influe sur la sortie d'alignement, je suggère de regarder le module biopython Pairwise2 (qui peut inclure une pénalité d'écart/pénalité d'extension de l'écart). http://biopython.org/DIST/docs/api/Bio.pairwise2-module.html