Как сгенерировать все возможные шаблоны из набора букв?

Question

Как я могу упростить циклы for в этой функции, используя аргумент k?

def PatternGenerate(k):
    base = ['A','C','G','T']
    pattern = []
    for x in base:
        for y in base:
            for z in base:
                result = str(x) + str(y) + str(z)
                pattern.append(result)
    return pattern

У меня есть нужный результат, но нет функции:

['AAA', 'AAC', 'AAG', 'AAT', 'ACA ',' ACC ',' ACG ',' ACT ',' AGA ',' AGC ',' AGG ',' AGT ',' ATA ',' ATC ',' ATG ',' ATT ',' CAA ', «CAC», «CAG», «CAT», «CCA», «CCC», «CCG», «CCT», «CGA», «CGC», «CGG», «CGT», «CTA», «CTC ',' CTG ',' CTT ',' GAA ',' GAC ',' GAG ',' GAT ',' GCA ',' GCC ',' GCG ',' GCT ',' GGA ',' GGC ', 'GGG', 'GGT', 'GTA', 'GTC', 'GTG', 'GTT', 'TAA', 'TAC', 'TAG', 'TAT', 'TCA', 'TCC', 'TCG ',' TCT ',' TGA ',' TGC ',' TGG ',' TGT ',' TTA ',' TTC ',' TTG ',' TTT ']

Answer 1

Вот способ сделать это, используя repeat и product из itertools:

from itertools import product, repeat

# This one returns a list, like your version:
def list_all_kmers(k):
    return ["".join(nucls) for nucls in product(*repeat("ACGT", k))]

# This one generates k-mers one by one:
def generate_all_kmers(k):
    # It seems "return" also works
    # I'm not sure it makes a difference here
    # but see https://stackoverflow.com/a/45620965/1878788
    yield from ("".join(nucls) for nucls in product(*repeat("ACGT", k)))

for kmer in generate_all_kmers(3):
    print(kmer)

Результат:

AAA
AAC
AAG
AAT
ACA
ACC
ACG
ACT
AGA
AGC
AGG
AGT
ATA
ATC
ATG
ATT
CAA
CAC
CAG
CAT
CCA
CCC
CCG
CCT
CGA
CGC
CGG
CGT
CTA
CTC
CTG
CTT
GAA
GAC
GAG
GAT
GCA
GCC
GCG
GCT
GGA
GGC
GGG
GGT
GTA
GTC
GTG
GTT
TAA
TAC
TAG
TAT
TCA
TCC
TCG
TCT
TGA
TGC
TGG
TGT
TTA
TTC
TTG
TTT

Некоторые пояснения:

repeat("ACGT", k) генерирует k раз "ACGT".Это можно представить при создании списка из него:

list(repeat("ACGT", 3))

Результат:

['ACGT', 'ACGT', 'ACGT']

product(l1, l2, l3) генерирует все кортежи, имеющие первый элемент из l1, второй из l2 и третий из l3, где l1, l2 и l3 являются «итерациями», например списками или строками.Это работает с любым числом или итерациями:

Ноль:

list(product())

Результат:

[()]

Один:

list(product("ACGT"))

Результат:

[('A',), ('C',), ('G',), ('T',)]

Два:

list(product("ACGT", "ACGT"))

Результат:

[('A', 'A'),
 ('A', 'C'),
 ('A', 'G'),
 ('A', 'T'),
 ('C', 'A'),
 ('C', 'C'),
 ('C', 'G'),
 ('C', 'T'),
 ('G', 'A'),
 ('G', 'C'),
 ('G', 'G'),
 ('G', 'T'),
 ('T', 'A'),
 ('T', 'C'),
 ('T', 'G'),
 ('T', 'T')]

И т.д.

Однако, если мы хотим использовать результат repeat, мы должны использовать *, чтобы сказать, что сгенерированные элементы должны быть приняты в качестве отдельных аргументов.В вызове функции f(*[l1, l2, l3]) это все равно что делать f(l1, l2, l3).Это работает также, если вы используете генератор вместо списка, поэтому нам не нужно делать list(repeat(...)) (мы только что сделали это выше для визуализации).

Затем мы хотим сделать строки изэлементы в кортежах.Это достигается благодаря методу join пустой строки, который мы используем в «понимании списка» (между []) или в «выражении генератора» (между ()).

Понимание списка создает полный список, а выражения генератора генерируют элементы один за другим «по требованию».

Answer 2

Будет намного проще, если вы используете рекурсивную форму.

def PatternGenerate(k):
    base = ['A','C','G','T']
    pattern = []
    if k == 1:
      return base
    else:
      for p in PatternGenerate(k-1):
        for b in base:
          pattern.append(p+b)

      return pattern

Объясните Идея такова: если k == 1, просто вернуть базу, если k> 1, найтиPatternGenerate (k-1) и добавьте его с основанием.

Answer 3

Более поздняя версия с использованием itertools

import itertools
k = 2
result = ["".join(t) for t in itertools.combinations_with_replacement(['A','C','G','T'], k)]
print(result)

Реализация внутри combinations_with_replacement очень похожа на реализацию @ Andriy.

Answer 4

Один из способов сделать это с помощью рекурсии.Вот пример функции генератора для этого:

def genAll(depth, base = ['A','C','G','T']):
    if depth <= 0:
        yield ''
    else:
        for char in base:
            for tail in genAll(depth - 1, base):
                yield char + tail

for comb in genAll(2):
    print(comb)

Вывод:

AA
AC
AG
AT
CA
CC
CG
CT
GA
GC
GG
GT
TA
TC
TG
TT