Rosalind – Enumerating k-mers Lexicographically

Esse problema é muito simples, dada um alfabeto, uma coleção com um certo número de símbolos e um tamanho, temos que fazer todas as combinações possíveis organizados lexicograficamente, na “ordem alfabética”.

Primeiro, a quantidade de possibilidades será o número de símbolos elevado pelo tamanho da palavra que vamos formar.

O exemplo de dados é:

A C G T 2

Então o alfabeto é o ‘A’, ‘C’, ‘G’ e ‘T’ e o tamanho é 2, ou seja temos 2 posições

_ _

E cada posição tem quatro possibilidades.

A primeira solução que eu pensaria é fazer um loop, usando um for para cada posição, algo como:

1
2
3
4
5
alfabeto=['a','c','g','t']
 
for i in alfabeto:
    for j in alfabeto:
        print i+j

Mas ai temos o problema de como criaríamos for de acordo com o tamanho de entrada, já que ele é variável. Mas podemos criar uma solução recursiva para esse problema.

1
2
3
4
5
6
7
8
def fn_re(n):
 
    if n>1:        
        fn_re(n-1)
 
    print n
 
fn_re(len(alfabeto))
>>>4 3 2 1

Ou seja, enquanto n for maior que o tamanho for maior que zero, a gente faz algo, até a condição de parada, que é n chegar a zero, não ter o que fazer, ai a gente só retorna o processamento. Então o que a gente precisa é mandar o alfabeto, e mandar o tamanho da palavra que vamos formar, ai para cada letra do alfabeto, a gente chama de novo a função.

1
2
3
4
5
6
7
def combina(alfabeto,n,kmer,lista):
    if n==0:
        lista.append(kmer)
    else:
        for letra in alfabeto:
            combina(alfabeto,n-1,kmer+letra,lista)
    return lista

Um jeito legal de entender melhor o que está acontecendo, é imprimir o kmer e a lista, no inicio da função, assim:

1
2
3
4
5
6
7
8
9
def combina(alfabeto,n,kmer,lista):
    print kmer
    print lista
    if n==0:
        lista.append(kmer)
    else:
        for letra in alfabeto:
            combina(alfabeto,n-1,kmer+letra,lista)
    return lista

Ai quando a gente usa ela

1
2
3
alfabeto=['a','c','g','t']
n=2
resposta= combina(alfabeto,n,'',[])

A gente vê o seguinte:

[] a [] aa [] ac ['aa'] ag ['aa', 'ac'] at ['aa', 'ac', 'ag'] c ['aa', 'ac', 'ag', 'at'] ca ['aa', 'ac', 'ag', 'at'] cc ['aa', 'ac', 'ag', 'at', 'ca'] . . .

A primeira chamada, o kmer é ” e a lista ta vazia.
O n é diferente de zero, então a gente continua e então chamamos a função para todo o alfabeto, no primeira chamada recursiva, vamos diminuir um no n, que vai ficar 1 e veja que vamos concatenar no for a uma letra ao kmer, a primeira letra do nosso alfabeto é o a, então na segunda vez que imprimimos na tela, vemos o a, porque fizemos kmer+letra na chamada e temos o n sendo 1, então chamamos recursivo de novo, só que agora, na recursão o kmer é ‘a’, e no for vamos fazer kmer+letra de novo, e chamar recursivo, mas agora temos ‘aa’, agora a gente vai cair dentro do if, e ao invés de fazer a chamada recursiva, a gente so coloca o ‘aa’ na lista, e assim seguimos.

Bem agora é só ler o arquivo, pegar os parâmetros e pimba, o script vai estar la no repositório recologia, e se eu escrevi alguma bobeira, algo errado, deixe um comentário corrigindo ou mande um e-mail.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def combina(alfabeto,n,kmer,lista):
    print kmer
    print lista
    if n==0:
        lista.append(kmer)
    else:
        for letra in alfabeto:
            combina(alfabeto,n-1,kmer+letra,lista)
    return lista
 
"""
file = open( "/mnt/B21AA1BD1AA17ECB/downloads_chromium_ubuntu/rosalind_lexf.txt" )
alfabeto = file.readline().split()
n = int(file.readline())
file.close()
"""
 
###Exemplo
alfabeto=['a','c','g','t']
n=2
 
 
print "Número de possibilidades: "+str(len(alfabeto)**n)
 
resposta= combina(alfabeto,n,'',[])
 
for i in resposta:
    print i

Leave a Reply

Your email address will not be published. Required fields are marked *