Montagem de
Sequências de Transcritos
Daniel Guariz Pinheiro, PhD.
Laboratório de Genética Molecular e Bioinformática
Departamento de Genética
Faculdade de Medicina de Ribeirão Preto
Universidade de São Paulo
Planejamento
• Introdução
– Montagem de Sequências
– Algoritmos para Montagem de Sequências
– Softwares para Montagem de Sequências de
Transcritos
• Newbler
• Velvet
• Prática
– Newbler
– Velvet
Por quê sequenciar o transcritoma?
• Mantém o foco da pesquisa nas regiões gênicas do genoma;
• Acelera o processo de anotação genômica;
– Descoberta de novos genes e modelos gênicos;
• Visão geral da atividade gênica celular em determinado momento;
– Obtenção da expressão gênica relativa para diferentes células sob
diferentes condições;
• Pode auxiliar na identificação de eventos de processamento
alternativo de transcritos (e.g. Alternative Splicing) em tecidos ou
condições biológicas específicas;
• Detecção de mutações pontuais e/ou estruturais, tais como fusão
de genes;
Introdução
MONTAGEM DE SEQUÊNCIAS DE
TRANSCRITOS
Montagem
• Definição
– É uma estrutura hierárquica que mapeia os dados de
sequências de fragmentos para uma reconstrução
aproximada do alvo (neste caso transcritos) em sua
forma original;
• leituras (reads) => contigs => scaffolds
– A montagem agrupa sequências em contigs e contigs
em scaffolds (supercontigs);
– A montagem só é possível quando o
(transcriptoma) é excessivamente sequenciado;
alvo
Conceitos Básicos (1)
• contig – alinhamento múltiplo de leituras de onde é extraída uma
sequência consenso;
•
unitig – contig formado pela sobreposição de sequências únicas das leituras,
ou seja, sem ambiguidades;
• scaffold – definem a ordem e orientação dos contigs além do tamanho
dos gaps entre os contigs;
• singlets – leituras não agrupadas em um contig;
• gap – espaço entre dois contigs, onde não se conhece a sequência;
Gap
Conceitos Básicos (2)
• Cobertura (coverage)
– Total de pares de bases sequenciadas [N*L] dividido pelo tamanho da
região de interesse (genoma) [G]
• ((N*L)/G)
– Ex: Genoma de 1Mbp (G)
» 5 milhões de reads (N) de 50bp (L)
» Cobertura = (5.000.000 * 50) / 1.000.000 = 25X
– Na prática, corresponde a quantas vezes, em média, cada base do
genoma foi sequenciada;
– Profundidade (depth of coverage)
• Requisitos para o sequenciamento de genomas:
– Sanger: C. Venter (3Gb ~7.5x)
• [Levy et al., 2007]
– Roche 454: J. Watson (3Gb ~7.4x)
• [Wheeler et al., 2008]
– Illumina (52pb): Panda (Ailuropoda melanoleura) (2.4Gb ~73x)
• [Li et al., 2010]
Modelo Lander-Waterman
Estimar parâmetros (número esperado de contigs, tamanho dos contigs)
(Lander e Waterman, 1988)
L = tamanho das leituras
T = mínimo de sobrepsição entre leituras
G = tamanho do genoma (pool de transcritos)
N = número de leituras
c = cobertura (NL / G)
σ = 1 –T/L
• E(#contigs) = Ne-cσ
• E(tamanho do contig) = L((ecσ–1)/c+1–σ)
Modelo Lander-Waterman aplicado para estimar a
cobertura no transcriptoma de arroz [Zhang et al., 2010]
Genoma 1Mb
coverage 10x
~5 contigs
* quanto maior a cobertura
menos contigs são produzidos
porém maiores;
Montagem “de novo”
• Reconstrução da sequência (transcrito) em sua forma
original, sem a consulta de sequências previamente
resolvidas de genomas, transcritos e proteínas.
• A montagem é possível quando o alvo é
excessivamente amostrado com leituras “shotgun” que
se sobrepõem.
• Montagem de novo de dados de Next-Generation
Sequencing (NGS)
– tamanho das leituras (menos informação por leitura)
• necessidade de maior cobertura – aumento da complexidade;
– grande volume de dados
• necessidade de algoritmos que utilizem de forma racional e
eficiente os recursos computacionais (CPU/RAM);
Cobertura – nova geração de
sequenciadores
• Tamanho esperado de contigs
Panda e Cachorro
genoma de ~2.4Gb
[Schatz et al., 2010]
Avaliação da Montagem
• Montagens bem sucedidas:
– Montagens são medidas pelo tamanho e precisão dos contigs e
scaffolds;
– Tamanhos das sequências obtidas:
•
•
•
•
tamanho máximo;
tamanho médio;
tamanho total combinado;
N50 (tamanho do menor contig no conjunto dos maiores contigs que
combinados representam 50% da montagem) – contiguity;
– Valores muito altos podem representar erros na montagem e valores muito
pequenos podem representar montagem incompleta;
– Precisão dos contigs
• Medidas de satisfação e violações de restrições de montagem
(Phillippy et al., 2008);
– e.g. sequências sobrepostas no contig devem ter concordância entre si;
• Se a referência existe é útil e pode ser utilizada para a comparação;
– Comparações com proteomas de espécies próximas também podem ser úteis
para avaliação da montagem (Papanicolaou, et al. 2009);
N50
• https://www.broad.harvard.edu/crd/wiki/index.php/N50
• N50 - representação do tamanho médio (mediana ponderada) de
um conjunto de sequências;
• Dado um conjunto de sequências de tamanhos variáveis;
– N50 = tamanho N onde estão 50% das bases da montagem estão em
sequências de tamanho l < N;
– L = {2,2,2,3,3,4,8,8}
50% < N50(L) = 6
– tamanho combinado 32
– L’ = {2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8}
• 6 x (2); 6 x (3); 4 x (4); 16 x (8)
– N50(L) = mediana(L’) = 6
Desafios (1)
•
Contaminates nas amostras (e.g. Bacteria)
•
Ribosomal RNA (pequenas e grandes sub-unidades)
•
Artefatos gerados na etapa de PCR (e.g. Quimeras e mutações)
•
Erros de sequenciamento
– e.g. Roche 454 - erros de homopolímeros (3 ou mais bases consecutivas);
•
Presença de primers/adaptadores (e.g. adaptadores SMART utilizados na síntese
de cDNA);
•
Repetições e genomas poliplóides (sequências repetitivas no transcritoma torna a
montagem mais difícil);
– Necessidade de “spanners” – leituras que atravessam uma região de repetição e que possuem
suficientes regiões únicas em ambos os lados;
– Utilização de leituras paired-ends/mate-pairs e suas propriedades de tamanho e orientação,
estando um dos pares ancorado em uma região única;
Desafios (2)
• Passos extras na preparação das amostras e síntese de cDNA pode
levar a um maior risco de erros na clonagem ou contaminação;
• Transcritos muito abundantes (alta cobertura), transcritos pouco
abundantes (baixa cobertura);
• Processamento alternativo do RNA
– e.g. Alternative splicing
• Genes parálogos
• A falta de um genoma referência torna difícil o julgamento da
qualidade da montagem
Problemas recorrentes causados por
repetições
“k-mers”
• Subsequências de tamanho k
– Em uma sequência de tamanho (L) há (L-k+1) kmers;
– Exemplo: sequência de tamanho L=8 tem 5 k-mers
com k=4
ACGTACGA
ACGT
CGTA
GTAC
TACG
ACGA
k-mers Uniqueness ratio
k-mers – sequências de tamanho k
k-mers uniqueness ratio – número de k-mers distintas que ocorrem uma única vez no genoma
número total de k-mers distintas que ocorrem no genoma
Trichomonas vaginalis
[Schatz et al., 2010]
Introdução
ALGORITMOS PARA MONTAGEM DE
SEQUÊNCIAS
Algoritmos para montagem
• Três categorias (baseadas em grafos)
– Overlap/Layout/Consensus (OLC)
• grafo de sobreposições;
– de Bruijn Graphs (DBG)
• grafo de sobreposição de sufixo-prefixo de k-mers;
– Greedy graphs
• estrutura implícita de grafos de sobreposições;
Grafo
Grafo é uma estrutura G(V, A) onde V é um conjunto não
vazio de objetos denominados nós ou vértices
(nodes/vertices) e A é um conjunto de pares não
ordenados de V, chamado arestas ou arcos
(edges/arcs).
Nós (vértices): V = {U, V, W, X, Y, Z}
Arestas (arcos): A = {a, b, c, d, e, f, g, h, i, j}
Representação simplificada de um grafo qualquer
Overlap-Layout-Consensus (OLC)
•
Três passos:
– 1º detecção de sobreposição;
• Alinhamento pareado entre todas as leituras – identificação dos pares com melhor match
(alinhamento global + heurísticas [e.g. seed & extend]);
– 2º layout dos fragmentos (montagem do contig);
• Construção e manipulação do grafo de sobreposição (Analisar/Simplificar/Limpar);
• Caminho Hamiltoniano;
– 3º decisão da sequência (montagem do consenso);
• Alinhamento Múltiplo de Sequências – normalmente baseado na pontuação dos pares com
sobreposição (sum-of-pairs ou SP);
– Realiza ajustes no layout se necessário;
• Normalmente a frequência de um nucleotídeo em determinada posição determina a base
consenso;
Grafo de sobreposição:
nós - leituras;
arestas - sobreposições;
Caminho Hamiltoniano – caminho que
permite passar uma única vez por todos os
nós do grafo (contig) – caminho elementar;
sobreposições não consideradas – ?caminhos alternativos?
Softwares montadores (OLC)
• Utilizam o paradigma OLC:
– Phrap (http://www.phrap.org/)
• genomas
• Sanger, 454
• (Green, P., 1994 - unpublished)
– CAP3 (http://seq.cs.iastate.edu/)
• genomas, cDNAs
• Sanger, 454
• (Huang, X. and Madan, A., 1999)
– MIRA (http://sourceforge.net/projects/mira-assembler/)
• genomas, cDNAs
• Sanger, 454, Solexa
• (Chevreux, B. et al., 1999) (Chevreux, B. et al., 2004)
– Newbler (https://valicertext.roche.com/)
• genomas, cDNAs
• Sanger, 454
• Software Proprietário da Roche
Greedy Graphs
• Operação básica: dada alguma leitura ou contig, adiciona uma ou mais
leituras ou contigs (mais similares uns aos outros) de forma progressiva
até que não haja mais operações possíveis;
• Estrutura implícita de grafo, em que somente são consideradas as arestas
com alto score;
• Deve ter mecanismos para lidar com sobreposições falsas.
– Sobreposições de regiões repetitivas podem ter score alto e levar a erros na
montagem.
I - reads 1 e 2 (score 200)
II - reads 3 e 4 (score 150)
III - reads 2 e 3 (score 50)
Softwares montadores (Greedy)
• Baseados em grafos do tipo Greedy:
– SSAKE (http://www.bcgsc.ca/platform/bioinfo/software/ssake)
• genomas
• Solexa
• (Warren, R.L. et al., 2007)
– SHARCGS (http://sharcgs.molgen.mpg.de/)
• genomas
• Solexa
• (Dohm, J.C. et al., 2007)
– VCAKE (http://sourceforge.net/projects/vcake/)
• genomas
• Solexa
• (Jeck, W.R. et al., 2007)
grafos de-Bruijn
• Grafos k-mer
– nós – todas as subsequências de tamanho k;
– arestas – todas as sobreposições (k-1 bases) entre essas
subsequências que são consecutivas na sequência original;
– Pode representar as múltiplas sequências das leituras e
implicitamente as sopreposições;
aaccgg (k-mer 4):
aacc
accg
ccgg
ccggtt (k-mer 4):
ccgg
cggt
ggtt
Grafo de de-Bruijn:
nó – subsequência (k-mer);
arestas – sobreposições;
Caminho Euleriano – caminho que atravessa
cada aresta uma única vez (contig) – caminho
simples;
[Miller, et al. 2009]
Características dos grafos k-mers
• Em geral
– A montagem é um problema de redução de grafos.
• NP-difíceis, não há uma solução eficiente conhecida;
• Utilização de heurísticas: reduzir a redundância, reparar erros, reduzir a complexidade,
alargar caminhos simples e simplificar o grafo;
• Vantagens
– Desenvolvidos para lidar com a alta complexidade e o grande volume de dados
dos NGS;
– Rápida detecção de k-mers compartilhados - reduz custo computacional em
relação à busca de sobreposições em alinhamentos pareados;
• Não necessita comparações pareadas (todas x todas);
• Desvantagens
– Usam muita memória (tabela hash k-mers);
– Mais sensível a repetições e a erros de sequenciamento;
– baixa sensibilidade (perde algumas sobreposições verdadeiras), dependendo do:
• tamanho de k
• tamanho da sobreposição
• taxa de erro nas leituras
Tamanho de k
• Tamanho de k :não pode ser nem muito
grande, nem muito pequeno:
– grande o suficiente para não pegar falsas
sobreposições que compartilham k-mers por
acaso;
– pequeno o suficiente para que muitas
sobreposições verdadeiras compartilhem k-mers;
Características dos grafos de-Bruijn
•
O DNA é fita dupla, portanto a que se ter um mecanismo para identificar a correta
orientação;
– e.g. único nó (subsequência) com dois canais de entrada/saída – forward/reverse;
•
Repetições complexas (repetições em tandem, repetições invertidas, repetições
imperfeitas, repetições inseridas em outras repetições). Repetições maiores ou
iguais a k levam a grafos complicados, que não contêm por si só informações
suficientes para resolver a ambiguidade;
– e.g. recorrer às sequências originais e possivelmente a fragmentos mate-pairs/paired-ends;
•
Sequências palíndromes (idêntica à reversa complementar) induz a caminhos que
retornam a si (k=4; ACGT = ACGT);
– e.g. utilização de um k ímpar (k=5; ACGTA ≠ TACGT) evita esse tipo de ocorrência;
•
Erros de sequenciamento;
– e.g. pesar os vértices pelo número de leituras que lhes dão suporte auxilia na identificação de
erros;
Complexidades em k-mers
• Ramificações – caminhos sem-saídas
divergentes;
“tips”
– Induzidos por erros no sequenciamento nas
extremidades das leituras;
• Bolhas – caminhos que divergem e depois
convergem;
– Induzidos por erros no sequenciamento no meio
das leituras;
• Corda esfiapada – caminhos que convergem e
divergem;
– Induzidos por repetições;
[Miller, J.R., et al., 2010]
• Ciclos – caminhos que convergem neles
mesmos;
– Induzidos por repetições (e.g. repetições em
tandem – pequenos ciclos);
Exemplo
AGTCGAG CTTTAGA CGATGAG CTTTAGA
GTCGAGG TTAGATC ATGAGGC
GAGACAG
GAGGCTC
ATCCGAT AGGCTTT GAGACAG
AGTCGAG
TAGATCC ATGAGGC TAGAGAA
TAGTCGA CTTTAGA CCGATGA
TTAGAGA
CGAGGCT AGATCCG TGAGGCT AGAGACA
TAGTCGA GCTTTAG TCCGATG GCTCTAG
TCGACGC
GATCCGA GAGGCTT AGAGACA
TAGTCGA
TTAGATC GATGAGG TTTAGAG
GTCGAGG TCTAGAT
ATGAGGC TAGAGAC
AGGCTTT ATCCGAT AGGCTTT GAGACAG
AGTCGAG
TTAGATT ATGAGGC
AGAGACA
GGCTTTA TCCGATG
TTTAGAG
CGAGGCT TAGATCC TGAGGCT
GAGACAG
AGTCGAG TTTAGATC ATGAGGC TTAGAGA
GAGGCTT GATCCGA GAGGCTT GAGACAG
Exemplo
• Grafo completo
GATT
(1x)
TGAG ATGA GATG CGAT CCGA TCCG ATCC GATC AGAT
(9x) (8x) (5x) (6x) (7x) (7x) (7x) (8x) (8x)
AGAA
(1x)
GCTC CTCT TCTA CTAG
(2x) (1x) (2x) (2x)
TAGT AGTC GTCG TCGA CGAG GAGG AGGC GGCT
(3x) (7x) (9x) (10x) (8x) (16x) (16x)(11x)
CGAC GACG
(1x) (1x)
ACGC
(1x)
GCTT CTTT TTTA TTAG
(8x) (8x) (8x) (12x)
TAGA AGAG GAGA AGAC GACA ACAG
(16x) (9x) (12x) (9x) (8x) (5x)
Exemplo
• Após simplificação...
GATT
AGAT
GATCCGATGAG
GCTCTAG
AGAA
TAGTCGA CGAG
GAGGCT
CGACGC
GCTTTAG
TAGA AGAGA AGACAG
Exemplo
• Após remoção de tips...
AGAT
GATCCGATGAG
GCTCTAG
TAGTCGA CGAG
GAGGCT
GCTTTAG
TAGA AGAGA AGACAG
Exemplo
• Após remoção de bolhas
– Velvet (Tour bus)
• breadth-first traversal
• prioridade ao que tem maior cobertura (multiplicidade
no vértice)
AGAT
GATCCGATGAG
TAGTCGA CGAG
GAGGCT
GCTTTAG TAGA AGAGA AGACAG
Exemplo
• Simplificação final
AGATCCGATGAG
TAGTCGAG
GAGGCTTTAGA
AGAGACAG
Softwares montadores (de-Bruijn)
• Baseados em grafos de de-Bruijn:
– VELVET /Oases (http://www.ebi.ac.uk/~zerbino/velvet/)
• genomas, cDNAs
• Solexa, SOLiD
• (Zerbino, D.R. e Birney E., 2008)
– ABySS/Trans-ABySS
(http://www.bcgsc.ca/platform/bioinfo/software/abyss)
• genomas, cDNAs
• Solexa, SOLiD
• (Simpson, J.T, et al., 2009) (Birol, I., et. al., 2009)
Introdução
FERRAMENTAS PARA MONTAGEM
DE TRANSCRITOS
Softwares
NEWBLER
Instalação (Newbler)
• Registro para requisição de software
– http://454.com/contact-us/software-request.asp
• Download
– DataAnalysis_2.5.3_101207_1209.tgz
• Descompactar
– tar -zxvf /origin/of/software/DataAnalysis_2.5.3_101207_1209.tgz -C /destiny/path/
• Ir para o diretório destino
– cd /destiny/path/DataAnalysis_2.5.3/
• Executar setup.sh
– ./setup.sh
Funcionamento
•
Alinhamentos pareados entre as leituras (seed & extend);
•
Constrói Alinhamentos múltiplos de leituras com sobreposição e identifica regiões de com
diferenças consistentes entre os conjuntos de leituras e as divide em contigs (unitigs);
•
Montagem “contigs” (unitigs) e criação do grafo de contigs, baseado no alinhamento das
leituras que formam os contigs;
•
Resolução de estruturas de ramificação no grafo;
•
Extensão dos “contigs” é realizada por meio da visita a cada um dos nós do grafo;
•
Montagem da sequência consenso usando a informação da qualidade/sinal para cada
base nos alinhamentos múltiplos;
Se há dados disponíveis de sequências paired-end inclui uma etapa adicional:
•
Organização dos contigs em scaffolds, usando a informação dos pares e da distância
aproximada dos pares entre os contigs.
nós – leituras alinhadas de forma contígua (contigs)
arestas – leituras que alinham parte em um contig e parte em outro
Exemplo
•
( ) Identificar as sobreposições entre as leituras;
– seed & extend;
– Identificação de unitigs (A,B,C e Repeat);
•
•
( ) Construção do grafo de sobreposições;
( ) Percorrendo o grafo para obter a sequência consenso;
Princípios básicos Newbler
Definições (-cdna):
contig: Conjunto de leituras com regiões de sobreposição não contestáveis (“unitigs”)
e com diferenças consistentes entre os demais conjuntos de leituras. Um contig
pode representar um exon ou parte dele.
isogroup: É uma coleção de contigs que contêm leituras que os conectam, podendo
representar os contigs de um mesmo locus (gene).
isotig: Caminhos alternativos no grafo de contigs dentro de um isogroup. Um isotig
pode representar um transcrito individual, ou seja, uma isoforma do gene.
isotigs
• Conexões entre contigs em um isogroup representados por
sequências (leituras) com alinhamentos divergindo de forma
consistente em dois ou mais diferentes contigs ou por avaliação de
profundidade “depth spike”.
“depth spike”
Obs: cauda poly(A) - é ignorada portanto
não é possível determinar a
correta de orientação do transcrito.
isotig a partir de um único contig
Chamada básica do Montador
runAssembly [parâmetros] seqs.fasta
• Procura pelo arquivo seqs.fasta.qual no
mesmo diretório
• Cria o seguinte diretório (por padrão):
– P_yyyy_mm_dd_hh_min_sec_runAssembly
• P_ = Projeto, seguido de data e hora
Parâmetros mais comuns (1)
•
-cdna
– montagem em projetos transcritomas (cDNA);
•
-urt
– “use read tips” (extremidades das leituras) para produzir isotigs mais longos a partir de
únicas leituras;
•
-o output_directory
– informar o diretório onde serão armazenados os resultados;
•
-force
– força o reinicio da montagem, caso o diretório informado para os resultados já exista;
•
-vt trimmingFile.fasta
– informar um arquivo fasta com as sequências de vetores, primers ou adaptadores , que devem
ser excluídas das extremidades das leituras;
•
-vs screeningFile.fasta
– informar um arquivo fasta com as sequências cujas regiões devem ser mascaradas nas
leituras;
Parâmetros mais comuns (2)
•
-a num
–
•
-l num
–
•
número de processadores para uso (default=1);
-minlen num
–
•
mantém os dados de sequências na memória para aumentar a velocidade (necessita de RAM);
-cpu num
–
•
tamanho mínimo para o contig em 454LargeContigs/454Isotigs (default=500);
-m
–
•
tamanho mínimo para o contig em 454AllContigs (default 100) – obs.: 0 se -cdna;
tamanho mínimo de leituras para serem usadas na montagem;
-het
–
habilita o modo para considerar heterogizidade (e.g., organismos diplóides). Esperar uma maior
variabilidade.
Outros Parâmetros (1)
-cdna options
• -ig
– Isogroup Threshold (número máximo de contigs em um isogroup). Não serão formados isotigs
e aparecerão como contigs nos arquivos de saída (default: 500 contigs);
•
-it
– Isotig Threshold (número máximo de isotigs em um isogroup). O processo de percorrer o
grafo para e aparecerão como contigs nos arquivos de saída (default: 100 isotigs);
•
-icc
– Isotig Contig Count Threshold (número máximo de contigs em um isotig). Isotig não aparece
na lista e seus contigs poderão ou não aparecer na lista, dependendo se ele pertence ou não a
outro isotig (default: 100 contigs);
•
-icl
– Isotig Contig Length Threshold (tamanho mínimo de um contig para o isotig). Isotig não
aparece na lista e seus contigs poderão ou não aparecer na lista, dependendo se ele pertence
ou não a outro isotig (default: 3 bp);
Outros parâmetros (2)
•
-notrim
–
•
-p
–
•
especificar seed count parameter (default 1);
-ml
–
•
especificar seed length parameter (default: 16);
-sc
–
•
especificar seed step parameter (default: 12);
-sl
–
•
trata leituras separadamente, não agrupamento de duplicatas;
-ss
–
•
especificar que as leituras são paired-ends, caso contrário será detectada automaticamente;
-ud
–
•
desabilitar trimagem default de qualidade e primer;
especificar tamanho mínimo da sobreposição (default: 40);
-mi
–
especificar a identidade mínima da sobreposição (default: 90);
Manual
Roche Assembly manual (Part C)
Arquivos de saída (1)
• Arquivos de sequências e qualidades
– Contigs
• 454AllContigs.fna
>contig00001
>contig00002
length=542 numreads=16 gene=isogroup00001 status=isotig
length=2 numreads=43 gene=isogroup00001 status=it_thresh
• 454AllContigs.qual
– Isotigs
• 454Isotigs.fna
>contig00018
>isotig00003
gene=isogroup00001
gene=isogroup00004
length=3413
length=2675
numContigs=10
• 454Isotigs.qual
• 454Isotigs.faa (ORFs traduzidas)
>contig00018
>contig00018
1503
1824
3236
2369
-1
+3
1734
546
577
181
19
1
name/start/end/frame/nucleotide length/protein length/number of methionines
Arquivos de saída (2)
• Arquivos extras
– Alinhamentos de ORFs
• 454IsotigOrfAlign.txt
contig00018
-1:1503..3236*
-2:2660..2902
+3:2709..3152
2881
119
8
59
GGCGGGCAGTAAATATCATCATTGAGAATGCCCTCTTTCACTTGCAGAAAGAACAGGCGCTGAGTGATGTCCTGAATCAA 2960
.P..P..C..Y..I..D..D..N..L..I..G..E..K..V..Q..L..F..F..L..R..Q..T..I..D..Q..I..L
93
L..R..A..T..F..I..M..M
1
..R..A..V..N..I..I..I..E..N..A..L..F..H..L..Q..K..E..Q..A..L..S..D..V..L..N..Q..
84
– ACE (Como as leituras foram alinhadas para a formação dos Isotigs
- visualização Tablet)
• 454Isotigs.ace
– Estatísticas (Estatísticas da montagem, e.g. número de leituras e
bases alinhadas, sobreposições, tamanho médio dos contigs, etc.)
• 454NewblerMetrics.txt
– http://contig.wordpress.com/2010/03/11/newbler-output-i-the454newblermetrics-txt-file/
– Progresso de execução
• 454NewblerProgress.txt
Arquivos de saída (3)
• Leituras
– Status de cada leitura no alinhamento ( alinhamento 3’ e 5’
no contig);
• 454ReadStatus.txt
AccnoRead Status
F62E2P401D47TD
F62E2P401ALCTK
F62E2P401CVVLA
F62E2P401ANAAD
F62E2P401CE0XB
F62E2P401EC2X1
F62E2P401C259U
5' Contig
5' Position
Singleton
Outlier
TooShort
Repeat
PartiallyAssembled
contig03687
Assembled
contig02209
322
Assembled
contig00119
21
5' Strand
124
+
Assembled – Utilizada integralmente na montagem e coordenadas;
Too Short – Muito pequena;
Repeat – Identificada como repetitiva;
Outlier – Leitura problemática (e.g. quimera);
PartiallyAssembled – Somente aproveitada uma parte da leitura na montagem e coordenadas;
3' Contig
3' Position
contig03687
contig02209
48
contig00129
38
493
+
-
3' Strand
+
F62E2P401EC2X1 – inicia na base 48 contig02209 e termina na base 322
do contig02209 (a leitura na forma complementar-reversa está
integralmente dentro do contig02209)
F62E2P401C259U – inicia na base 21 contig00119 e termina na base 38
do contig00129 (leitura atravessa dois contigs)
– Pontos de trimagem originais e revisados das leituras para
a montagem
Accno
• 454TrimStatus.txt
Trimpoints Used Used Trimmed Length
F62E2P401BCQ2E
F62E2P401BGGG5
F62E2P401ATLP4
F62E2P401BJE8M
18-543
38-149
5-97
5-66
526
112
93
62
5-543
5-149
5-97
5-66
539
145
93
62
Trimpoints Orig – pontos de trimagem originais (presentes no sff ou fasta)
Trimpoins Used – trimagem realizada pelo montador
Orig Trimpoints Orig Trimmed Length
557
779
297
260
Raw Length
Arquivos de saída (4)
• Montagem
– Informações relacionadas à sequência consenso,
qualidade, profundidade (sequências únicas, ou seja,
não ambíguas), profundidade (sequências únicas
alinhadas – iguais ao consenso), sinal e desvio padrão
em cada posição do contig (somente SFF);
• 454AlignmentInfo.tsv
Position
>isotig00001
1
C
2
A
3
G
4
G
5
A
6
G
Consensus
1
64
2
64
2
64
2
64
2
64
2
64
2
Quality Score
Unique Depth
2
2
2
2
2
2
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
2.00
2.00
1.00
1.00
Align Depth
Signal
StdDeviation
Arquivos de saída (5)
• Grafos
– Estrutura de conexão entre contigs [3 seções – Nós (1) /Arestas (2)(3)];
• 454ContigGraph.txt
(1) ContigNum ContigName
Length
Average_depth
...
31
contig00031
12
1.4
32
contig00032
1633
80.3
33
contig00033
947
105.7
...
(2) Edge
FromContigNum
FromEnd
ToContigNum
ToEnd
...
C
32
5'
31
3'
5
C
32
3'
33
5'
20
...
S
22
2592
31:+;32:+;33:+
S
23
2580
32:+;33:+
S
24
947
33:+
...
(3) Edge
ContigNum
Sequence
Thru-FlowInformation
...
I
4
TGTTCGGTGTTCTCCGCCTCGGGCTGTCACAAATCGTGCTGCTGTGAGCCACTGCGTGCAGGTCTCAT
...
– Layout dos Isotigs
• 454IsotigsLayout.txt
>isogroup00007 numIsotigs=3 numContigs=3
Length : 12
1633 947
(bp)
Contig : 00031 00032 00033 Total:
isotig00022 >>>>> >>>>> >>>>> 2592
isotig00023
>>>>> >>>>> 2580
isotig00024
>>>>>
947
AlignmentReadDepth
2:2-3'..3-5';1:6-3'..3-5'
“I” short contig
•
seq. acima inicia antes do contig4 e termina depois =
dois fluxos de informação separados por ;
qtd de sequências:contig_anterior-extremidade..contig_posterior-extremidade
“P” paired-ends – como as sequências em pares atravessam contigs e permitem
scaffolds
“F” read-flow – como as sequências simples atravessam contigs e permitem
scaffolds
Exemplos
• Pool de 2 amostras de culturas de melanócitos
de epiderme humana normal
– 565.055 cDNA sequences (454 GS FLX)
– Newbler v2.5.3
• 9.681 Isotigs / “Isoformas de transcritos”
• -cdna
• parâmetros default
UCSC Genome Browser (1)
•
isogroup00003
–
•
isotig00001
Gene: DNAJC1
Softwares
VELVET
Compilação (Velvet/Oases)
• Makefile
– Compilar Velvet
make ’OPENMP=1’ ’CATEGORIES=3’ ’MAXKMERLENGTH=75’
– Compilar Oases
make ’VELVET_DIR=/path/to/velvet/’
•
Variável ambiente $PATH
– bash
export PATH=“${PATH}:/path/to/velvet/:/path/to/oases/”
Etapas de montagem com grafos
de-Bruijn
Construção da tabela hash
• velveth
– Criação de uma tabela hash a partir de um conjunto de sequências de leituras,
computando sobreposições entre k-mers.
– São gerados 2 arquivos (Sequences e Roadmaps) necessários para a
construção do grafo de-Bruijn pelo programa seguinte: velvetg;
• Sequences: sequências indexadas;
• Roadmaps: representação doas sobreposições entre os k-mers;
./velveth output_directory hash_length [[-file_format][-read_type] filename]
•
Principais parâmetros
–
–
hash_length é o tamanho dos k-mers em bp. Quanto menor o k mais lento!!!
read_type pode ser:
•
•
•
–
-short / -shortPaired
-short2 / -shortPaired2
-long / -longPaired
file_format pode ser:
•
•
•
-fasta (default)
-fastq
...
Construção do Grafo de-Bruijn (1)
• velvetg
– Construção e manipulação do grafo de-Bruijn, correção de erros e
resolução de repetições.
– Arquivos gerados:
•
•
•
•
•
•
•
•
•
contigs.fa - sequências consensos (gaps dentro contigs = N’s);
PreGraph - grafo intermediário 0;
Graph - grafo intermediário 1;
Graph2 - grafo intermediário 2;
LastGraph - descrição plena do grafo de-Bruijn produzido;
Log - descrição das ações executadas;
stats.txt - números relativos à montagem;
UnusedReads.fa - sequências não utilizadas na montagem;
velvet_asm.afg - formato compatível com AMOS;
./velvetg output_directory [options]
Construção do grafo de-Bruijn (2)
• Simplificação do grafo
– unificação de nós em cadeia
• Remoção de erros
– remoção de “tips” – cadeia de nós desconectada
no fim;
– remoção de “bubbles” – dois caminhos
redundantes que iniciam e terminam nos mesmos
nós (Algoritmo Tour Bus);
• remoção de conexões errôneas – remoção de nós e arcos
de baixa cobertura (erro sequenciamento);
Construção do Grafo de-Bruijn (3)
Principais parâmetros
-cov_cutoff <floating-point|auto>
: remoção de nós/arcos baixa cobertura
(sem remoção)
-ins_length <integer>
: distância esperada entre pares (sem
pareamento|auto)
-read_trkg <yes|no>
: tracking of posições das leituras na
montagem (no)
-min_contig_lgth <integer>
: tamanho mínimo para o consenso (k*2)
-amos_file <yes|no>
: exportar montagem arquivo AMOS (no)
-exp_cov <floating point|auto>
: estimativa da cobertura esperada
para regiões únicas, é usado na
resolução de repetições (sem leituras
longas ou em pares)
-long_cov_cutoff <floating-point> : remoção de nós com baixa cobertura
de leituras longas (sem remoção)
-unused_reads <yes|no>
: exportar leituras não aproveitadas em
UnusedReads.fa (no)
-exportFiltered <yes|no>
: exportar nós que foram eliminados pelo filtro
de cobertura (no)
-shortMatePaired* <yes|no>
: indica que a entrada é uma biblioteca matepair (no)
Estatísticas
• Arquivo tabular
–
–
–
–
–
–
–
–
–
–
–
–
ID
lgth
out
in
long_cov
short1_cov
short1_Ocov
short2_cov
short2_Ocov
long_nb
short1_nb
short2_nb
identificador do contig
tamanho em k-mers
número de arcos 3’
número de arcos 5’
cobertura em k-mers (long)
cobertura em k-mers (short1)
cobertura em k-mers – mapeamento perfeito (short1)
cobertura em k-mers (short2)
cobertura em k-mers - mapeamento perfeito (short2)
número de reads (long)
número de reads (short1)
número de reads (short2)
Cobertura k-mers
• Tamanho k-mers: Quantas vezes uma subsequência de
tamanho k é observada;
• Tamanho k-mers (Lk) e tamanho nucleotídeos (LN)
– Lk= LN-(k-1) = LN-k+1
– LN = Lk+(k-1) = Lk+k-1
– e.g. ACGTGAAG (LN = 8)
• k=3
– ACG / CGT / GTG / TGA / GAA / AAG (6)
– Lk = 8-3+1 = 6
• Cobertura k-mers (Ck) e cobertura nucleotídeos (CN)
– Ck = CN * (LN–k+1)/LN
– CN = (LN * CK)/(LN-k+1)
VelvetOptimiser
• Encontrar os “melhores” parâmetros (k-mer e cov_cutoff)
– VelvetOptimiser.pl [options] -f 'velveth input line‘
--help
--v|verbose+
--s|hashs=i
--e|hashe=i
--f|velvethfiles=s
--a|amosfile!
--o|velvetgoptions=s
--t|threads=i
--g|genomesize=f
--k|optFuncKmer=s
--c|optFuncCov=s
--p|prefix=s
This help.
Verbose logging, includes all velvet output in the logfile. (default '0').
The starting (lower) hash value (default '19').
The end (higher) hash value (default '31').
The file section of the velveth command line. (default '0').
Turn on velvet's read tracking and amos file output. (default '0').
Extra velvetg options to pass through. eg. -long_mult_cutoff -max_coverage etc (default '').
The maximum number of simulataneous velvet instances to run. (default '48').
The approximate size of the genome to be assembled in megabases.
Only used in memory use estimation. If not specified, memory use estimation
will not occur. If memory use is estimated, the results are shown and then program exits. (default '0').
The optimisation function used for k-mer choice. (default 'n50').
The optimisation function used for cov_cutoff optimisation. (default 'Lbp').
The prefix for the output filenames, the default is the date and time in the format DD-MM-YYYY-HH-MM_.
(default 'auto').
Advanced!: Changing the optimisation function(s)
Velvet optimiser assembly optimisation function can be built from the following variables.
Lbp = The total number of base pairs in large contigs
Lcon = The number of large contigs
max = The length of the longest contig
n50 = The n50
ncon = The total number of contigs
tbp = The total number of basepairs in contigs
Examples are:
'Lbp' = Just the total basepairs in contigs longer than 1kb
'n50*Lcon' = The n50 times the number of long contigs.
'n50*Lcon/tbp+log(Lbp)' = The n50 times the number of long contigs divided
by the total bases in all contigs plus the log of the number of bases
in long contigs.
Oases (1)
Carrega uma montagem preliminar produzida pelo
Velvet e agrupa os contigs em pequenos grupos,
chamados loci . Explorando as informações de
leituras em pares (paired-ends/mate-pairs) e leituras
longas, quando disponíveis, para construir as
isoformas transcritas dos genes;
Oases (2)
• Identificação de locus
– (Genes)
– Scaffolding contigs
• Identificação de isoformas
– (Transcritos)
– Scaffoldings alternativos
• Pontuação confiança para a montagem do transcrito.
– Assume que a maioria dos exons (nós) são constitutivos.
• 1 : montagem trivial;
• p/n : montagem alternativa;
– p = número de contigs (nós) no transcrito; n = número de contigs (nós) no
locus.
Alternative Splicing events (1)
• Problemas na montagem ao lidar com eventos
de “Alternative Splicing”
Alternative Splicing events (2)
• Splicing (de-Bruijn) graph
[Larcroix, et. al. WABI, 2009]
Alternative Splicing events (3)
• Oases utiliza Algoritmo de Programação Dinâmica
para iterativamente encontrar os caminhos com
maior peso no grafo de-Bruijn
– Busca por Splicing MOTIFs para inferir eventos de splicing:
• exon skipping (ES), alternate donor (AD), alternate acceptors (AA), intron
retention (IR), mutually exclusive exons (MEE), alternative polyadelination site
(aPS)
– Em fase de testes!!!
Oases (3)
./oases directory [options]
Standard options:
-ins_length2 <integer>
-ins_length_long <integer>
-ins_length*_sd <integer>
-unused_reads <yes|no>
-amos_file <yes|no>
-alignments <yes|no>
--help
Advanced options:
-cov_cutoff <floating-point>
: expected distance between two paired-end reads in the second shortread dataset (default: no read pairing)
: expected distance between two long paired-end reads (default: no read
pairing)
: est. standard deviation of respective dataset (default: 10% of
corresponding length)
[replace '*' by nothing, '2' or '_long' as necessary]
: export unused reads in UnusedReads.fa file (default: no)
: export assembly to AMOS file (default: no export)
: export a summary of contig alignment to the reference sequences
(default: no)
: this help message
: removal of low coverage nodes AFTER tour bus or allow the system to
infer it (default: 3)
-min_pair_count <integer>
: minimum number of paired end connections to justify the scaffolding of
two long contigs (default: 4)
-min_trans_lgth <integer>
: Minimum length of output transcripts (default: hash-length)
-paired_cutoff <floating-point> : minimum ratio allowed between the numbers of observed and estimated
connecting read pairs
-conserveLong <yes|no>
: Preserve contigs mapping onto long sequences to be preserved from
coverage cutoff (default: no)
Must be part of the open interval ]0,1[ (default: 0.1)
-scaffolding <yes|no>
: Allow gaps in transcripts (default: yes)
-degree_cutoff <integer>
: Maximum allowed degree on either end of a contig to consider it
'unique' (default: 3)
Arquivos de saída
• Arquivos gerados:
– transcripts.fa
• Sequências consensos dos transcritos (isoformas)
identificados
– >Locus_n_Transcript_x/y_Confidence_z_Length_LN
– >Locus_1_Transcript_1/2_Confidence_1.000_Length_399
– >Locus_1_Transcript_2/2_Confidence_1.000_Length_394
– splicing_events.txt
– contig-ordering.txt
Hawkeye
• http://sourceforge.net/apps/mediawiki/amos/index.php?title=Haw
keye
• Integrado ao AMOS – “A Modular, Open-Source whole genome
assembler”
• Boas estatísticas de montagem
• Suporte a somente alguns formatos de arquivos
– ACE, AFG, BNK
• Sistema instável
• Necessita compilar o pacote AMOS
• Sem páginas de ajuda
Tablet - Next Generation Sequence
Assembly Visualization
•
•
•
•
•
http://bioinf.scri.ac.uk/tablet/
Sistema Estável
Interface intuitiva
Instalação simples
Suporte a vários formatos de arquivos
– ACE, AFG, MAQ, SOAP2, SAM and BAM
• Importa atributos
– GFF3
• Exportar dados de cobertura por contig
(transcrito) – número de profundidade
por base do contig
– oases_asm.afg.txt
• Script para sumarizar os dados de
cobertura (coveragestats.py)
• Requer muita memória
Exemplos
• Linhagem celular HCC1954BL
– Linfoblastos humanos de uma paciente com
Câncer de Mama
– 5.995.729 (36bp) paired-end sequences (Illumina
RNA-Seq)
– Velvet/Oases
• 3.071 transcritos
• 31 k-mers
• -exp_cov 5 -cov_cutoff 0.360724128
UCSC Genome Browser (1)
•
Locus_2
–
2 transcritos (2 isoformas idêntificadas)
•
•
•
Gene: CD74
Locus_2_Transcript_1/2_Confidence_1.000_Length_1500
Locus_2_Transcript_2/2_Confidence_1.000_Length_1308
UCSC Genome Browser (2)
•
Locus_1
–
2 transcritos (2 isoformas idêntificadas)
•
•
•
Locus_1_Transcript_1/2_Confidence_1.000_Length_399
Locus_1_Transcript_2/2_Confidence_1.000_Length_394
Gene: RPL36A
UCSC Genome Browser (3)
•
Locus_1
–
2 transcritos (2 isoformas idêntificadas)
•
•
•
Locus_1_Transcript_1/2_Confidence_1.000_Length_399
Locus_1_Transcript_2/2_Confidence_1.000_Length_394
Gene: RPL36AL
Referências
•
•
•
•
•
•
•
•
•
•
•
•
Miller JR, Koren S, Sutton G. Assembly algorithms for next-generation sequencing data. Genomics.
2010 Jun;95(6):315-27. Epub 2010 Mar 6. Review. PubMed PMID: 20211242; PubMed Central
PMCID: PMC2874646;
Zerbino DR, Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs.
Genome Res. 2008 May;18(5):821-9. Epub 2008 Mar 18. PubMed PMID: 18349386; PubMed
Central PMCID: PMC2336801;
Schatz MC, Phillippy AM, Shneiderman B, Salzberg SL. Hawkeye: an interactive visual analytics tool
for genome assemblies. Genome Biol. 2007;8(3):R34. PubMed PMID: 17349036; PubMed Central
PMCID: PMC1868940;
Kumar S, Blaxter ML. Comparing de novo assemblers for 454 transcriptome data. BMC Genomics.
2010 Oct 16;11:571. PubMed PMID: 20950480; PubMed Central PMCID: PMC3091720;
Milne I, Bayer M, Cardle L, Shaw P, Stephen G, Wright F, Marshall D. Tablet--next generation
sequence assembly visualization. Bioinformatics. 2010 Feb 1;26(3):401-2. Epub 2009 Dec 4.
PubMed PMID: 19965881; PubMed Central PMCID: PMC2815658;
http://pt.wikipedia.org/wiki/Teoria_dos_grafos
http://contig.wordpress.com
http://genepool.bio.ed.ac.uk/bioinformatics/index.html
http://cbsu.tc.cornell.edu/nextgenworkshop2010w5.aspx
https://banana-slug.soe.ucsc.edu
http://www.stanford.edu/class/gene211
http://www.slideshare.net/bosc2010/chambwe-bosc2010
Conclusão
CONSIDERAÇÕES FINAIS
Conclusão
• Há uma diferenças enormes entre abordagens,
funcionalidades e eficiência entre os diferentes
algoritmos e implementações para as tarefas de
alinhamento de sequências e montagem;
• As diferentes abordagens refletem diretamente no
processamento e especialmente no resultado das
análises;
• Portanto é necessário conhecer os princípios de cada
abordagem, reconhecer os parâmetros e os resultados,
para podermos utilizá-los da melhor forma possível.
– Promover a utilização racional dos programas
disponíveis!!!
Daniel Guariz Pinheiro
[email protected]