View
2.108
Download
0
Category
Preview:
DESCRIPTION
Essa apresentação contempla a resolução de problemas de bioinformática utilizando a plataforma Rosalind e a linguagem de programação Python.
Citation preview
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...
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
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!
Recommended