Introduction

Ce travail est une description de la conférence de Miklòs Csurös, conférence présentée le 4 mars 2004. Le travail comporte trois sections, soit une description biologique de l’expérience, une analyse probabiliste de la méthode proposée et une mise en contexte informatique des outils utilisés.

Le but de la présentation de M. Csurös était de nous présenter la nouvelle version de la méthode CAPSS. Cette méthode propose de séquencer un génome dans un temps moindre et en réduisant les coûts de laboratoire. La version améliorée de CAPSS, qui est encore expérimentale, se doit de réduire les biais et autres erreurs en proposant un différent plan d’expérience pour la collecte et le traitement des données. Certain projet utilise présentement CAPSS, il en sera question dans le travail.

Bonne lecture !

Partie biologique

Pour une mise en contexte, je vais, préalablement à la description de la démarche, esquisser les grandes lignes d’un séquençage shotgun. C’est une méthode utilisée dans l’expérience.

Séquençage shotgun : La technique shotgun permet le séquençage de larges portions aléatoires de génome (plus longue que la moyenne). L’idée shotgun vient de la méthode de clonage des fragments de séquences dans un vecteur universel.

Voici les étapes importantes de la technique :

Construire la librairie :

Fragmentation de l’ADN génomique en fragments de 1 à 1,5 k pb

Plus récemment on utilise des BACs, les fragments sont de 350 k pb

(Les bactéries (BAC) reproduise facilement l’ADN)

Clonage dans un vecteur universel

Séquençage en shotgun

Réaction de séquençage par amorce universelle d’une portion aléatoire des vecteurs chimériques de la librairie
Assemblage des séquences en contigs
Identification des gaps

i. Amorces dérivées des régions flanquent le gap

ii. Sélection d’un sous-clone couvrant le gap

Assemblage

Comparaison des séquences entre elles
Alignement

Le principe de base de CAPSS, soit le séquençage en shotgun, réduit le temps global de manipulation associé au séquençage en passant par une fragmentation aléatoire du génome. Ces parties seront ensuite testées pour des chevauchements suffisamment longs pour construire un contig qui, joint aux autres contigs, pourra mener à l’identification de la séquence du génome entier.

But de CAPSS

Lors de séquençage, la taille impressionnante des génomes demande un travail fastidieux. En particulier, lorsque nous travaillons sur des organismes supérieurs. Les coûts monétaire (laboratoire) et temporel (algorithmique et laboratoire) deviennent rapidement exorbitant.

La stratégie de séquençage proposée par M. Csurös et son équipe a pour but de réduire de façon radicale le nombre de librairies et séquences nécessaires au séquençage d’un génome entier. L’approche est appelée CAPSS, Clone-Array Pooled Shotgun Sequencing. Elle utilise un séquençage basé sur des librairies BACs.

L’expérience en cours teste l’exactitude de la stratégie CAPSS. À cette fin, un modèle probabiliste fut créé pour vérifier les progrès de CAPSS. Bien que l’article ne le spécifie pas, je suppose que le séquençage du génome est fait chromosome par chromosome. Plusieurs biais sont ainsi évités. (Dû aux régions répétées entre les différents chromosomes). Nous verrons plus loin qu’il y a déjà plusieurs sources d’erreurs à considérer, inutile d’en créer.

Méthode utilisée pour couper l’ADN

Les coupures des segments d’ADN peuvent être aléatoires ou contrôlées. Dans les cas où il faut contrôler les longueurs des sous segments ou les sites de coupures, il est possible d’utiliser des enzymes de restrictions. Quelques centaines d’enzymes de restrictions existent. Dans l’expérience présente, les coupures sont contrôlées.

Description de la démarche

Figure 1 : La démarche d’un séquençage par CAPSS

Étapes :

1- D’abord, plusieurs copies du chromosome à séquencer sont isolées. Nous considérerons ce chromosome comme étant la séquence de référence.

2- Fragmenter les copies de la séquence de référence en sous séquences de 150k pb.

3- Insérer ces fragments dans des BACs, facilitant l’amplification et permettant l’entreposage des sous séquences. (Création de la librairie clone)

4- Création d’une librairie shotgun. Cette librairie est un sous-ensemble d’ensemble de clones. C’est au travers de cette étape que sera séquencé exhaustivement le fragment du génome inséré dans le BAC. C’est-à-dire que chaque BAC est pris séparément et des parties sont séquencées aléatoirement. Ceci produit un groupe de petites séquences provenant toutes du BAC. Lorsque le séquençage est terminé, il y a élimination les séquences associées au vecteur bactérien. Des outils informatiques vont procéder à des alignements entres les séquences et trouver des sites de chevauchement, sites qui serviront à produire une séquence virtuelle nommée contig.

5- Finalement, grâce à un algorithme informatique, il y a un assemblage de la séquence de référence. Les chevauchements entre les BACs permettent de déterminer, par des alignements, l’ordre des clones.

Innovation

La partie innovatrice de l’expérimentation arrive au niveau de la cartographie physique et du séquençage des BACs. Pour avoir une couverture complète de la séquence de référence, il n’est pas nécessaire de conserver tous les fragments de toutes les copies de la séquence de référence. En conservant des fragments qui se chevauchent (très utile à l’assemblage) et qui couvrent le chromosome entier, on peut, à frais moindre, séquencer le génome. L’expérimentation prévoit que les chevauchement doivent être d’au moins 20k pb pour être détectés. Ainsi, les fragments appartenant au chevauchement de deux autres fragments seront rejetés.

Exemple :

Figure 2 : Exemple de couverture redondante d’un chromosome par des sous séquences clones

Nous pouvons ici voir que la séquence 4 est entièrement comprise dans le chevauchement des séquences 3 et 5. Donc la séquence 4 cause de la redondance et peut être enlevée de l’ensemble de recouvrement minimal.

Il faut ainsi déterminer, parmi l’ensemble des BACs, le sous ensemble minimal qui couvre entièrement la séquence de référence en prévoyant des chevauchements d’au moins 20k pb. (Les chevauchements ne doivent pas être trop longs non plus.) Comme le but de l’expérimentation est de réduire la quantité de séquençage, seuls les extrémités des clones (BACs) sont séquencés pour déterminer les chevauchements et, finalement, l’ensemble minimal.

Ainsi, une étape de présélection des clones, soit une cartographie basée sur les chevauchements des extrémités et ne demandant qu’un séquençage fractionnaire de chaque clone, est effectuée.

La nouvelle approche est basée sur le pooled shotgun sequencing (PSS) et elle ne restreint pas la librairie shotgun à provenir d’un seul BAC. Elle provient d’un ensemble de BACs distribué sur une plaque (tableau) de puits. Les ensembles sont soit les BACs d’une colonne ou les BACs d’une rangée.

Figure 3 : Un exemple de tableau de puits. Chaque puit contient exactement un BAC.

Une librairie shotgun provient de l’ensemble des BACs d’une colonne ou d’une rangée.

Le but est toujours de produire un contig à partir des extrémités séquencées. Par construction du modèle, un contig provenant des séquences du pool d’une colonne et d’une rangée est associé au BAC intersectant ces colonnes et rangées.

La méthode PSS est l’étape de présélection visant à cibler les BACs pouvant, à eux seuls et sans redondance, être mis bout à bout pour reconstruire le génome. En fait, la méthode permet de réduire le nombre de librairies shotgun à un facteur de 2ÖN, (où N = nombre de clones).

En effet, selon la méthode clone par clone, une librairie est construite pour tout clone. Un total de N librairies est nécessaire. Pour la méthode PSS, il y a ÖN pools colonnes et ÖN pools rangées. À raison d’une librairie par pool, 2ÖN librairies sont construites.

L’approche n’est pas sans faille. C’est ici que l’amélioration de CAPSS entre en ligne de compte. Il faut réduire les biais…

Difficultés dans la cartographie des contigs

Des problèmes sont rencontrés lors de la cartographie des contigs. Trois problèmes sont considérés majeurs. Notons que les BACs sont distribués sur un seul tableau dans la version initiale de CAPSS.

Un premier type d’erreur pouvant survenir est le faux négatif, où un BAC n’est pas échantillonné dans un pool de rangées ou de colonnes. Cette première limite n’est cependant qu’un résultat d’un nombre de fragments shotgun trop faible et peu facilement être évité par un design judicieux de la manipulation. En effet, c’est un biais présent dans un plan d’expérience rectangulaire, et qui sera réduit dans un plan transversal.

Les deux autres problèmes pouvant émerger sont issus de situations où il y a des chevauchements entre les clones ou lorsque deux clones possèdent des régions trop similaires. On les nomme ambiguïtés et faux positifs (false mapping). Le premier cas, l’ambiguité, fait référence au fait que plusieurs clones puissent être sélectionnés comme pouvant contenir la séquence d’un contig. L’ambiguïté apparaît lorsque le contig est le résultat d’un pool d’au moins deux colonnes et deux rangées. Le clone contenant la séquence du contig se trouve donc à être parmi un choix de quatre puits possibles.

Dans le cas d’un faux positif, un contig est assigné à un clone ne contenant pas la séquence du contig. Ceci est possible si le contig n’est pas résultant du clone à l’intersection d’une colonne et d’une rangée, mais le produit du chevauchement entre fragment shotgun d’un autre puit dans la rangée du faux positif et d’un autre puit dans la colonne du faux positif. Cet agencement crée l’illusion que le clone est à l’intersection

Un faux positif est plus grave, en pratique qu’une cartographie ambiguë. Il ne peut être détecté pendant la cartographie de contigs.

Exemple :

Figure 4 : Chaque case de ce tableau contient un et un

seul BAC. De plus, tous les BACs sont différents.

Dans la figure 4, supposons que les clones B et E partagent une séquence.

Lors de l’assemblage de la rangée R₄ et la colonne C₅, le BAC A est assemblé et contient la séquence commune au clone C.

Les clones B et E génèrerons également des contig lors de l’assemblage des pools (R₄, C₅) et (R₈, C₈).

Les clones A et F explicitent la possibilité d’une difficulté dans la cartographie. Dû aux clones B et E, le même contig peut être assigné aux clones A et F à la fois.

De façon générale, si un contig contient des fragments de deux pools-rangées (i et k) et deux pools-colonnes (j et l ), alors il y a quatre BACs potentiels pour la cartographie, soient les quatre intersections des colonnes et rangées. Ce qui amène 2 choix de pair de clones (pair d’intersections), soient (B_ij, B_kl) et (B_il, B_kj).

Par l’exemple des quatre BACs, aux intersections, un faux positif arrivera si un contig C contient des fragments d’un seul pool-colonne et pool-rangée. Dans le cas où la conclusion veut que C e Bij, mais en réalité C e B_i,lÇ B_k_,j.

Solution :

L’une des décisions à prendre pour la manipulation des données en vue d’une l’analyse statistique est le type de plan d’expérience utilisé. Dans le cas présent, un plan d’expérience rectangulaire posait trop de problèmes de biais, entre autre ceux mentionnés précédemment, lors de l’assemblage. La version initiale de CAPSS utilisait un plan rectangulaire. Pour améliorer l’outil, c’est le plan transversal qui est donc adopté. En particulier un plan double tableau, où les mêmes séquences BACs sont distribuées dans deux tableaux.

Le plan transversal utilise m groupes de BACs. Ces derniers sont distribués dans 2m tableaux. Chaque clone est inclus une et une seule fois dans chaque tableau du groupe. De plus, une des propriétés les plus importantes de ce plan est que pour toutes paires de BACs, ils sont dans une même rangée ou une même colonne au plus une fois dans les deux tableaux.

Par exemple, premier tableau distribuant un ensemble de 25 BACs

17	22	2	7	12
21	1	6	11	16
25	5	10	15	20
4	9	14	19	24
8	13	18	23	3

Deuxième tableau contenant le même ensemble de 25 BACs. La distribution de ce tableau repose sur un réarrangement du premier tableau

15	18	1	4	12
22	25	3	11	14
24	7	10	13	21
6	9	17	20	23
8	16	19	2	5

Ainsi, en sélectionnant dans les deux tableaux les pools de la colonne et de la rangée de la séquence k, elle sera l’unique élément de l’intersection de ces 2 ensembles. L’avantage de cette propriété est que les problèmes de biais sont théoriquement nuls. En pratique, ils sont énormément réduits par rapport au plan rectangulaire. De plus les contigs cartographiés à deux clones simultanément indiquent un chevauchement des clones. D’autres solutions ont été proposées, par exemple le tableau « spare », mais celle-ci semble la plus efficace.

Partie Informatique

Séquençage d’un BAC

Le problème de séquençage est de déterminer la chaîne la plus courte contenant tous les fragments shotgun comme sous segment. Ce problème est bien connu en informatique et a quelques applications en biologie computationnelle. Entre autre, dans l’assemblage de fragments.

La définition (formelle) informatique du problème est :

Soit S une alphabet S = {a, c, g, t}

Soit F = { s_i | s_i e S^* } F est l’ensemble des fragments du BAC

(On suppose que tous les s_i sont distincts, mais les chevauchements sont permis.)

Déterminer la chaîne minimale S telle que tous s_i e F est sous chaîne de S.

Remarquons premièrement que nous avons affaire à un problème d’optimisation. De plus, le problème de la chaîne minimale est NP-Dur. Par définition intuitive, ce problème est au moins aussi difficile qu’un problème NP-Complet. Donc résoluble en temps exponentiel.

Pour palier au problème de complexité temporel, quelques heuristiques ont été inventées. Parmi les heuristiques existantes, le meilleur, dans un ratio (valeur déterminée) / (valeur optimale), est 2,5. Les heuristiques s’inspirent du problème du commis-voyageur et de la théorie des graphes.

Aparté :

Il est intéressant de savoir que quelques variantes du problème de la chaîne minimale existent. Ces variantes semblent être spécifiques à la biologie computationnelle.

Soit S une alphabet S = {a, c, g, t}

Soit F = { s_i | s_i e S^* } F est l’ensemble des fragments

Soit e tel que 0 < e < 1

Soit t un entier naturel non nul

Encore une fois, les chevauchements entre les s_i sont permis, mais les inclusions sont supposées inexistantes.

Première variante :

Déterminer la chaîne minimale S contenant tous les s_i, tel que, pour tous les s_i de F, la distance entre S et s_i est au plus e|s_i|. Notons que la distance dans le cas présent ne pénalise pas les gaps aux deux extrémités des s_i.

Seconde variante :

Déterminer la chaîne minimale S contenant tous les s_i, tel que, pour tous les s_i de F, la distance entre S et s_i est au plus e|s_i|. Deux sous chaînes consécutives de S ont un chevauchement d’au moins t caractères.

Déterminer l’ordre des BACs

En pratique, la cartographie physique est déterminée à partir de la matrice d’incidence BAC-contig. Cette matrice est globale et elle permet d’exploiter la dépendance entre les données, ce qui accroît la précision du résultat.

Notons qu’un contig est cartographié à un clone s’il contient des séquences des quatre ensembles de puits, associés au BACs, dans notre plan transversal. Les contigs associés à plusieurs BACs indiquent un chevauchement de BACs. En groupant tous les BACs reliés à un même ensemble de chevauchements.

Il faut maintenant ordonné les BACs dans l’ensemble de chevauchements.

Démarche :

1. Déterminer la matrice BAC-contig que nous noterons M

Les colonnes représentent les contigs et les rangées les BACs

M [i, j] = 1 Si le BAC indicé i contient le contig indicé j

0 Sinon

Pour le reste de la démarche, nous allons supposer que la matrice M est exempte d’erreur. Donc, tous les chevauchements sont détectés et tous les contigs sont correctement assemblés.

2. Déterminer une permutation des colonnes pour que la matrice ait la propriété des 1 consécutifs. La nouvelle matrice M’ correspond au véritable ordre physique des contigs dans le génome.

Déterminer une telle permutation prend un temps linéaire. Le problème C1P, matrice ayant la propriété des 1 consécutifs, est un problème bien connu en théorie de la complexité. Il faut faire attention de ne pas confondre le problème de C1P, qui est utilisé notamment en biologie, et le problème de décision, sous matrice C1P. Ce dernier, qui est entre autre utilisé dans la théorie des graphes, est NP-complet.

Problème de sous matrice C1P : Soit une matrice M_nxn et soit un entier k, existe-t-il une sous matrice M’_nxk t.q M’ ait la propriété des 1 consécutifs.

Problème de matrice C1P : Soit une matrice M, déterminer une permutation des colonnes de M t.q. M ait la propriété des 1 consécutifs ?

Comme nous avons supposé que la matrice est sans erreur, il est possible d’affirmer qu’il existe une permutation des colonnes (ou rangées) résultant en une matrice ayant la propriété des 1 consécutifs. En effet, la fin d’un clone (ou un contig) c₁ correspond ou précède le début d’un autre clone (ou contig) c₂.

En pratique, il est impossible de s’assurer d’une matrice sans erreur. Nous devons donc déterminer la « meilleure » permutation possible, celle minimisant le nombre d’erreur. La solution adoptée fut une version d’optimisation du problème du commis voyageur. La réduction du problème est :

Soit M =

Matrice initiale

clone - contig

Définissons le graphe valué complet G = (A, S, P) où,

L’ensemble des arêtes est S X S,

i.e. A = { (i , j ) | i et j e S}

L’ensemble des sommets est l’ensemble des clones, qui serons notés R_i (où i correspond à la rangée de la matrice initiale correspondant au clone) en plus d’un sommet u.

S = { R_i | i = 1..n } union { u }

L’utilité du sommet supplémentaire u est de marquer le début de la séquence lorsque l’algorithme aura déterminé l’ordre optimal des clones. Nous verrons que par construction, le sommet « u » a cette propriété.

Le poids de chaque arête (u , v) est le nombre de positions sur lesquels les sommets u et v diffèrent dans la matrice initiale. (Les sommets sont des clones). Donc, le poids de tous les arêtes de la forme (u, s_i) est le nombre d’occurrences de 1 dans la rangée « i ».

P(u , v) = S_i ( v[i] Å u[i] )

Il suffit maintenant de déterminer un chemin hamiltonien de coût minimal dans le graphe complet G. Cette chaîne correspond à l’ordre minimisant le nombre de « gaps » entre les rangées. Par construction, le sommet initial ou final du chemin sera le sommet u.

Partie mathématique

Modèle probabiliste

L’analyse statistique

Un plan d’expérience peut être défini comme un plan pour la collecte des données. La partie « expérience » demande une description spécifique de l’objectif du problème à résoudre. Les facteurs contrôlés, les variables dépendantes (en entrée) et aléatoires (en sortie) de l’expérimentation font également partie de la description. Les variables de sortie permettent de déterminer, par la forme de leur distribution respective, la loi ou le processus à utiliser pour l’analyse. Pour sa part, la partie « plan » décrit la façon de collecter les données (Le nombre de données, facteurs à fixer, description du modèle). Un bon prélèvement évite des biais ou bruits dans les données qui pourraient amener de fausses conclusions ou simplement masquer les conclusions intéressantes.

L’objectif de l’expérience et de minimiser la banque de séquences nécessaires pour séquencer un génome. En évitant ainsi les redondances, la vitesse de traitement sera accrue. La variable d’entrée est la librairie de clones. La variable de sortie est l’ensemble minimal, soit un sous ensemble propre de la librairie d’entrée, couvrant le génome entier.

Dans la présente expérience, les plans d’expériences, soit le plan rectangulaire et le plan transversal ont été étudiés et le plan transversal fut retenu. Le plan décrit dans l’article ne précise pas le nombre de données à collecter, cependant, lors d’une simulation sur la Drosophile, les séquences collectées en entrée couvre le génome à 360%. Parmi les facteurs fixes, dans la même simulation, la longueur des BACs sont en moyenne 150k pb. (Avec un écart type de 500 pb). De plus, nous faisons une présélection des segments conservés basées sur le chevauchement des extrémités. Il faut donc fixer la longueur approximative d’un chevauchement pour être considéré. Dans la simulation, les chevauchements moyens de 87k pb sont détectés.

La partie statistique de la recherche de M. Csurös a été omise lors de la présentation de ce dernier. Dans un article sur le sujet, on présente la démarche probabiliste du projet hybride CAPSS (soit un combiné de WGS et CAPS) et d’un projet CAPSS pure. Un projet CAPSS pure inclus uniquement des séquences CAPS. Je vais concentrer mes explications uniquement sur le modèle probabiliste de CAPSS pour un projet pur.

Résultats et modèle probabiliste

Posons q tel que 0 < q < 1, la fraction minimale d’un segment chevauchant un autre pour que le chevauchement soit considéré.

Résultat 1

Couverture

Lors du séquençage des BACs

Soient, n : nombre de fragments

l : longueur de chaque fragment

L : longueur du BAC

Alors, la couverture du BAC par les fragments, notée c, est :

Théorème 1 :

La probabilité que la position « i » dans un BAC est couvert par au moins un fragment est :

P(couverture de i) = 1-e^-c

La probabilité que la position ne soit couverte par aucun fragment est :

P(non couverture de i) = e^-c

Ce théorème pose une approximation de probabilité. A preuve repose sur une évaluation de limite où le nombre de fragments est infini.

Réellement,

P(non couverture de i) = (1-(l / L))ⁿ ≈ e^-c

Dans le cas d’un projet purement CAPSS, un projet n’ayant pas de séquence WGS, w = 0. Je vais expliciter les théorèmes du modèle probabiliste développé selon le projet pur, par soucis de simplicité.

Modèle probabiliste associé à une expérience CAPSS

Notation adoptée :

L ® Longueur d’un BAC (clone) ~ 100 à 200k pb

l ® Longueur d’un fragment de BAC ~ 500 pb

ql ® La longueur minimale d’un chevauchement pour qu’il soit détecté

N ® Nombre total de clone

F_p ® Nombre de séquences CAPS

a ® La couverture totale de la séquence de référence (par les séquences CAPS)

Donc a = (F_pl)/(NL)

Théorème 1.1

Séquençage de BACs

Considérons une séquence BAC ne chevauchant aucun autre clone.

Posons

Conclusion

(i) Le nombre prédit de contig couvrant le clone est :

(ii) Le nombre de séquences shotgun dans le contig couvrant le clone est :

(iii) La longueur d’un contig peut être définie par :

Où l_link peut être borné par :

Théorème 3

Détection du chevauchement entre 2 clones de différents groupes

Soient deux clones venant de différents groupes partageant un chevauchement.

Posons :

Alors,

(i) La probabilité qu’un îlot dans le chevauchement de j > 0 séquences shotgun soit dans la cartographie des deux clones simultanément est 1 – q(j),

Où

(ii) La probabilité que l’îlot couvrant le chevauchement soit cartographié aux deux séquences avec une probabilité de :

Processus Poisson

Essentiellement, la démonstration des deux théorèmes précédents repose sur un processus Poisson. Les taux respectifs des processus utilisés sont, a et 2a.

Par définition, un processus Poisson est un processus de dénombrement. C'est-à-dire un processus stochastique N = {N(i) , i>0 } où N(i) représente le nombre total d’évènements qui s’étant produit jusqu’à temps t. Comme le processus est stochastique, une dépendance est supposée entre les évènements.

Un processus de dénombrement {T(1), T(2), ..} est Poisson si :

® T(0) = 0

® Le processus a des augmentations indépendantes

® Le nombre d’évènements pour tout intervalle de longueur t suit une distribution Poisson de paramètre l

Dans le cas présent, les évènements sont le nombre de séquences rencontrées dans la lecture de gauche à droite de l’alignement d’une île.

Simulation de CAPS-MAP

Assemblage de séquences de Drosohila

C’est le génome de la Drosophila qui a été utilisé pour simuler et tester CAPS-MAP. La simulation était un projet hybride, soit avec des séquences WGS et CAPS, comme décrites précédemment.

Les données de la simulation :

Génome contenant 112,6 millions pb

Séparation en 2880 BACs

Longueur des BACs est en moyenne 150 000 pb

Couverture du génome par les BACs est 360 %

Séparation des BACs en 5 groupes (576 BACs par groupe)

Plan transversal de 5 paires de tableaux

Chaque tableau est de dimension 24x24

Chaque BAC est couvert à 120% par les séquences CAPS

Les séquences shotgun furent générées par le simulateur wgs-simulator. Ce dernier imite une collection de séquences shotgun. L’assemblage des séquences shotgun en contigs utilise l’outil Atlas. Bien que la méthode proposée séquence uniquement les extrémités des clones pour déterminer le sous ensemble minimal, l’article laisse entendre que les clones sont séquencés en entier pour la simulation de CAPS-MAP.

Rappelons qu’un contig est cartographié à un clone s’il contient des séquences des quatre ensembles de puits associés au clone. Les contigs qui sont associés à plusieurs BACs donnent l’indice d’un chevauchement de BACs. Les BACs sont groupés dans des bactigs, soit des ensembles disjoints de chevauchements maximaux.

Table 1 : Cette table contient la description des statistiques de la simulation par rapport à la couverture du génome par les bactigs

Pour des fins de comparaison, le réel graphe de chevauchement des BACs fut monté.

Dans la simulation, le graphe réel comprenait :

Ø 2880 arêtes

Ø 10992 sommets

Ø 66 sous graphes connexes

Par la suite, comme décrit précédemment, les BACs sont ordonnés à l’aide de la matrice BAC-contig pour chaque bactig. La détermination d’une permutation amenant la matrice à avoir la propriété des un consécutifs. Comme la matrice n’est évidemment pas parfaite, parmi les sommets (contigs), 93% étaient vrais et 22% des chevauchements n’ont pas été détectés. De plus, il y a eu 1 % de faux positifs, soient des chevauchements inexistants détectés.

Figure 5: voici un exemple de résultat de BACs ordonnés selon

1-     Loc : la location relative des BACs

2-     True : la vraie location

3-     TSP : la location obtenue après l’application de l’algorithme adapté TSP

Application de CAPSS dans un projet

PGI

Bien que le but de CAPSS soit de faire le séquençage d’un génome, il a été utilisé pour la comparaison de génomes. PGI, Pooled genomic indexing, est une méthode de cartographie entre des séquences et des génomes. Le but précis de l’expérimentation est de déterminer les parties de génomes conservées entre l’humain et autres espèces. Présentement, le projet PGI étudie le macaque.

La méthode PGI utilise les principes de CAPSS et CAPS-MAP pour la détection de chevauchements et le séquençage. Cependant, contrairement à CAPSS, la méthode PGI compare les séquences à une séquence de référence qui est déjà connue.

CAPSS

PGI

Tout d’abord, les BACs sont distribués dans un tableau. Ils sont ensuite séquencés par la méthode shotgun et l’information ainsi recueillie permet la cartographie des clones, séparés des vecteurs hôtes, dans des séquences homologues provenant d’autres organismes.

La cartographie physique, à base de BACs, utilisé par la méthode PGI est économique. En effet le coût sont environ 1% du coût du séquençage classique. Tout comme CAPSS, le nombre de librairie requis est √N, par rapport au nombre de clones.

Un tableau de clone peut être représenté comme un graphe G = (S, A). L’ensemble des arêtes correspond à l’ensemble des clones. (Cette correspondance est bijective). Les sommets représentent les pools du tableau. L’incidence des arêtes indique l’appartenance des clones à un même ensemble de pools. Tout graphe ainsi construit représente un plan de pooling. Dans le cas d’un graphe complet (N = K(K-1)/2 arêtes pour K sommets), le plan minimise le nombre de librairies shotgun à construire. Malheureusement cette minimisation est au détriment de la précision, car il y a augmentation de l’ambiguïté. L’ambiguïté existe encore une fois, à cause des homologies et chevauchements entre les clones. La recherche montre que les graphes de N arêtes et K > N^3/2/32 sommets, donc un tableau où certains puits sont laissés systématiquement vides, réduit les ambiguïtés reliées à la cartographie.

Comme, les mêmes problèmes d’ambiguïté que la recherche sur CAPSS a soulevé est à considérer dans PGI, il fallut étudier les solutions. En effet, il y a des faux positifs et des cartographies fausses ou ambiguës dans les deux méthodes. Bien que le plan transversal est efficace pour réduire les biais, dans le cas présent, la solution du tableau « spare » semble la plus appropriée. Par définition, le tableau « spare » contient au plus 3 clones dans les intersections de deux rangées et deux colonnes.

Pour déterminer les mesures du tableau, il faut d’abord borner N le nombre de clones. Soit m le premier nombre premier tel que N < m³. Le tableau sera de dimension m² x m². Ensuite, il faut placer les clones. Il y aura un maximum de m clones par colonnes et par rangées. Identifier les puits du tableau (R₍_a,
b),C_{(x, y)}), où a, b, x, y e { 0, 1,…,(m-1) }. Si, pour un puit (R₍_{a, b)},C_{(x, y)}) l’équation ax + b = y est satisfaite, alors mettre un clone dans ce puit. Notons que les équations sont dans le corps multiplicatif Z/_nZ \ {0}. Le tableau résultant est un tableau « spare ».

Figure 6 : exemple de tableau spare

Bien qu’il y ait une différence marquée dans les buts respectifs des méthodes CAPSS et PGI, les procédés sont très compatibles. Assez similaire pour être utilisé simultanément sur le même ensemble de données. Un modèle probabiliste a également été élaboré pour tester la performance de PGI.

PGI sur les génomes de la sourie et du rat

Les données :

La sourie :

207 clones

Un plan transversal dont les tableaux sont de dimension 14 x15

Un tableau spare de dimension 39 x 39

Le rat :

625 clones

Un plan transversal dont les tableaux sont de dimension 25 x25

Un tableau spare de dimension 87 x 87

Les résultats statistiques :

Sourie

Table 2: Cette table montre les résultats de la simulation d’indexation de PGI sur différentes bases de données (UG, HS, HTDB) et à l’aide de différents plans d’expériences (rectangulaire, transversale, tableau sparse)

Rat

Table 3 : Cette table montre les résultats de la simulation d’indexation de PGI sur la base de données

UG et à l’aide de différent plan d’expérience (rectangulaire, transversale, tableau sparse)

Il y a présentement un projet PGI en cours sur le macaque. On tente de déterminer les régions conservées entre l’Homme et le macaque.

Les données :

2304 clones

Un plan transversal de tableaux 48 x 48

Les résultats :

Les résultats préliminaires permettent de conclure que 81% des clones sont cartographiés au génome humain. Ces résultats sont donnés avant le séquençage complet des clones. Suite au séquençage des clones, une confirmation de 80% des clones précédents étaient bien indexés.

Voici une sortie typique des résultats de l’alignement Homme/Macaque. Il y a une distinction entre les régions à probabilité haute et basse d’alignement. La séquence de référence est le chromosome X de l’Homme.