Compartimentation chromosomique - DSIMB - Inserm

"Compartimentation chromosomique." S. Hazout1, A. de Brevern1, F. Loirat1,
A. Badel-Chagnon1, C. André2 et P. Vincens1,3
1 Equipe de Bioinformatique Moléculaire, INSERM U155, Université Paris 7
2 Département de Biomathématiques, CHU La Pitie-Salpétriere, Paris.
3 Département de Biologie, ENS Ulm, 36 rue d'Ulm, Paris. Attention : Les figures ne sont pas incluses dans ce fichier. 1. INTRODUCTION
Les projets "génome" se développant par l'apparition continuelle de
nouvelles séquences nucléiques, il devient nécessaire de développer des
outils adaptés à l'analyse à grande échelle de ces séquences de grande
taille. La compartimentation chromosomique d'un génome se situe à deux
niveaux : le premier que l'on peut appeler compartimentation partielle, qui
consiste à rechercher les zones de forte identité (c'est à dire ayant en
moyenne au moins 65% d'identité de bases), le second dénomme
compartimentation globale, visant à coder la totalité des séquences
chromosomiques analysées en termes de composition (par exemple, en
dinucléotides) afin de rechercher les chaînes de codes proches, et donc les
régions de similitude compositionnelle. Ces deux visions sont
complémentaires : la première permet de localiser les traces les mieux
conservées des transferts de matériels génétiques intra ou intergénomiques,
et, la seconde permet d'avoir une vision globale de l'organisation
chromosomique d'un génome sous forme d'une succession de fragments codes
(que l'on peut représenter sous la forme d'un code-barre), et ainsi de
repérer les zones de similitude de séquence. L'objectif de la
compartimentation chromosomique est double : (i) obtenir une représentation
plus synthétique d'un génome sous forme de régions de forte identité ou de
forte similitude, qui puisse être plus facilement traitable ultérieurement,
et (ii) pouvoir intégrer ces deux visions dans un modèle d'évolution du
génome étudié.
Le but de l'étude est de présenter deux méthodes, que nous avons
élaborées, qui répondent respectivement aux problèmes de compartimentations
partielles ou globales :
*ASSIRC pour Accelared Search for SImilarity Regions in Chromosome,
approche basée sur une recherche des régions de forte identité à partir de
motifs répétés (appelés "graines") obtenus préalablement en utilisant les
"fonctions de hachage",
*HXM pour Hybrid Chromosome Model, approche reposant sur un
apprentissage non supervisé et auto-organisé des fragments de séquences.
Nous avons appliqué ces techniques à l'étude des régions
subtélomeriques des 16 chromosomes de la levure Saccharomyces cerevisae,
car celles-ci présentent des zones de forte similitude.
2. COMPARTIMENTATIONPARTIELLE.
ASSIRC: un logiciel d'extraction de séquences de forte identité au sein
d'un génome.
Le but de la compartimention partielle est d'extraire les régions de
forte identité de bases entre séquences chromosomiques d'un même génome. La
méthode ASSIRC que nous avons mise au point est détaillée dans l'article de
Bioinformatics (Vincens et al., 1998). Aussi nous ne rappellerons que les
grandes lignes de l'approche.
Les étapes de l'analyse sont les suivantes : (i) définir des "graines",
c'est à dire des motifs répétés de petite taille (entre 8 et 11 bases)
présents dans l'ensemble des séquences étudiées, par une fonction de
hachage ("hash-functions" ; voir Sedgewick, 1989), permettant la
transformation des chaînes de taille fixée en un nombre, et donc facilitant
la recherche des duplicats exacts, (ii) construire les "marches 2D"
(appelée "Randow Walk" ; Gates, 1985) des régions contenant une des graines
sélectionnées par la première procédure, puis définir au mieux les limites
de la région de forte identité de bases à partir de ces marches, et (iii)
vérifier la pertinence de la sélection en réalisant un alignement entre les
séquences par le logiciel BESTFIT provenant du pacquage UWGCG (Devereux et
al., 1984).
a. Codage de motifs grâce aux fonctions de hachage
Une suite u de k bases {ui} peut être codée bijectivement par un nombre
X(u) compris entre 1 et 4k au moyen d'une fonction de hachage par la
formule:
X(u) = (i ai 4k-i
ou ai prend la valeur 0, 1, 2 ou 3 si la base ui est l'une des 4 bases
(A, C, G ou T).
Apres avoir transforme les séquences étudiées en des suites de nombres,
il est aisé de localiser les motifs dupliques de taille k. Chaque doublet
de motifs dupliques constitue une "graine" pour la recherche des régions de
forte identité.
b. Représentation d'une séquence par une "marche 2D" et délimitation
des régions candidates.
Pour caractériser les régions candidates, c'est a dire susceptibles de
correspondre à un doublet de régions de forte identité de bases, il faut
définir au mieux les extensions maximales des séquences à partir de la
graine. Pour répondre a cet objectif, on a utilise le principe de la
"marche aléatoire" qui consiste a transformer une chaîne de caractères par
une trajectoire. A chaque base, on associe un vecteur de déplacement; ainsi
on a affecte aux bases A, T. C et G les vecteurs respectifs VA (+2, +3), VT
(+2, -3), VC ( 3, -2) et VG (-3, +2) (les valeurs 2 et 3 ont été choisies
pour tenir compte des fréquences des bases dans le génome de la levure, 30%
pour T et A, 20% pour G et C). La trajectoire est construite en sommant le
vecteur de déplacement associée a la mième base de la sequence au point
précédent obtenu a partir des (m -1) bases précédentes.
Les marches aléatoires autour d'une graine commune (trajectoires
identiques places à l'origine du repère) sont construites. De ces
trajectoires, on calcule la distance d(m) entre les points associés aux
même hases situées à droite ou à gauche des extrémités de la graine le long
des deux séquences. Les limites à droite et à gauche des régions candidates
sont déterminées en ne conservant que les bases ayant une distance d(m)
inférieure a une valeur seuil fixée par l'utilisateur.
c. Détermination des zones de forte identité de bases.
La derrière étape consiste à sélectionner parmi les régions candidates
celles qui, après alignement par le logiciel BESTF1T, présente une taille
d'homologie supérieure à une valeur fixée par l'utilisateur (par exemple,
100 bases). La méthode ASSIRC fournit une liste des régions de forte
identité (les pourcentages d'identité sont en général supérieurs a 65%) et
donc permet de définir une compartimentation partielle d'un génome.
3. COMPARTIMENTATION GLOBALE.
"Modèle du Chromosome Hybride" ("Hybrid Chromosome Model " H?M)
L'objectif de la compartimentation globale est d'abord définir un
codage qui permettra de labelliser tous les fragments de taille fixée
extraits des séquences chromosomiques, puis d'extraire les chaînes exactes
(i. e. suites de caractères identiques) qui seraient susceptibles de
correspondre a des régions de forte similitude dans l'ensemble des
séquences codées. Pour répondre a cet objectif, il est nécessaire
d'associer a chaque fragment de L bases un vecteur observation; nous avons
choisi de prendre le vecteur des Z-scores calcules {Zif} a partir des
effectifs des dinucléotides dans le fragment,
Zif = (Nif - Nib)/ ( Nib
ou Nif et Nib désignent respectivement l'effectif du ième dinucléotide
(i = 1, ..., 16) dans le fragment et celui attendu en moyenne (i.e. Nib =
L.fib, avec fib, la fréquence du dinucléotide dans l'ensemble du génome).
Les séquences étudiées sont découpées en fragments de longueur L avec un
recouvrement de séquences de r bases, et sont donc représentées par une
suite de vecteurs observations.
Pour répondre au problème, une stratégie simple consiste à réaliser une
classification en g groupes par une méthode de type "k-moyennes" ("k-
means", Hartigan et Wong, 1979) de l'ensemble des vecteurs observations, et
à recoder les fragments en leur attribuant le label du groupe auquel ils
appartiennent. Chaque sequence serait alors définie par une suite de
labels. Une étape supplémentaire serait de rechercher les chaînes de labels
identiques pour localiser les régions de forte similitude au sein des
séquences étudiées.
Une autre stratégie consiste à apprendre directement les suites de
vecteurs observations dans les séquences étudiées ; l'approche qui répond à
cette optique, repose sur la construction d'un chromosome hybride qui est
censé "assimiler au mieux" l'ensemble des vecteurs observations (i.e. les
fragments de L bases) en prenant en compte la séquentialité de ces vecteurs
observés dans les séquences, d'où le nom de "Hybrid Chromosome Model" (voir
figure 1). Le chromosome hybride correspond a une suite de N vecteurs-
observations qui se pressentent sous la forme d'une matrice 16xN. La
procédure d'apprentissage est semblable à celle utilisée dans les méthodes
"Self-Organized Maps" (SOM) ou cartes de Kohonen (1989).
Le principe est simple: (i) on initialise la matrice par N vecteurs
observations tires au sort ou sélectionnes dans la base de données, (ii) on
examine tous les n-uplets de fragments présents dans la base (le n-uplet
correspond a n vecteurs observes le long d'une sequence chromosomique);
pour chaque n-uplet (désigne par l'indice k et défini par le vecteur W(k)),
on recherche le plus proche (selon une distance euclidienne entre vecteurs
observations) parmi les n-uplets consécutifs dans le chromosome hybride. Si
l'on désigne par Vold les n vecteurs observateurs correspond