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

題目：

統(tǒng)計最優(yōu)比對的數(shù)量（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).

需得：以編輯距離為標(biāo)準(zhǔn)所得的s和t的最優(yōu)比對數(shù)量，結(jié)果對134,217,727 (即227-1)取模

?

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

>Rosalind_78

PLEASANTLY

>Rosalind_33

MEANLY

測試輸出

4

?

生物學(xué)背景

? ? ? ? 在57 使編輯距離最小的序列比對中，我們學(xué)習(xí)了如何在考慮點突變、插入、刪除的情況下得到兩條不等長序列的最優(yōu)比對（optimal alignment）。然而，只找到這么一個最優(yōu)比對，就急著宣布它是真實的進(jìn)化過程是荒謬的，實際情況可以很復(fù)雜，可能有很多情況都達(dá)到最優(yōu)比對的條件，且這些比對間的差異也可能非常大。

? ? ? ??在本題中，我們從簡單的部分做起，只關(guān)心最優(yōu)比對的數(shù)量。

?

思路

? ? ? ??先從讀懂題開始。用所給示例數(shù)據(jù)構(gòu)建動態(tài)規(guī)劃矩陣，如下圖：

[['', 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]]

? ? ? ??用紅色標(biāo)記出回溯路線：

[['', 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]]

? ? ? ??可以看到，在回溯過程中出現(xiàn)了兩次“分叉”，因此產(chǎn)生了4種最優(yōu)比對結(jié)果，即：

PLEASANTLY

M-EA—N-LY

? ? ? ??或

PLEASANTLY

M-E--AN-LY

? ? ? ??或

PLEASANTLY

-MEA—N-LY

? ? ? ??或

PLEASANTLY

-ME--AN-LY

? ? ? ??因此，本題本質(zhì)要計算的是有多少種回溯方式。

? ? ? ??本題結(jié)果代碼來自網(wǎng)絡(luò)（https://github.com/mattdoug604/Rosalind/blob/master/2_bioinformatics_stronghold/rosalind_CTEA.py），在此做簡單分析。

? ? ? ??本題依然要建立動態(tài)規(guī)劃矩陣，按照57 使編輯距離最小的序列比對的思路對矩陣d進(jìn)行填充時。在填充矩陣d的同時，同時填充另一個矩陣counts記錄到達(dá)這個點可以走的“岔路”的數(shù)量。矩陣填充完成后，counts矩陣右下角的值即為所求。具體可參考代碼內(nèi)容，相信明白動態(tài)規(guī)劃的思想后并不難理解。

?

代碼