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

題目：

按字母順序排列的K-mer結(jié)果

Given: A collection of at most 10 symbols defining an ordered alphabet, and a positive integer n (n<10).

所給：不超過(guò)10個(gè)字符和一個(gè)正整數(shù)n（n<10）。

Return: All strings of length n that can be formed from the alphabet, ordered lexicographically (use the standard order of symbols in the English alphabet).

需得：這些字符組成的所有包含n個(gè)字符的字符串，以英文字母順序輸出。

?

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

A C G T

2

測(cè)試輸出

AA

AC

AG

AT

CA

CC

CG

CT

GA

GC

GG

GT

TA

TC

TG

TT

?

背景

k-mer是指將reads分成包含k個(gè)堿基的字符串，一般長(zhǎng)短為m的reads可以分成m-k+1個(gè)k-mers。k-mer用于測(cè)序后序列拼接的過(guò)程。

?

思路

本題需要解決的關(guān)鍵問題是如何枚舉出長(zhǎng)度為k的字符串。我這里依然用了遞歸的思路。首先將所給字典中的字符按順序兩兩組合，形成包含長(zhǎng)度為2的字符的列表，隨后再按相同方法把該列表與原字典中的字符組合，形成3-mer的列表，以此類推，直到得到長(zhǎng)度為k的字符。

?

代碼

def perm(dic, subdic, k):

"""
:param dic: 題目給出的原字符字典
:param subdic: 組合后的字符字典
:param k: 最后需要的字符長(zhǎng)度
:return: 按字典順序排列的k-mer
"""

??? i = 0

??? ls = []

??? while i < len(dic):

??????? j = 0

??????? while j < len(subdic):

??????????? ls.append(dic[i] + subdic[j])? # 將字符按順序組合

??????????? j += 1

??????? i += 1

??? i = 2

??? while i < k:

??????? i += 1

??????? ls = perm(dic, ls, k-1)

??????? break

?

??? return ls

?

f = open('rosalind_lexf.txt', 'r')

lines = f.readlines()

f.close()

dic = lines[0].replace('\n','').replace(' ','')

k = int(lines[1])

?

i = 0

mydic = []

while i < len(dic):

??? mydic.append(dic[i])? # 將讀入的字符串該存為列表

??? i += 1

dic = mydic

?

result = []

result = perm(dic, dic, k)? # 起始先輸入兩個(gè)原始字典

?

i = 0

f = open('output.txt', 'a')

while i < len(result):

??? f.write(result[i] + '\n')

??? print(result[i])

??? i += 1

?

f.close()