如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫(xiě)在前面 ?謝謝配合~

題目：

有打分矩陣的全局比對(duì)（Global Alignment with Scoring Matrix）

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

所給：兩個(gè)不超過(guò)1000個(gè)氨基酸的蛋白質(zhì)序列，以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).

需得：兩個(gè)序列比對(duì)的最大得分。限制條件：

????使用BLOSUM62打分矩陣

????空位罰分為5（即，每個(gè)空位減去5分）。

?

測(cè)試數(shù)據(jù)

>Rosalind_67

PLEASANTLY

>Rosalind_17

MEANLY

測(cè)試輸出

8

?

背景

? ? ? ? 在57 使編輯距離最小的序列比對(duì)中我們學(xué)到帶有空位罰分的序列比對(duì)，那時(shí)我們將不匹配和空位的罰分都設(shè)為1。但在實(shí)際中，一種氨基酸向不同氨基酸轉(zhuǎn)變的概率并不相同，我們需要有更復(fù)雜的罰分方式來(lái)描述這種生物學(xué)意義。替換打分矩陣由此而生。

? ? ? ??BLOSUM矩陣是通過(guò)對(duì)大量符合特定要求的序列計(jì)算而來(lái)的，BLOSUM62矩陣是由一致度大于62%的序列計(jì)算而來(lái)的。

?

思路

? ? ? ??有了之前的動(dòng)態(tài)規(guī)劃基礎(chǔ)，本題并不難寫(xiě)，這里有關(guān)動(dòng)態(tài)矩陣規(guī)劃的代碼就來(lái)自66 統(tǒng)計(jì)最優(yōu)比對(duì)的數(shù)量，只稍加改動(dòng)就可以直接用在本題上。改動(dòng)的部分就是將打分矩陣融入填充過(guò)程，我選擇用字典實(shí)現(xiàn)。

? ? ? ??本題給的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'}

? ? ? ??這樣，在比對(duì)時(shí)，直接從字典中查出打分結(jié)果即可。

?

代碼