Page suivante: 4 Analyse structurale Niveau précédent: 3 Cartographie Page précédente: 3.2.1 Cartes de restriction par

3.3 Cartographie basée sur les fragments chevauchants

La stratégie des fragments chevauchants consiste dans un premier temps à découper l'ADN du génome en longs fragments (quelques centaines de milliers de bases) présentant des régions de chevauchement. Il s'agit ensuite de replacer ces fragments les uns par rapport aux autres. La détection des fragments chevauchants et la détermination de leurs positions relatives peuvent, par exemple, être effectuées à l'aide de sondes. Une sonde est une séquence d'ADN assez courte permettant d'identifier une région particulière du génome. On dit alors qu'elle s' hybride à cette région. Deux fragments s'hybridant à une même sonde sont probablement chevauchants (Figure 6).

 
Figure 6: Représentation schématique de plusieurs hybridations. Le génome est représenté par une ligne noire horizontale. Les fragments chevauchants sont représentés en dessous par des lignes horizontales plus courtes. Les sondes sont représentées par les parallépipèdes en pointillés et indiquent les régions explorées par les sondes. Les sondes r et s sont reliées par un fragment et doivent donc être considérées comme étant voisines sur le génome. 

Dans une version simplifiée, sans tenir compte des incertitudes, le problème peut se formuler de la façon suivante : étant donné un ensemble C de fragments et deux sous-ensembles disjoints de représentant respectivement les paires de fragments qui doivent se recouvrir et qui ne doivent pas se recouvrir, trouver un ordre des fragments satisfaisant ces contraintes de recouvrement. Le problème de décision associé est NP-complet [ Gol 93] et s'interprète naturellement en terme de graphe d'intervalles. Une modélisation plus réaliste du problème consisterait, à partir des probabilités de recouvrement de chaque paire, à déterminer les ordres de vraisemblance maximum.

Dans [ Cla 94], le problème est abordé via le langage de programmation par contraintes ElipSys, une version parallélisable du langage de programmation par contrainte Eclipse, lui-même issu de Chip, et s'appuyant sur des algorithmes traditionnels du monde CSP. Les données sont issues d'hybridations des fragments avec un ensemble de sondes. Les auteurs procèdent en deux étapes :

1. on cherche d'abord à ordonner les positions d'hybridation des sondes. La proximité de deux sondes A et B est plus ou moins vraisemblable en fonction :
   • du nombre de fragments avec lesquels les deux sondes se sont hybridées ;
   • du nombre de fragments avec lesquels seulement l'une des 2 sondes s'est hybridée (plus est faible vis-à-vis de , plus il est vraisemblable que les deux sondes soient proches) ;
2. on choisit pour chaque fragment une position qui maximise le nombre d'hybridations.

La modélisation choisie pour représenter ce problème dans le cadre CSP est la suivante :

variables :

à chaque sonde est associée une variable qui représente sa position ; soit N le nombre de sondes ou variables ;

valeurs :

les valeurs que peut prendre une variable, comprises entre 1 et N, sont les positions possibles dans l'ordre, de la sonde associée à la variable ;

contraintes :

elles sont codées comme des inégalités et des différences arithmétiques, et sont de trois types :

1. une première série de contraintes interdisent à deux sondes d'avoir la même position, limitant l'espace de recherche à des permutations ;
2. des contraintes de voisinage assurent que deux sondes dont la proximité est suffisamment vraisemblable (ou invraisemblable) seront l'une à coté de l'autre (ou non) ;
3. des contraintes d'ordre partiel entre sondes, provenant de sources différentes (carte partielle de fragments chevauchants déjà établie, carte génétique...).

L'effet positif de l'utilisation des contraintes pour réduire l'espace de recherche dans la phase de résolution est mis en évidence.

Un problème majeur dans l'ordonnancement des fragments chevauchants est le << bruit >> expérimental. Celui-ci a plusieurs sources :

1. les faux positifs et les faux négatifs résultant du seuillage naïf des vraisemblances de contiguïté ;
2. l'apparition de << chimères >> lors du processus expérimental, i.e., de fragments ayant subi des remaniements au niveau moléculaire (deux fragments peuvent s'unir pour en former un nouveau, des insertions ou des suppressions de portions peuvent avoir lieu à l'intérieur d'un fragment) ;
3. les sondes peuvent s'hybrider à plusieurs endroits du fait des répétitions dans la séquence d'ADN.

Page suivante: 4 Analyse structurale Niveau précédent: 3 Cartographie Page précédente: 3.2.1 Cartes de restriction par