Projeto de Biologia Computacional - 2004

Parte 1: Alinhamento

Prazo de Entrega: 17 de outubro de 2004

Neste projeto vamos fazer o alinhamento de seqüências de DNA. Faremos alinhamento da primeira região espaçadora ITS1 (Internal Transcribed Spacer) do gene do rDNA de alguns moluscos. Os genes rDNA (DNA ribossômico) são genes que codificam rRNA. Os moluscos estudados são hospedeiros intermediários da Schistosoma mansoni, causador da esquistossomose.

O ITS1 é um trecho do DNA que é copiado para um RNA precursor. Esse trecho é removido e não aparece no rRNA. Para mais detalhes veja DNA in a cell. Esse trecho do RNA, bem como o trecho da segunda região espaçadora ITS2, é útil para estudos de filogênia. Recomendo que todos dêem uma olhada nesse paper.

Minha motivação para este projeto veio do trabalho Analysis of the First and Second Internal Transcribed Spacer Sequences of the Ribosomal DNA in Biomphalaria tenagophila Complex (Mollusca: Planorbidae) de T. Vidigal, L. Spatz, J. Kissinger, R. Redondo, E. Pires, A. Simpson e O. Carvalho.

Coletando os dados

Iremos buscar os nossos dados no GenBank. Uma boa página para começar a dar uma olhada no GenBank é NCBI GenBank Overview. Para obter as seqüências, vamos usar a página Entrez cross-database search.

As seqüências de nucleotídeos a serem procuradas têm números de acesso: AY030387, AY425730, AY425731, AY425732, AY425733, AY425734, AY425735, AY425736, AY425737, AY425738, AY425739, AY425740, AY425741, AY425742, AY425743 e AY425744. São esses os números que você deve digitar para fazer a busca. Note que é necessário escolher a opção para busca de Nucleotide.

Uma vez encontrada uma seqüência no GenBank, você verá uma página com várias observações sobre a seqüência. A seqüência do DNA propriamente dita está no fim da página. Uma das seqüências conterá mais do que o ITS1. Você precisará separar da seqüência toda somente o ITS1.

Armazenando os dados

Para armazenar os dados das seqüências obtidas vamos usar o formato definido pelo programa FASTA criado por William R. Pearson. Esse formato é bastante popular e utilizado por vários outros programas. Uma seqüência em formato FASTA começa com uma única linha de descrição, seguida por linhas da seqüência propriamente dita. A linha com a descrição começa com um símbolo ">" na primeira coluna. A seqüência termina quando um outro símbolo ">" é encontrado ou quando o arquivo termina. A seqüência pode conter quebras de linhas ou espaços em branco. As bases podem ser representadas por letras maiúsculas ou minúsculas (seu programa deverá aceitar entradas com letras maiúsculas ou minúsculas). Exemplo:

> AY425730 590 bp
aaaggtttct gtttcgcttt atcgatgata aacgaaagca gcaaaacaag tcaaaaactc
tcgtctcatc gccggccggg gcgtcgaagc gcacgaagcg cgctctggct ggtacgaccg
ctcctttgtc ggggtaccta cttgtcctcg atgcgaccca cggtggcggc ttgagcccac
cccttaataa gggggggggg gctcgccggg tcgcgaggtt caaagagtgg ccagctttcc
gtcctgtact cgctctctat agtacaactg ctctcggacg gagttggcga ccgccccatt
cacatttgtc cttttgagaa agtctccagg gtacctatgc cccctgacgg ctgctggcac
accgaccacg ctctgtaggt gtgcgtaagt ggcaaagtct cgagggtaga gagctcccac
gctcgtcttg tgggccgcga ggtttaaaga gccggtcggc atgctgctgc tctgcggcat
gcaggccggc cgccctggct ttcttacacg ttacctttac acaaactcat tgacacattg
tgaaaatttt tttccaaact atgggtgggc aacgctatac acmaaaagtt
> AY425740 585 bp
aaaggtttct gtttcgcttt atcgcacgat aaacgaaagc agcaaaacaa gccaaaaact
cctcgtctca ttgccggccg gggcgtcgaa gcgcacgaag cgccgctctg gctggtacga
ccgctccttt gtcggggtac ctactagtcc tcgatgcgat ccacggtggc ggcttagagc
cctcaagggg ctcgccgggt cgcgaggttc aaagagtggc cagcttccgt cttgtactcg
ctctctatag tacaactgct cttggacgga gttggcgacc gccccaattt tttttcatgt
ccttctgaga aagtctccag ggtacctatg ccccctgacg gctgctggca caccgaacac
gctctgtagg ttgtgcgtaa gcggccaagt ctcgagggta gagagctccc acgctcgtct
tgtgggccgc gaggtttaaa gagccggtcg gctgctgctg ctctgcggca tgtaggccgg
ccgccctggc tttcttacac gttaccttta cacaaactca tgtcacattg tgataattta
tttcaaaact atggtggcaa cgctatacac ccaaaagtaa caact

Como são representadas as seqüências

Além dos símbolos A, C, T, G, outros símbolos podem aparecer na seqüência. Esses outros símbolos representam subconjuntos do conjunto {A, C, T, G}. Existem 16 subconjuntos desse conjunto. Como não há necessidade do conjunto vazio ser representado, 15 símbolos são usados para representar esses subconjuntos.

Esses subconjuntos são usados quando na seqüência podem aparecer qualquer um dos nucleotídeos representados pelo subconjunto ou quando há incerteza sobre qual nucleotídeo que aparece na posição. Mais detalhes podem ser encontrados em http://www.chem.qmul.ac.uk/iubmb/misc/naseq.html#200. Reproduzo abaixo a tabela de recomendações do Nomenclature Committee of the International Union of Biochemistry (NC-IUB) e do International Union of Pure and Applied Chemistry (IUPAC) para a representação dos subconjuntos. Cada um desses símbolos, e não outros, podem fazer parte da seqüência dada de DNA.

Summary of single-letter code recommendations

Symbol Meaning Origin of designation

G G Guanine

A A Adenine

T T Thymine

C C Cytosine

R G or A puRine

Y T or C pYrimidine

M A or C aMino

K G or T Keto

S G or C Strong interaction (3 H bonds)

W A or T Weak interaction (2 H bonds)

H A or C or T not-G, H follows G in the alphabet

B G or T or C not-A, B follows A

V G or C or A not-T (not-U), V follows U

D G or A or T not-C, D follows C

N G or A or T or C aNy

Symbol	Meaning	Origin of designation
G	G	Guanine
A	A	Adenine
T	T	Thymine
C	C	Cytosine
R	G or A	puRine
Y	T or C	pYrimidine
M	A or C	aMino
K	G or T	Keto
S	G or C	Strong interaction (3 H bonds)
W	A or T	Weak interaction (2 H bonds)
H	A or C or T	not-G, H follows G in the alphabet
B	G or T or C	not-A, B follows A
V	G or C or A	not-T (not-U), V follows U
D	G or A or T	not-C, D follows C
N	G or A or T or C	aNy

Algoritmo de alinhamento

Vamos implementar um algoritmo de programação dinâmica para obter um alinhamento de pontuação ótima entre os pares de seqüências de bases dadas. Na implementação não serão penalizados buracos nas extremidades. Você deve prever pontuações/penalizações para:

alinhamento de bases iguais;
alinhamento de A com G (purinas);
alinhamento de C com T (pirimidinas);
abertura de buracos;
extensão de buracos e
outros alinhamentos não previstos.

Embora você deva escrever o seu programa permitindo facilmente alterar qualquer um dos parâmetros acima, para comparação entre os nossos programas (e também com os alinhamentos produzidos pelo pacote Clustal W) vamos usar a seguinte pontuação correspondente aos casos acima: (1) 19; (2) 9,5; (3) 9,5; (4) 30, (5) 6,66 e (6) 0.

Você deve supor como alinhamento de bases iguais o alinhamento de N (aNy) com qualquer outra base.

A entrada do seu programa pode ser um arquivo contendo duas seqüências a serem alinhadas ou um arquivo contendo todas as seqüências. O seu programa deve fornecer como saída a pontuação (similaridade) entre os pares de seqüências e uma representação do alinhamento propriamente dito. Como exemplo, reproduzo abaixo trechos produzidos pelo programa Clustal W para o par de seqüências acima. O símbolo * indica que houve alinhamento de símbolos iguais.

 CLUSTAL W (1.83) Multiple Sequence Alignments

Sequence format is Pearson
Sequence 1: AY425730        590 bp
Sequence 2: AY425740        585 bp
[...]
Group 1: Sequences:   2      Score:9937
[...]
AY425730        AAAGGTTTCTGTTTCGCTTTATCG-ATGATAAACGAAAGCAGCAAAACAAGTCAAAAACT
AY425740        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
                ************************ * ************************ ********

AY425730        C-TCGTCTCATCGCCGGCCGGGGCGTCGAAGCGCACGAAGCGC-GCTCTGGCTGGTACGA
AY425740        CCTCGTCTCATTGCCGGCCGGGGCGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTACGA
                * ********* ******************************* ****************

AY425730        CCGCTCCTTTGTCGGGGTACCTACTTGTCCTCGATGCGACCCACGGTGGCGGCTTGAGCC
AY425740        CCGCTCCTTTGTCGGGGTACCTACTAGTCCTCGATGCGATCCACGGTGGCGGCTTAG---
                ************************* ************* ***************     

AY425730        CACCCCTTAATAAGGGGGGGGGGGCTCGCCGGGTCGCGAGGTTCAAAGAGTGGCCAGCTT
AY425740        -AGCCCTCAA----------GGGGCTCGCCGGGTCGCGAGGTTCAAAGAGTGGCCAGCTT
                 * **** **          ****************************************

AY425730        TCCGTCCTGTACTCGCTCTCTATAGTACAACTGCTCTCGGACGGAGTTGGCGACCGCCCC
AY425740        -CCGTCTTGTACTCGCTCTCTATAGTACAACTGCTCTTGGACGGAGTTGGCGACCGCCCC
                 ***** ****************************** **********************

AY425730        ATTCACATTT---GTCCTTTTGAGAAAGTCTCCAGGGTACCTATGCCCCCTGACGGCTGC
AY425740        AATTTTTTTTCATGTCCTTCTGAGAAAGTCTCCAGGGTACCTATGCCCCCTGACGGCTGC
                * *    ***   ****** ****************************************

AY425730        TGGCACACCGACCACGCTCTGTAGGT-GTGCGTAAGTGGCAAAGTCTCGAGGGTAGAGAG
AY425740        TGGCACACCGAACACGCTCTGTAGGTTGTGCGTAAGCGGCCAAGTCTCGAGGGTAGAGAG
                *********** ************** ********* *** *******************

AY425730        CTCCCACGCTCGTCTTGTGGGCCGCGAGGTTTAAAGAGCCGGTCGGCATGCTGCTGCTCT
AY425740        CTCCCACGCTCGTCTTGTGGGCCGCGAGGTTTAAAGAGCCGGTCGGC-TGCTGCTGCTCT
                *********************************************** ************

AY425730        GCGGCATGCAGGCCGGCCGCCCTGGCTTTCTTACACGTTACCTTTACACAAACTCATTGA
AY425740        GCGGCATGTAGGCCGGCCGCCCTGGCTTTCTTACACGTTACCTTTACACAAACTCAT-GT
                ******** ************************************************ * 

AY425730        CACATTGTGAAAATTTTTTTCCAAACTATGGGTGGGCAACGCTATACACMAAAAGTT---
AY425740        CACATTGTGATAATTTATTTCAAAACTATGG--TGGCAACGCTATACACCCAAAAGTAAC
                ********** ***** **** *********   ***************  ***  *   

AY425730        ----
AY425740        AACT

O que entregar

Seu programa. Você deve entregar o seu programa fonte. Se o seu programa fonte consiste de mais de um arquivo, você pode entregar um arquivo tar.gz ou zip.
Relatório simples comentando o trabalho feito. Como sugestão, você pode comentar sobre o desenvolvimento do trabalho - dificuldades encontradas, sugestão para melhorar o projeto da próxima vez - e sobre o conteúdo - algum chute que pode ser dado sobre o parentesco (ou de falta de) das espécies correspondentes aos genes baseado nas pontuações obtidas dos alinhamentos. Comente também se o seu programa obtém as mesmas pontuações como nesta tabela. O relatório pode ser uma arquivo texto simples ou um arquivo em algum formato popular (pdf, html, ps ou mesmo doc).
Teste o seu programa com as seqüências contidas neste diretório. Cronometre o tempo que seu algoritmo leva para alinhar as seqüências de cada arquivo. Inclua no relatório esses tempos, analisando os resultados obtidos. Se o seu programa não conseguir alinhar algumas dessas seqüência, explique o motivo.
Como parte do relatório, inclua uma seção com um manual de uso de seu programa, contendo instruções de como compilar e testar o seu programa. Informe também o compilador que você usou para testar o programa.

Last modified: Mon Sep 20 17:41:05 BRT 2004