【ROSALIND】【练Python，学生信】23 按字母顺序排列的K-mer

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

题目：

按字母顺序排列的K-mer结果

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

所给：不超过10个字符和一个正整数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个字符的字符串，以英文字母顺序输出。

 

测试数据

A C G T

2

测试输出

AA

AC

AG

AT

CA

CC

CG

CT

GA

GC

GG

GT

TA

TC

TG

TT

 

背景

k-mer是指将reads分成包含k个碱基的字符串，一般长短为m的reads可以分成m-k+1个k-mers。k-mer用于测序后序列拼接的过程。

 

思路

本题需要解决的关键问题是如何枚举出长度为k的字符串。我这里依然用了递归的思路。首先将所给字典中的字符按顺序两两组合，形成包含长度为2的字符的列表，随后再按相同方法把该列表与原字典中的字符组合，形成3-mer的列表，以此类推，直到得到长度为k的字符。

 

代码

def perm(dic, subdic, k):

"""
:param dic: 题目给出的原字符字典
:param subdic: 组合后的字符字典
:param k: 最后需要的字符长度
: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)  # 起始先输入两个原始字典

 

i = 0

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

while i < len(result):

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

    print(result[i])

    i += 1

 

f.close()