Sequencing by Hybridization Aluno: Ennio Baptista ([email protected])[email protected] Orientadora: Kátia Guimarães ([email protected])[email protected]

Sequencing by

Hybridization

Aluno: Ennio Baptista ([email protected])

Orientadora: Kátia Guimarães ([email protected])

mailto:[email protected]






2

Sequenciamento de DNASequenciamento de DNA

• Objetivo : determinar a estrutura de uma molécula de DNA, identificando A SEQÜÊNCIA DE nucleotídeos componentes.• É o primeiro passo para a interpretação das informações genéticas codificadas no DNA, as quais determinam as características estruturais e funcionais de cada ser vivo

3

Técnicas de Técnicas de SeqüenciamentoSeqüenciamento• Overlap-layout-consensus : nos últimos

20 anos apresentou melhor resultado (CAP3, Phrap,TIGR)

1) é difícil obter as informações corretas sobre a sobreposição dos fragmentos

2) é difícil encontrar o caminho correto num grafo de overlap com muitas arestas falsas

4

Técnicas de Técnicas de SeqüenciamentoSeqüenciamento• Abordagem Alternativa : Em 1988, 4 grupos de pesquisas propuseram como alternativa uma nova técnica de seqüenciamento de DNA denominada Sequencing by Hybridization (SBH)

• Bains and Smith (1988)• Drmanac et al., 1989• Lysov et al., 1988• Southern, 1988

• Custo, velocidade, automação e eficiência

5

SBH : SBH : PrincípiosPrincípios

Duas etapas complementares bem definidas :

1. Etapa Bioquímica :

2. Etapa Computacional :

6

SBH : SBH : Etapa BioquímicaEtapa Bioquímica

Etapa experimental em que o spectrum da seqüência é identificado :

1) Todos os probes de tamanho ℓ são fixados em posições conhecidas na superfície do DNA chip ou microarray : C(ℓ) 4ℓ probes

2) O DNA chip é colocado em contato com uma solução contendo cópias da cadeia de DNA marcadas por fluorescência

7

SBH : SBH : Etapa BioquímicaEtapa Bioquímica

3) O DNA chip é lavado e as cópias que tiverem hibridizado com algum de seus probes permanecem ligadas à sua superfície.

4) Um procedimento de leitura revela as posições onde ocorreram as hibridizações o spectrum é determinado

8

SBH : SBH : Etapa BioquímicaEtapa BioquímicaEXEMPLO – DNA Chip C (4)

DNA target : TATCCGTTT

AA AT AG AC TA TT TG TC GA GT GG GC CA CT CG CCAAAT ATAGAGAC ACGCTA TAGGTTTGTCGAGTGG GGCAGC GCAACA CAAACTCGCC

Spectrum = {ATAG, AGGC, TAGG, GGCA, CAAA,

GCAA}

9

SBH : SBH : Etapa CombinatorialEtapa Combinatorial

• Etapa computacional para descobrir o posicionamento de cada um dos probes

• A reconstrução de uma cadeia original, a partir do seu spectrum, só é possível graças a uma característica peculiar de formação do spectrum, que garante que todos os ℓ-1 nucleotídeos finais de uma ℓ-tupla se sobrepõem aos ℓ-1 nucleotídeos iniciais da ℓ-tupla seguinte.

10


TATCCGTTT ||||||||| ATAGGCAAA ATAG TAGG AGGC GGCA GCAA CAAA

EXEMPLO – SequenciamentoDNA target : TATCCGTTT

Spectrum = {ATAG, AGGC, TAGG, GGCA, CAAA , GCAA}

11

• SBH Shortest Superstring Problem (SSP)

• SSP Traveling Salesman Problemo Grafo dirigido completo tendo os Vértices associados às ℓ-tuplas, e as arestas, às sobreposições

Spectrum S grafo G(V,A)


12

Spectrum S grafo G(V,A)


S : resultado do experimento bioquímico

G : grafo dirigido completo V = {ℓ-tuplas do spectrum S} A = {(p,q) : p e q se sobrepõem por

ℓ-1 caracteres}

13


EXEMPLOSBH e o Caminho Hamiltoniano

S = {ATG, AGG, TGC, TCC, GTC, GGT, GCA, CAG}

G

ATGTGCGCACAGAGGGGTGTCTCC

14


• “Existe uma correspondência de um para um entre caminhos que visitam cada vértice de G e fragmentos de DNA com o spectrum S”

• O Caminho Hamiltoniano dá a seqüência, mas nenhum algoritmo eficiente é conhecido (NP-completo)

15

SBH : SBH : Outras AbordagensOutras Abordagens

Em 1989, Pevzner propõe uma solução de tempo linear.

• Um grafo em que cada aresta representa uma ℓ-tupla, e cada vértice uma (ℓ-1)-tupla, sendo que cada (ℓ-1)-tupla v é incidente a uma (ℓ-1)-tupla w, se existir no spectrum uma ℓ-tupla com seus ℓ-1 nucleotídeos iniciais coincidindo com v, e seus ℓ-1 nucleotídeos finais coincidem com w

16

S = {ATG,TGG,TGC,GTG,GGC,GCA,GCG,CGT}

GT CG

AT TG GC CA

GG


EXEMPLO – Grafo proposto por Pevzner

17

O Caminho Euleriano dá a seqüência em tempo polinomial, mas tem limitações :

• Erros de experimentaçãoErros de experimentação• Repetições de Repetições de ℓℓ-tuplas-tuplas• Branching VertexBranching Vertex

Construções AmbíguasConstruções Ambíguas


18

S = {ATG,TGG,***,GTG,GGC,GCA,GCG,***}

GT CG

AT TG GC CA

GG


Construções Ambíguas : ErrosConstruções Ambíguas : Erros

19


Construções Ambíguas : ErrosConstruções Ambíguas : Erros

S = {ATG,TGG,***,GTG,GGC,GCA,GCG,***}

GT CG

AT TG GC CA

GG

20


Construções Ambíguas : Branching VertexConstruções Ambíguas : Branching Vertex


GT CG

AT TG GC CA

GG


GT CG

AT TG GC CA

GG

21



GT CG

AT TG GC CA

GG


GT CG

AT TG GC CA

GG

Construções Ambíguas : Branching VertexConstruções Ambíguas : Branching Vertex

22

SBH : SBH : Ficam algumas Ficam algumas perguntasperguntas

“Qual a probabilidade de um fragmento de DNA de tamanho n ser reconstruído, sem ambigüidade, por um DNA array C(ℓ) ?”

“Qual deve ser o tamanho de ℓ para reconstruir , sem ambigüidade, uma seqüência de tamanho n a partir de seu spectrum ?”

23


• Como superar o problema da reconstrução de seqüências ambíguas ?

1) projetos de chips alternativos (alternative chip designs)

2) protocolos interativos (interative protocols)

3) usar informação de localização (using location information)

4) usar uma seqüência homóloga conhecida (using a known homologus sequence).

(Pe’er, 2000:260)

Documents

Sequencing by Hybridization Aluno: Ennio Baptista ([email protected])[email protected] Orientadora: Kátia Guimarães ([email protected])[email protected]