Séquençage par

hybridation

IFT 3290 – Bio-IFT 3290 – Bio-InformatiqueInformatique

Winnie Sheun Yee NgWinnie Sheun Yee NgHiver 2005Hiver 2005

Des puces d’ADNDes puces d’ADN

Une puce contient un ensemble de sondes d’une taille fixe c’est-à-dire tous les k-mers.

Une sonde est un fragment d’ADN sur la puce.

http://keck.med.yale.edu/affymetrix/technology.htm

Détection par hybridationDétection par hybridation Construire une puce de toutes les sondes

possibles de taille k. Incuber des fragments marqués de la

séquence cible avec la puce d’ADN. Les fragments de la séquence cible

s’hybrident avec les sondes dont les bases leur sont complémentaires.

Détection par hybridationDétection par hybridation Par spectroscopie, les sondes hybridées aux

fragments cibles sont détectées.

http://keck.med.yale.edu/affymetrix/technology.htm

Détection par hybridationDétection par hybridation La composition en k-mers de la séquence

d’ADN recherchée est identifiée. Reconstruction de la séquence cible par des

algorithmes combinatoires sur la composition en k-mers.

Séquençage par hybridationSéquençage par hybridation

Problème : Reconstruire une « string » à partir de sa composition en k-mers.

Entrée : Un ensemble, Spectrum, de tous les k-mers d’une « string » s inconnue.Sk(u) = {s[i, · · · , i+k − 1]: i = 1, · · · , |s| − k +1}.

Sortie : Une « string » s reconstruite à partir du Spectrum(s, k).

Approche 1 : SBH, un Approche 1 : SBH, un problème de chemin problème de chemin hamiltonienhamiltonien Recherche d’un chemin hamiltonien dans un

graphe de chevauchements où chaque k-mer de s (la séquence cible) est un sommet et où chaque chevauchement de taille (k-1) est un arc.

Définition : Un chemin hamiltonien est un chemin dans G qui passe une et une seule fois par chaque sommet.

Reconstruction de séquence par l’approche du chemin hamiltonien

Spectrum(s, k) = {ATG AGG TGC TCC GTC GGT GCA CAG}

où les sommets = k-mers du Spectrum ; et les arcs = chevauchements entre les k-mers.

Le chemin hamiltonien (chemin qui traverse tous les nœuds exactement une fois) correspond à la reconstruction de la séquence ATGCAGGTCC.

H

N. C. Jones & P. A. Pevzner

Reconstruction multiple de Reconstruction multiple de séquences par l’approche du séquences par l’approche du chemin hamiltonienchemin hamiltonien

Spectrum(s, k) = {ATG TGG TGC GTG GGC GCA GCG CGT}

Un tel Spectrum(s, k) résulte en deux chemins hamiltoniens distincts.

H

N. C. Jones & P. A. Pevzner

Reconstruction multiple de Reconstruction multiple de séquences par l’approche du séquences par l’approche du chemin hamiltonienchemin hamiltonien

Spectrum(s, k) = {ATG TGG TGC GTG GGC GCA GCG CGT}

ATGCGTGGCA

H

N. C. Jones & P. A. Pevzner

Reconstruction multiple de Reconstruction multiple de séquences par l’approche du séquences par l’approche du chemin hamiltonienchemin hamiltonien

Spectrum(s, k) = {ATG TGG TGC GTG GGC GCA GCG CGT}

ATGGCGTGCA

H

N. C. Jones & P. A. Pevzner

ComplexitComplexité du problème du é du problème du chemin hamiltonienchemin hamiltonien Le problème du chemin hamiltonien est

NP-complet c’est-à-dire que le temps de calcul nécessaire à sa résolution croît trop vite par rapport à la taille des données à traiter.

Approche 2 : SBH, un Approche 2 : SBH, un problème de chemin eulérienproblème de chemin eulérien Recherche d’un chemin eulérien dans un

graphe de chevauchements où tous les sommets sont toutes les sous-chaînes de longueur k-1 et où chaque k-mer de s est un arc entre son préfixe et son suffixe de taille (k-1).

SBH, un problème de chemin SBH, un problème de chemin eulérieneulérien Définition : Un chemin eulérien est un chemin

dans G qui visite chaque arc exactement une fois.

)degre )degre arcs outin vvGEuler ((,

Reconstruction de séquence Reconstruction de séquence par l’approche du chemin par l’approche du chemin eulérieneulérien

Spectrum(s, l) = {ATG TGG TGC GTG GGC GCA GCG CGT}

où les sommets = (k-1)-mers ; et les arcs = k-mers du Spectrum.

GT CG

CAGC

GG

TGAT

N. C. Jones & P. A. Pevzner

Reconstruction de séquence Reconstruction de séquence par l’approche du chemin par l’approche du chemin eulérieneulérien

GT CG

CAGC

GG

TGAT

GT CG

CA

GG

TGAT

GC

Les chemins eulériens du graphe (chemin qui traverse tous les arcs exactement une fois) correspondent aux séquences.

N. C. Jones & P. A. Pevzner

Nombre de chemins Nombre de chemins eulérienseulériens

1)! - )degreinVv

vGc (()(

où c(G) = cofacteur de M.

Soit une matrice A = (aij), où aij = 1 s’il existe une arête allant du sommet I au sommet j dans le graphe eulérien G et aij = 0 sinon. Soit M la matrice –A et dont les éléments de la diagonale sont remplacés par degrein(i) pour tout i.

G

Chaque c(G) de M = 2. Le nombre de cycles eulériens dans G est 2 • 0! • 1! • 1! • 0! = 2

1100

0211

1120

0011

;

0100

0011

1100

0010

MA

ComplexitComplexité du problème du é du problème du chemin eulérienchemin eulérien La recherche du parcours eulérien se fait en

temps linéaire avec un parcours en profondeur.

À noterÀ noter L'assemblage par parcours eulérien est

ambigu : il a beaucoup de chemins eulériens.

Des méthodes biochimiques permettent de discriminer les hybridations non-spécifiques dans les expériences SBH.

Améliorer la puissance de Améliorer la puissance de résolution du SBHrésolution du SBH Le séquençage positionnel par hybridation

est proposé. Le PSBH permet de mesurer

approximativement la position de chaque k-mer du fragment d’ADN cible.

PSBH se réduit à trouver un parcours eulérien avec la restriction additionnelle que la position de tout arc est dans l’intervalle de positions associé à cet arc.

Fin…Fin… Questions? Commentaires.

Annexe :Annexe :Tailles…Tailles…

La longueur maximale d’un fragment d’ADN qui peut être reconstruite avec une tableau C(k) est estimée à √(2•4k).

La longueur minimale de la sonde pour reconstruire une séquence de taille n à partir de son spectrum est estimée à .

l42

2log 1

nk

p

Annexe :Annexe :Manufacturer des puces Manufacturer des puces d’ADNd’ADN Une puce d’ADN est manufacturée par VLSIPS

« very large scale immobilized polymer synthesis ».

Les sondes sont développées un nucléotide à la fois à travers le processus photolithographique (série d’étapes chimiques).

Chaque nucléotide a un « groupe protecteur  photolabile » qui empêche la croissance de la sonde.

Annexe : Annexe : Manufacturer des puces Manufacturer des puces d’ADNd’ADN Ce groupement protecteur est désactivé par la

lumière. À chaque étape chimique, une région prédéfinie

du « array » est illuminée en activant ainsi la croissance nucléotidique.

Tout le « array » est exposé à un nucléotide particulier mais les réactions d’ajout du nucléotide se produiront seulement sur les sondes de la région activée.

Annexe : Annexe : Manufacturer des puces Manufacturer des puces d’ADNd’ADN En concaténant les nucléotides sur les sondes

approppriées des régions approppriées, il est possible de développer un ensemble de sondes de taille k en moins 4•k étapes.

Cependant, à cause de la diffraction, de la réflexion interne et de la dispersion, les points proches des limites des régions illuminées sont exposés à une illumination imprévue.

Ainsi, des sondes de composition et de taille inconnues sont construites.

Annexe : Annexe : ComplexitComplexité du problème du chemin é du problème du chemin eulérieneulérien

Si la multiplicité des arcs n’est pas connue, il s’agit alors du problème du facteur chinois où on recalcule, en temps polynomial, les multiplicités minimales qui permettent de parcourir le graphe.