Introdução à Montagem de Genomas
Gustavo Gilson Lacerda Costa
[email protected]
Histórico
•
•
•
•
•
•
•
•
•
•
•
•
1995, Haemophilus influenzae
1996, Methanococcus jannaschii
1997, Saccharomyces cerevisiae
1997, Escherichia coli
1998, Caenorhabditis elegans
2000, Drosophila melanogaster
2000, Arabidopsis thaliana
2001, Homo sapiens
2002, Schizosaccharomyces pombe
2002, Oryza sativa
2002, Mus musculus
2005, Pan troglodites
Onde sequenciar seu genoma
• Illumina (www.everygenome.com)
– $9500 por indivíduo
– $7500 para grupos de 5
• Serviço contratado sempre através do médico do
paciente
• O médico recebe um notebook com um
navegador genômico carregado com os dados do
paciente
Onde sequenciar seu genoma
• DNAVision (www.dnavision.com)
Onde sequenciar seu genoma
• Complete Genomics (www.completegenomics.com)
– Para grandes lotes, preço por genoma pode chegar a $5000
– Serviço voltado para empresas e instituições acadêmicas
MONTAGEM DE GENOMAS
Whole Genome Shotgun (WGS)
• Quebrar o DNA original em fragmentos aleatórios e
selecionar os fragmentos de determinado tamanho (Ex:
2Kbp)
Não sabemos a posição de cada fragmento no genoma
8
Whole Genome Shotgun (WGS)
• Sequenciar as pontas de cada fragmento
9
Whole Genome Shotgun - Montagem
DNA original
singlet
gap
10
Montagem de genomas (ab initio)
• Reconstruir a sequência do genoma, dados vários
(potencialmente milhões) fragmentos curtos de
sequência (os reads)
• Os reads têm tamanho entre 35-800 bp
• Os reads podem conter erros de sequenciamento
(mismatches ou indels)
• A orientação (5`3` ou 3`5`) de cada read é
desconhecida
TAMANHO DOS GENOMAS
Tamanho do genoma
3,4 Gbp
Homo sapiens
15 Gbp
Allium cepa
680 Gbp
Amoeba dubia
13
1pg ~ 1Gbp
Cobertura
• Total de pares de bases em reads dividido pelo
tamanho do genoma
• Ex: Genoma de 1Mbp
• 5 milhões de reads de 50bp
• Cobertura = (5000000 * 50) / 1000000 = 25X
• Na prática, corresponde a quantas vezes, em
média, cada base do genoma foi sequenciada
Cobertura
• É preciso ter várias coberturas para conseguir
montar contigs grandes (oversampling)
• Sanger: 8X a 10X
• 454 Titanium (pirosequenciamento): 15X
• Solexa: > 50X
Modelo de Lander-Waterman
L = tamanho do read
T = overlap mínimo
G = tamanho do genoma
N = número de reads
c = cobertura (NL / G)
σ = 1 – T/L
E(#clusters) = Ne-cσ
E(tamanho do cluster) = L((ecσ – 1) / c + 1 – σ)
cluster = contig ou singlet
17
Exemplo
Genome size: 1 Mbp L= 600
c
T= 40
N
1
#cluster #contigs bases não
sequenciadas
1,667
655
614
367,806
3
5,000
304
250
49,787
5
8,334
78
57
6,735
8
13,334
7
5
335
18
Modelo de Lander waterman
Medidas para avaliar uma montagem
•
•
•
•
Número de contigs
Tamanho médio dos contigs
Tamanho do maior contig
N50: maior N tal que 50% do total de pares de
base do genoma esteja contida em contigs >= N
bp
Cálculo do N50
• Seja uma montagem de um genoma de 300 bp que
produziu 8 contigs de tamanho (3, 3, 15, 24, 39, 45, 54 e
117)
• Ordenar os contigs em ordem decrescente de tamanho
e ir somando um por um
• Quando a soma ultrapassar 150 (300/2), o tamanho do
contig da vez é o N50
• Os dois maiores contigs (117+54=171) ultrapassam 150.
Logo N50=54 (tamanho do segundo maior contig)
Glossário de montagem
• Read: fragmento sequenciado
• Contig: Pedaço contíguo de sequência formado a
partir da sobreposição dos reads
• Singlet: read sem sobreposição com nenhum
outro
• Gap: região do genoma não capturada por
nenhum read
• Cobertura: Total de bases sequenciadas dividido
pelo tamanho do genoma
Paradigmas de montagem
I. Guloso (Greedy)
II. Overlap – Layout – Consensus (OLC)
III. Grafo de De Bruijn (DBG)
I - Guloso (Greedy)
• Phrap, TIGR assembler, CAP3
Guloso
• Criação de uma tabela de
sobreposições
• Pegue a sobreposição de melhor
score
• Junte os fragmentos
• Repita até que não possa ser
feita mais nenhuma junção
I - Guloso (Greedy)
• Phrap, TIGR assembler, CAP3
– Mesmo paradigma, diferentes resultados
– Cada programa usa uma série de heurísticas próprias,
pré e pós processamentos
– Cap3: montagem de ESTs (transcritos)
– Phrap e TIGR: genomas (pequenos e simples)
– Nenhum deles funciona bem com reads curtos
(Illumina/Solid)
II - Overlap – Layout – Consensus (OLC)
• Overlap: alinhamento par a par entre todos os
reads sequenciados para detectar sobreposições
• Layout: ordenação/orientação dos reads de
acordo com os overlaps
• Consensus: reconstrução da sequência do
genoma através do alinhamento múltiplo dos
reads (obedecendo ao layout)
II - Overlap – Layout - Consensus
• Montadores OLC usam uma estrutura de dados
chamada grafo de overlap
– Celera Assembler
– Arachne
– Mira
– Newbler
O que é um grafo?
• Informalmente, um grafo é um conjunto de
vértices conectados por um conjunto de arestas
Grafo direcionado
Grafo não direcionado
1
2
3
4
5
6
1
2
3
4
5
6
II - Overlap-Layout-Consensus
Grafo de overlaps
Vértices: reads
Arestas: overlaps
Overlap graph for a bacterial genome. The thick edges in the picture on the
left (a Hamiltonian cycle) correspond to the correct layout of the reads along
the genome (figure on the right). The remaining edges represent false
overlaps induced by repeats (exemplified by the red lines in the figure on the
right)
Fonte: http://www.cbcb.umd.edu/research/assembly_primer.shtml
III - Grafo de De Bruijn (DBG) Definição
• É uma representação de uma sequência (ou
conjunto de sequências) através de sua
decomposição em subsequências de tamanho K
(K-mer)
• Os vértices são sequências de k-1 caracteres
• Arestas são inseridas entre pares de vértices (u,v)
em que o sufixo de tamanho k-2 de u é igual ao
prefixo de tamanho k-2 de v
Construção de um grafo de De Bruijn
Reads= (GTGC,ATGT,GCCG,CGCA,TGCC) k=3
GT
AT
TG
CC
GC
CG
CA
Grafo de De Bruijn
K=8
Fonte: http://www.homolog.us/blogs/2011/07/28/de-bruijn-graphs-i/
Grafo de De Bruijn
GENOMA
E se o genoma fosse desconhecido?
Vamos ver como ficaria o grafo de De Bruijn construído a partir dos
reads
Cada read é decomposto em subsequências de tamanho K (K-mers)
e inserimos todos os K-mers no grafo de uma vez
Grafo de De Bruijn
Grafo de De Bruijn
• Sem erros de sequenciamento e com cobertura
alta
– DBG do genoma ~ DBG dos reads
• A sequência do genoma pode ser recomposta
através de um caminho euleriano no DBG
• Caminho euleriano: caminho que passa por todas
as arestas do grafo exatamente uma vez
• Se o DBG não for euleriano, tenta-se simplificá-lo
ao máximo e encontrar subgrafos eulerianos
Grafo de De Bruijn
• Erros de sequenciamento tipicamente geram
topologias características no DBG
Grafo de De Bruijn
• Repeats também
induzem topologias
características
Grafo de De Bruijn
• Repeats também
induzem topologias
características
Reconstituição do genoma com o DBG
Reads= (GTGC,ATGT,GCCG,CGCA,TGCC) k=3
GT
AT
TG
CC
GC
CG
CA
• Reconstruir a sequência do genoma é encontrar
um caminho euleriano (caminho que passa por
cada aresta uma unica vez)
Reconstrução da sequência (De Bruijn)
Reconstrução da sequência (De Bruijn)
Reconstrução da sequência (De Bruijn)
Reconstrução da sequência (De Bruijn)
Reconstrução da sequência (De Bruijn)
Reconstrução da sequência (De Bruijn)
Montagem - De Bruijn (Velvet, Euler-USR, Abyss)
• Escolha um valor de K, menor que o tamanho do read
– K grande: mais especificidade
– K pequeno: mais sensibilidade
• Inicie um grafo G vazio
• Para cada read sequenciado, divida-o em palavras de
tamanho k (k-mers), com passo de 1, e insira os k-mers
no grafo G
• Simplifique o grafo G (remova tips e bubbles)
• Busque caminhos eulerianos
• Se não houver, busque subgrafos eulerianos
Montagem - De Bruijn (Velvet, Euler-USR, Abyss)
• Os montadores DBG conseguem gerenciar quantidades
massivas de sequência
• Não precisa alinhar todo mundo contra todo mundo
• Construção do grafo em tempo linear
• Erros de sequenciamento -> grafo maior -> muita, muita
memória
O problema dos repeats
• Trechos de sequência repetidos ao longo do
genoma
• Em procariotos: pouco frequente
• Em fungos: média quantidade
• Em algumas plantas e em vertebrados compõem
a maior parte do genoma
• Desafio para qualquer software, independente
do paradigma usado
A
1
2
3
4
5
6
7
8
9
10
11
12
B
C
D
E
F
G
H
I
J
K
L
A
1
2
3
4
B
C
D
O problema dos repeats
• Vamos tentar reconstruir a seguinte frase
(genoma) a partir de alguns fragmentos (reads)
• It was the best of times, it was the worst of
times, it was the age of wisdom, it was the age of
foolishness, …
Qual a próxima palavra? Worst ou Age?
Erros de montagem causados por Repeats
excision
collapsed tandem
I
a
b
c
II
a
c
I
a
b
III
c
d
b
III
a
c
d
b
II
b
c
rearrangement
I
II
a
I
c
b
a
a
III
d
IV
e
d
III
f
II
e
b
IV
c
f
55
Resolvendo repeats com paired ends
56
O problema dos repeats
• O maior repeat tem tamanho 5. Logo eu
precisava de reads maiores que 6 para conseguir
montar sem ambiguidades
O problema dos repeats
• Ou então: vínculos par a par entre os reads com
distância conhecida (paired ends)
Construindo Scaffolds
• Os paired ends também são muito úteis para ordenar e
orientar os contigs
• Mesmo que não tenhamos a sequência entre dois contigs,
a informação de que eles são vizinhos é de grande valor
SCAFFOLD
59
Resumo do processo de montagem
Montagem
Scaffolding
60
Scaffolding
• Alguns montadores são capazes de produzir scaffolds
– Velvet
– Celera assembler
– SoapDeNovo
– Newbler
• Programas standalone
– Bambus
– Supercontigs
• Construção de scaffolds também é um problema
modelado em grafos (caminho de custo mínimo)
Tamanho do read, pairedends e cobertura
– Reads grandes facilitam a montagem. Se eles forem pareados
melhor ainda
• Reads longos podem atravessar repeats
• Reads paired-ends ajudam a resolver ambiguidades e
atravessar repeats maiores
– Cobertura alta também ajuda, mas só até um certo ponto
• Mais precisão para determinar as bases do consenso
• Diminui as chances de haver regiões do genoma não
sequenciadas
• Regiões do genoma de cobertura atipicamente alta
provavelmente representam repeats fundidos
5 November 2015 ·
Computational Genomics
Montagem comparativa
• Em algumas ocasiões, já existe um genoma de
algum organismo parecido sequenciado
(referência)
• Queremos saber as diferenças entre o nosso
genoma de interesse e a referência
• Mais simples computacionalmente
• Alinhamos os reads contra a referência, fazemos
o layout e o consenso
• Alignment-Layout-Consensus
Ressequenciamento
Ressequenciamento:
SNPS, variações estruturais, variações de número de cópias
reference genome
SNP
DEL
REFERÊNCIA= TODAY_IS_SUNDAY
Montagem ab initio
Montagem
comparativa