【ROSALIND】【练Python，学生信】66 统计最优比对的数量

2022-09-13 21:54 作者:未琢 0人读过 | 我要投稿

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面谢谢配合~

题目：

统计最优比对的数量（Counting Optimal Alignments）

Given: Two protein strings s and t in FASTA format, each of length at most 1000 aa.

所给：两条以FASTA格式给出的蛋白序列s和t，长度不超过1000个氨基酸。

Return: The total number of optimal alignments of s and t with respect to edit alignment score, modulo 134,217,727 (2^27-1).

需得：以编辑距离为标准所得的s和t的最优比对数量，结果对134,217,727 (即227-1)取模

测试数据

>Rosalind_78

PLEASANTLY

>Rosalind_33

MEANLY

测试输出

生物学背景

在57 使编辑距离最小的序列比对中，我们学习了如何在考虑点突变、插入、删除的情况下得到两条不等长序列的最优比对（optimal alignment）。然而，只找到这么一个最优比对，就急着宣布它是真实的进化过程是荒谬的，实际情况可以很复杂，可能有很多情况都达到最优比对的条件，且这些比对间的差异也可能非常大。

在本题中，我们从简单的部分做起，只关心最优比对的数量。

思路

先从读懂题开始。用所给示例数据构建动态规划矩阵，如下图：

[['', 0], ['-', 0], ['M', 0], ['E', 0], ['A', 0], ['N', 0], ['L', 0], ['Y', 0]]

[['-', 0], ['', 0], ['←', 1], ['←', 2], ['←', 3], ['←', 4], ['←', 5], ['←', 6]]

[['P', 0], ['↑', 1], ['↖', 1], ['↖←', 2], ['↖←', 3], ['↖←', 4], ['↖←', 5], ['↖←', 6]]

[['L', 0], ['↑', 2], ['↖↑', 2], ['↖', 2], ['↖←', 3], ['↖←', 4], ['↖', 4], ['←', 5]]

[['E', 0], ['↑', 3], ['↖↑', 3], ['↖', 2], ['↖←', 3], ['↖←', 4], ['↖←↑', 5], ['↖', 5]]

[['A', 0], ['↑', 4], ['↖↑', 4], ['↑', 3], ['↖', 2], ['←', 3], ['←', 4], ['←', 5]]

[['S', 0], ['↑', 5], ['↖↑', 5], ['↑', 4], ['↑', 3], ['↖', 3], ['↖←', 4], ['↖←', 5]]

[['A', 0], ['↑', 6], ['↖↑', 6], ['↑', 5], ['↖↑', 4], ['↖↑', 4], ['↖', 4], ['↖←', 5]]

[['N', 0], ['↑', 7], ['↖↑', 7], ['↑', 6], ['↑', 5], ['↖', 4], ['↖←↑', 5], ['↖', 5]]

[['T', 0], ['↑', 8], ['↖↑', 8], ['↑', 7], ['↑', 6], ['↑', 5], ['↖', 5], ['↖←↑', 6]]

[['L', 0], ['↑', 9], ['↖↑', 9], ['↑', 8], ['↑', 7], ['↑', 6], ['↖', 5], ['↖←', 6]]

[['Y', 0], ['↑', 10], ['↖↑', 10], ['↑', 9], ['↑', 8], ['↑', 7], ['↑', 6], ['↖', 5]]

用红色标记出回溯路线：