【ROSALIND】【练Python，学生信】68 有打分矩阵的全局比对

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

题目：

有打分矩阵的全局比对（Global Alignment with Scoring Matrix）

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

所给：两个不超过1000个氨基酸的蛋白质序列，以FASTA格式给出。

Return: The maximum alignment score between s and t. Use:

    The BLOSUM62 scoring matrix.

    Linear gap penalty equal to 5 (i.e., a cost of -5 is assessed for each gap symbol).

需得：两个序列比对的最大得分。限制条件：

    使用BLOSUM62打分矩阵

    空位罚分为5（即，每个空位减去5分）。

测试数据

>Rosalind_67

PLEASANTLY

>Rosalind_17

MEANLY

测试输出

8

背景

        在57 使编辑距离最小的序列比对中我们学到带有空位罚分的序列比对，那时我们将不匹配和空位的罚分都设为1。但在实际中，一种氨基酸向不同氨基酸转变的概率并不相同，我们需要有更复杂的罚分方式来描述这种生物学意义。替换打分矩阵由此而生。

        BLOSUM矩阵是通过对大量符合特定要求的序列计算而来的，BLOSUM62矩阵是由一致度大于62%的序列计算而来的。

思路

        有了之前的动态规划基础，本题并不难写，这里有关动态矩阵规划的代码就来自66 统计最优比对的数量，只稍加改动就可以直接用在本题上。改动的部分就是将打分矩阵融入填充过程，我选择用字典实现。

        本题给的BLOSUM62矩阵如下：

A  C  D  E  F  G  H  I  K  L  M  N  P  Q  R  S  T  V  W  Y

A  4  0 -2 -1 -2  0 -2 -1 -1 -1 -1 -2 -1 -1 -1  1  0  0 -3 -2

C  0  9 -3 -4 -2 -3 -3 -1 -3 -1 -1 -3 -3 -3 -3 -1 -1 -1 -2 -2

D -2 -3  6  2 -3 -1 -1 -3 -1 -4 -3  1 -1  0 -2  0 -1 -3 -4 -3

E -1 -4  2  5 -3 -2  0 -3  1 -3 -2  0 -1  2  0  0 -1 -2 -3 -2

F -2 -2 -3 -3  6 -3 -1  0 -3  0  0 -3 -4 -3 -3 -2 -2 -1  1  3

G  0 -3 -1 -2 -3  6 -2 -4 -2 -4 -3  0 -2 -2 -2  0 -2 -3 -2 -3

H -2 -3 -1  0 -1 -2  8 -3 -1 -3 -2  1 -2  0  0 -1 -2 -3 -2  2

I -1 -1 -3 -3  0 -4 -3  4 -3  2  1 -3 -3 -3 -3 -2 -1  3 -3 -1

K -1 -3 -1  1 -3 -2 -1 -3  5 -2 -1  0 -1  1  2  0 -1 -2 -3 -2

L -1 -1 -4 -3  0 -4 -3  2 -2  4  2 -3 -3 -2 -2 -2 -1  1 -2 -1

M -1 -1 -3 -2  0 -3 -2  1 -1  2  5 -2 -2  0 -1 -1 -1  1 -1 -1

N -2 -3  1  0 -3  0  1 -3  0 -3 -2  6 -2  0  0  1  0 -3 -4 -2

P -1 -3 -1 -1 -4 -2 -2 -3 -1 -3 -2 -2  7 -1 -2 -1 -1 -2 -4 -3

Q -1 -3  0  2 -3 -2  0 -3  1 -2  0  0 -1  5  1  0 -1 -2 -2 -1

R -1 -3 -2  0 -3 -2  0 -3  2 -2 -1  0 -2  1  5 -1 -1 -3 -3 -2

S  1 -1  0  0 -2  0 -1 -2  0 -2 -1  1 -1  0 -1  4  1 -2 -3 -2

T  0 -1 -1 -1 -2 -2 -2 -1 -1 -1 -1  0 -1 -1 -1  1  5  0 -2 -2

V  0 -1 -3 -2 -1 -3 -3  3 -2  1  1 -3 -2 -2 -3 -2  0  4 -3 -1

W -3 -2 -4 -3  1 -2 -2 -3 -3 -2 -1 -4 -4 -2 -3 -3 -2 -3 11  2

Y -2 -2 -3 -2  3 -3  2 -1 -2 -1 -1 -2 -3 -1 -2 -2 -2 -1  2  7

        我将其改成了字典，如下：

{'AA': '4', 'AC': '0', 'AD': '-2', 'AE': '-1', 'AF': '-2', 'AG': '0', 'AH': '-2', 'AI': '-1', 'AK': '-1', 'AL': '-1', 'AM': '-1', 'AN': '-2', 'AP': '-1', 'AQ': '-1', 'AR': '-1', 'AS': '1', 'AT': '0', 'AV': '0', 'AW': '-3', 'AY': '-2', 'CA': '0', 'CC': '9', 'CD': '-3', 'CE': '-4', 'CF': '-2', 'CG': '-3', 'CH': '-3', 'CI': '-1', 'CK': '-3', 'CL': '-1', 'CM': '-1', 'CN': '-3', 'CP': '-3', 'CQ': '-3', 'CR': '-3', 'CS': '-1', 'CT': '-1', 'CV': '-1', 'CW': '-2', 'CY': '-2', 'DA': '-2', 'DC': '-3', 'DD': '6', 'DE': '2', 'DF': '-3', 'DG': '-1', 'DH': '-1', 'DI': '-3', 'DK': '-1', 'DL': '-4', 'DM': '-3', 'DN': '1', 'DP': '-1', 'DQ': '0', 'DR': '-2', 'DS': '0', 'DT': '-1', 'DV': '-3', 'DW': '-4', 'DY': '-3', 'EA': '-1', 'EC': '-4', 'ED': '2', 'EE': '5', 'EF': '-3', 'EG': '-2', 'EH': '0', 'EI': '-3', 'EK': '1', 'EL': '-3', 'EM': '-2', 'EN': '0', 'EP': '-1', 'EQ': '2', 'ER': '0', 'ES': '0', 'ET': '-1', 'EV': '-2', 'EW': '-3', 'EY': '-2', 'FA': '-2', 'FC': '-2', 'FD': '-3', 'FE': '-3', 'FF': '6', 'FG': '-3', 'FH': '-1', 'FI': '0', 'FK': '-3', 'FL': '0', 'FM': '0', 'FN': '-3', 'FP': '-4', 'FQ': '-3', 'FR': '-3', 'FS': '-2', 'FT': '-2', 'FV': '-1', 'FW': '1', 'FY': '3', 'GA': '0', 'GC': '-3', 'GD': '-1', 'GE': '-2', 'GF': '-3', 'GG': '6', 'GH': '-2', 'GI': '-4', 'GK': '-2', 'GL': '-4', 'GM': '-3', 'GN': '0', 'GP': '-2', 'GQ': '-2', 'GR': '-2', 'GS': '0', 'GT': '-2', 'GV': '-3', 'GW': '-2', 'GY': '-3', 'HA': '-2', 'HC': '-3', 'HD': '-1', 'HE': '0', 'HF': '-1', 'HG': '-2', 'HH': '8', 'HI': '-3', 'HK': '-1', 'HL': '-3', 'HM': '-2', 'HN': '1', 'HP': '-2', 'HQ': '0', 'HR': '0', 'HS': '-1', 'HT': '-2', 'HV': '-3', 'HW': '-2', 'HY': '2', 'IA': '-1', 'IC': '-1', 'ID': '-3', 'IE': '-3', 'IF': '0', 'IG': '-4', 'IH': '-3', 'II': '4', 'IK': '-3', 'IL': '2', 'IM': '1', 'IN': '-3', 'IP': '-3', 'IQ': '-3', 'IR': '-3', 'IS': '-2', 'IT': '-1', 'IV': '3', 'IW': '-3', 'IY': '-1', 'KA': '-1', 'KC': '-3', 'KD': '-1', 'KE': '1', 'KF': '-3', 'KG': '-2', 'KH': '-1', 'KI': '-3', 'KK': '5', 'KL': '-2', 'KM': '-1', 'KN': '0', 'KP': '-1', 'KQ': '1', 'KR': '2', 'KS': '0', 'KT': '-1', 'KV': '-2', 'KW': '-3', 'KY': '-2', 'LA': '-1', 'LC': '-1', 'LD': '-4', 'LE': '-3', 'LF': '0', 'LG': '-4', 'LH': '-3', 'LI': '2', 'LK': '-2', 'LL': '4', 'LM': '2', 'LN': '-3', 'LP': '-3', 'LQ': '-2', 'LR': '-2', 'LS': '-2', 'LT': '-1', 'LV': '1', 'LW': '-2', 'LY': '-1', 'MA': '-1', 'MC': '-1', 'MD': '-3', 'ME': '-2', 'MF': '0', 'MG': '-3', 'MH': '-2', 'MI': '1', 'MK': '-1', 'ML': '2', 'MM': '5', 'MN': '-2', 'MP': '-2', 'MQ': '0', 'MR': '-1', 'MS': '-1', 'MT': '-1', 'MV': '1', 'MW': '-1', 'MY': '-1', 'NA': '-2', 'NC': '-3', 'ND': '1', 'NE': '0', 'NF': '-3', 'NG': '0', 'NH': '1', 'NI': '-3', 'NK': '0', 'NL': '-3', 'NM': '-2', 'NN': '6', 'NP': '-2', 'NQ': '0', 'NR': '0', 'NS': '1', 'NT': '0', 'NV': '-3', 'NW': '-4', 'NY': '-2', 'PA': '-1', 'PC': '-3', 'PD': '-1', 'PE': '-1', 'PF': '-4', 'PG': '-2', 'PH': '-2', 'PI': '-3', 'PK': '-1', 'PL': '-3', 'PM': '-2', 'PN': '-2', 'PP': '7', 'PQ': '-1', 'PR': '-2', 'PS': '-1', 'PT': '-1', 'PV': '-2', 'PW': '-4', 'PY': '-3', 'QA': '-1', 'QC': '-3', 'QD': '0', 'QE': '2', 'QF': '-3', 'QG': '-2', 'QH': '0', 'QI': '-3', 'QK': '1', 'QL': '-2', 'QM': '0', 'QN': '0', 'QP': '-1', 'QQ': '5', 'QR': '1', 'QS': '0', 'QT': '-1', 'QV': '-2', 'QW': '-2', 'QY': '-1', 'RA': '-1', 'RC': '-3', 'RD': '-2', 'RE': '0', 'RF': '-3', 'RG': '-2', 'RH': '0', 'RI': '-3', 'RK': '2', 'RL': '-2', 'RM': '-1', 'RN': '0', 'RP': '-2', 'RQ': '1', 'RR': '5', 'RS': '-1', 'RT': '-1', 'RV': '-3', 'RW': '-3', 'RY': '-2', 'SA': '1', 'SC': '-1', 'SD': '0', 'SE': '0', 'SF': '-2', 'SG': '0', 'SH': '-1', 'SI': '-2', 'SK': '0', 'SL': '-2', 'SM': '-1', 'SN': '1', 'SP': '-1', 'SQ': '0', 'SR': '-1', 'SS': '4', 'ST': '1', 'SV': '-2', 'SW': '-3', 'SY': '-2', 'TA': '0', 'TC': '-1', 'TD': '-1', 'TE': '-1', 'TF': '-2', 'TG': '-2', 'TH': '-2', 'TI': '-1', 'TK': '-1', 'TL': '-1', 'TM': '-1', 'TN': '0', 'TP': '-1', 'TQ': '-1', 'TR': '-1', 'TS': '1', 'TT': '5', 'TV': '0', 'TW': '-2', 'TY': '-2', 'VA': '0', 'VC': '-1', 'VD': '-3', 'VE': '-2', 'VF': '-1', 'VG': '-3', 'VH': '-3', 'VI': '3', 'VK': '-2', 'VL': '1', 'VM': '1', 'VN': '-3', 'VP': '-2', 'VQ': '-2', 'VR': '-3', 'VS': '-2', 'VT': '0', 'VV': '4', 'VW': '-3', 'VY': '-1', 'WA': '-3', 'WC': '-2', 'WD': '-4', 'WE': '-3', 'WF': '1', 'WG': '-2', 'WH': '-2', 'WI': '-3', 'WK': '-3', 'WL': '-2', 'WM': '-1', 'WN': '-4', 'WP': '-4', 'WQ': '-2', 'WR': '-3', 'WS': '-3', 'WT': '-2', 'WV': '-3', 'WW': '11', 'WY': '2', 'YA': '-2', 'YC': '-2', 'YD': '-3', 'YE': '-2', 'YF': '3', 'YG': '-3', 'YH': '2', 'YI': '-1', 'YK': '-2', 'YL': '-1', 'YM': '-1', 'YN': '-2', 'YP': '-3', 'YQ': '-1', 'YR': '-2', 'YS': '-2', 'YT': '-2', 'YV': '-1', 'YW': '2', 'YY': '7'}

        这样，在比对时，直接从字典中查出打分结果即可。

代码