Bioinformática com Rosalind

Marcos CastroPUG Beach

Python User Group (PUG-PI)

Bioinformática...

• Biólogos e programadores lendo a palavra “bioinformática” em Python:

Sequências

Validando sequências DNA/RNA

Testando...

• Rosalind é uma plataforma para o aprendizado de bioinformática através da resolução de problemas.

http://rosalind.info

Lista de problemas

Árvore de problemas

Sugerir problemas

Ranking

Submissão de código

• No final da página de cada problema você encontrará:

Submissão de código

Se acertar o problema...

Counting DNA Nucleotides• http://rosalind.info/problems/dna/

Transcribing DNA into RNA• http://rosalind.info/problems/rna/

Complementing a Strand of DNA

• Inverte a string• ‘A’ e ‘T’ são complementares um do outro

assim como ‘C’ e ‘G’.• Entrada: AAAACCCGGT– String invertida: TGGCCCAAAA

• Saída: ACCGGGTTTT

Complementing a Strand of DNA• http://rosalind.info/problems/revc/

• “s” representa uma string• “l” representa uma lista• “d” representa um dicionário

Counting Point Mutations

• Problema da classe de alinhamento.• Serão dadas duas strings de tamanhos iguais.• A Hamming distance entre duas strings “s” e

“t” é o número de símbolos correspondentes que são diferentes em “s” e “t”.

Counting Point Mutations

• Exemplo:

• Resposta: 7

Counting Point Mutations• http://rosalind.info/problems/hamm/

Translating RNA into Protein

• Nesse problema é dada como entrada uma string RNA “s” correspondente a uma fita de mRNA.

• A saída é uma string proteína codificada a partir de “s”.

Translating RNA into Protein

• Para resolver esse problema, o Rosalind fornece uma tabela de códons para mapear cada aminoácido.

Translating RNA into Protein

Translating RNA into Protein

• Resumindo: cada conjunto de 3 letras da string RNA corresponde a um aminoácido.

• Exemplo:• string RNA: AUGGCC• “AUG” corresponde a “M” na tabela.• “GCC” corresponde a “A” na tabela.

Translating RNA into Protein • http://rosalind.info/problems/prot/

Finding a Motif in DNA • http://rosalind.info/problems/subs/

• Nesse problema são dadas como entrada duas strings “s” e “t”.

• A saída são todas as posições em que “t” ocorre em “s”.

Finding a Motif in DNA

• Exemplo de entrada:s = GATATATGCATATACTT

t = ATAT

• Saída: 2 4 10

Finding a Motif in DNA

Enumerating Gene Orders

• Problema da classe “Rearranjos de Genoma”.• Uma permutação de tamanho “n” é um

ordenamento dos inteiros positivos:– {1, 2, ..., n}

• A entrada é um inteiro n <= 7.• A saída é composta pelo número de

permutações seguido de uma lista de todas as permutações.

Enumerating Gene Orders

• Exemplo de saída para n = 3:61 2 31 3 22 1 32 3 13 1 23 2 1

Enumerating Gene Orders• http://rosalind.info/problems/perm/

• Construindo o código aos poucos...

• l = [1, 2, 3]

Enumerating Gene Orders

• p = [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Enumerating Gene Orders

print(new_l) exibirá: (1, 2, 3) (1, 3, 2)

(2, 1, 3) e assim por diante...

Enumerating Gene Orders

• A linha 10 exibe a quantidade de permutações.

Enumerating Gene Orders

• Código final:

Enumerating Gene Orders

• Execução:

Finding a Shared Motif

• http://rosalind.info/problems/lcsm/

• Problema interessante onde o Rosalind fornece várias strings (cadeias de DNA) como entrada e quer como saída a maior substring comum a todas as strings fornecidas.

Finding a Shared Motif

• Em um primeiro momento você poderá pensar em gerar todas as substrings possíveis de apenas uma das strings, armazenar elas numa lista e percorrer o restante das strings para saber qual é a substring comum e de maior tamanho.

• itertools.combinations() faz isso...

Finding a Shared Motif

• Como gerar todas as substrigs de uma string?• Para a string “ABCD”:• “A”, “B”, “C”, “D”, “AB”, “AC”, “AD”, “BC”, “BD”,

“CD”, “ABC”, “ABD”, “ACD”, “BCD”, “ABCD”.• Fácil não é mesmo ?

Finding a Shared Motif

• Para uma string de tamanho 4, serão geradas 15 substrings.

• Para uma string de tamanho 10, serão geradas 1023 substrings.

• Para uma string de tamanho 20 são geradas 1.048.575 substrings.

• E para uma string do caso de teste do Rosalind? Obs.: strings de tamanho 1000

Ops...

Finding a Shared Motif

• A exceção aconteceu porque eu tentei armazenar um número muito grande de elementos numa lista. Qual a solução?

a) Otimizar meu código b) Comprar mais memória RAM c) Mudar o algoritmo d) Implementar em Java (Haha)

Finding a Shared Motif

• Solução trivial para o problema seria não guardar as substrings.

• A cada substring gerada você verifica nas outras strings. Isso resolve.

• Alguns casos de testes foram testados, o programa levou entre 5 a 8 segundos.

• Será que podemos melhorar isso?

Finding a Shared Motif

• Uma possível otimização é não fazer verificação de uma determinada substring caso ela tenha tamanho menor do que a maior substring guardada até o momento.

• Para um determinado caso de teste, essa otimização diminuiu o tempo de 6.2 segundos para 3.7 segundos.

Arquivos FASTA

• Formato FASTA é um arquivo baseado em texto para representar sequências genéticas onde os nucleotídeos ou aminoácidos são representados usando códigos de uma única letra.

• Linhas do arquivo que começam com “>” ou “;” representam comentários (descrição da sequência).

Arquivos FASTA

NCBI

• NCBI: National Center of Biotechnology Information

• http://www.ncbi.nlm.nih.gov/

• NCBI dentre outras funções, armazena dados da sequenciação de genomas.

NCBI

NCBI

BLAST

• Basic Local Alignment Search Tool

• É a ferramenta de alinhamento mais utilizada atualmente.

• Alinha uma sequência de entrada contra uma base de dados desejada.

BLAST

• Mais informações:– http://pt.slideshare.net/marlluslustosa/slides-blas

t

K-mers

• Composição k-mer é uma coleção de todas as substrings k-mer de texto.

• Composição k-mer para TATGGGGTGC com k=3:

• {TAT, ATG, TGG, GGG, GGG, GGT, GTG, TGC}

Grafos De Bruijn

• Reconstrução de strings• Como era feito: procura-se um caminho no

grafo que visita cada nó somente uma vez (caminho hamiltoniano).

• Problema: mais de um caminho encontrado.• Novo grafo desenvolvido: Grafo de Bruijn• O Grafo de Bruijn representa melhor uma

composição k-mer.

Grafos De Bruijn

• O foco agora é nas arestas.

• Caminhos eulerianos: passa por uma aresta somente uma vez.

Construção do Grafo De Bruijn

• Exemplo de sequência: TAATG com k = 3• Composição k-mer:– {TAA, AAT, ATG}

• {TAA, AAT, ATG} são as arestas do grafo.• Os nós são formados por prefixos e sufixos de

cada mer.• Prefixo de TAA: TA• Sufixo de TAA: AA

Construção do Grafo De Bruijn

• Continuação... {TAA, AAT, ATG}

TAA AAT ATGTA ATAA TG

Desafio

• String Reconstruction from Read-Pairs Problem– http://rosalind.info/problems/4i/ – Grafos De Bruijn– Caminhos eulerianos– Reconstrução de genomas

Sugestões de estudo

• https://www.youtube.com/pycursos – Playlist Python para Bioinformatas

• Livro:

Fim

marcoscastro.mewww.facebook.com/groups/pugpi/

Obrigado!