Une des énigmes majeures de l'évolution des génomes reste le rôle des
phénomènes de duplication de l'ADN. Les événements de duplication sont
à l'origine de l'accroissement de la taille des génomes, des familles
de gènes et des locus de répétitions en tandem (i.e., adjacentes) les
plus variables de tout le génome humain. Malgré cela, le rôle et
caractéristiques évolutifs, les raisons de leur existence et les
mécanismes qui contrôlent leur développement sont encore peu connus.
En outre, on sait que des répétitions en tandem influent sur le
contrôle de l'expression de gènes ou le développement de maladies
telles que la chorée de Huntington ou le diabète de type I.
Ce projet vise à avancer dans la compréhension de l'évolution de
diverses structures répétées. Il exige d'abord de se doter d'outils
informatiques et de modèles performants pour :
localiser ces structures répétées tant en tandem que distantes,
comparer différentes répétitions ou allèles issus d'un site de répétition,
et reconstruire leur histoire évolutive en tenant compte des événements de duplication.
Nous envisageons d'améliorer les algorithmes existants pour prendre en
compte toute la complexité évolutive de ces structures. L'autre
objectif est d'appliquer ces outils aux données biologiques pour
étudier diverses structures répétées et plusieurs aspects évolutifs.
Tout d'abord, recenser les répétitions distantes à l'intérieur des
génomes procaryotes, puis eucaryotes, pour découvrir des régions
conservées ayant un rôle régulateur ou des familles de gènes.
Ensuite, caractériser les microsatellites de génomes eucaryotes par
une approche de génomique comparative pour élucider les forces qui
contrôlent leur existence. Retracer l'histoire évolutive de familles
de gènes importantes du point de vue fonctionnel, comme les quelques
200 protéines de la plus grande famille de l'arabette. Enfin, comparer
des allèles de sites de répétition variables pour deux types
d'applications, soit pour examiner un rôle fonctionnel, soit pour
inférer des relations évolutives entre individus, populations ou
souches bactériennes. Ces applications serviront aussi à valider les
algorithmes conçus préalablement.
Laboratoires et participants
Méthodes et Algorithmes pour la Bioinformatique, LIRMM (Laboratoire d'Informatique de Robotique de Microélectronique de Montpellier), Montpellier
Sèverine Bérard, maintenant Maitre de Conférences, Univ. Montpellier II, Severine.Berard@cirad.fr,
Sequioa, Laboratoire d'Informatique Fondamentale de Lille (L.I.F.L.), Lille
Anciennement Projet Adage, Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Nancy
Laboratory for Biocomputing and Informatics, Boston University, Boston, USA.
Gary Benson, Professeur à Boston University, gbenson@bu.edu,
Alfredo Rodriguez, Ingénieur,
Yevgeniy Gelfand, Ingénieur.
Avancées
En 2004 et 2005
STAR : logiciel de détection de répétitions en tandem
approximatives RTA, publication [10] et mise
en accès sur internet à STAR.
Publication d'un panorama des problèmes algorithmiques liés à
l'évolution des répétitions en tandem [20].
Début de la thèse de Sébastien Leclercq sur la modélisation des microsatellites dans les génomes.
Recherche de répétitions et de similarités par des méthodes de filtration :
YASS : implémente un algorithme de recherche de similarités
utilisant des graines espacées,
[17, 18]
Études théoriques de la conception de graines : les problèmes
de conception de graines, qui sont résolus en routine dans des
logiciels tels que YASS de l'INRIA ou PatternHunter
(développé par l'équipe de Ming Li et maintenant commercialisé par
Bioinformatics
Solutions Inc.), ne peuvent être résolus en temps polynomial.
Dans un travail récent, nous montrons qu'ils sont difficiles à
résoudre optimalement et à approximer. Ceci implique que les
méthodes exponentielles proposées jusqu'alors ont des complexités
quasi-optimales [15].
Nouvelle méthode de recherche locale, dédiée à l'inférence
d'arbres de duplication, optimisant les critères du maximum de
parcimonie et du minimum évolution. Cette méthode a été téstée sur
des jeux de données simulés, ainsi que sur les séquences répétées
des gènes à doigts de zinc humains. Nous avons observé que les
résulats de notre méthode étaient meilleurs que ceux obtenus par les
méthodes concurrentes [5, 6].
Publication d'une revue des méthodes d'inférence d'arbre de
duplications [11].
WebMAM : développement d'une interface web pour un logiciel de manipulation,
d'analyse et d'annotation d'alignement multiple MAM [3].
Filtration à l'aide de graines espacées multiples, ou comment
augmenter l'efficacité de la filtration en utilisant une famille de
graines espacées, plutôt qu'une seule. Algorithme de design de graines
multiples. [12]
En 2006 et 2007
Etude de la formation de la famille de protéines PPR
chez la plante modèle Arabidopsis thaliana
Analysis of the formation of a large, lineage specific
protein family, the PPR protein family, in the model
plant Arabidopsis thaliana
Collaboration: IBP (Orsay) URGV (Evry) - LIRMM; [19]
New version of the program MS_Align
Nouvelle version du logiciel MS_Align (pour accèder au programme cliquer sur son nom)
[4].
Analyse des allèles du minisatellite humain MSY1
Analysis of the haplotypes of the human hypervariable minisatellite MSY1.
Collaboration I.G.H. - LIRMM
Détails / Details: http://www.lirmm.fr/~rivals/RESEARCH/REPEVOL/MSY1/ ; [4].
Analyse conjointe à l'échelle de l'espèce de souris
Mus musculus de 4 minisatellites polymorphes
Species wide analysis of 4 polymorphic murine minisatellites.
Collaboration I.S.E.M. - LIRMM
Détails / Details: http://www.lirmm.fr/~rivals/RESEARCH/REPEVOL/MMS/ ; [9].
Comparaison de 5 logiciels de détection des microsatellites
dans les génomes
Comparison of 5 programs for microsatellites detection in complete
genomes
Collaboration: CEFE (Montpellier) - LIRMM
[21].
Etude de la complexité de la comparaison cyclique de séquences
Complexity study of cyclic comparison of sequences
[16]
Définition et étude d'un nouveau type de graines espacées,
appelé graines sous-ensemble
Proposition d'un cadre général pour l'étude de la sensibilité de
tous types de graines espacées et de modèles probabilistes
d'alignement
Definition and study of a new type of spaced seeds called subset seeds
Proposal of a unifying framework for determining seed sensitivity
Collaboration: IMBP (Moscaw) - LORIA/LIFL; [13]
Méthode de prédiction de recombinaison in minisatellite maps.
A method to detect recombination in minisatellite data
Collaboration: Covenant University (Nigeria) - LIRMM
[2, 1]
Méthodes d'inférence d'histoires de duplication de gènes prenant
en compte les inversions de segments chromosomiques.
Methods to
infer duplication history of a tandemly repeated genes considering
chromosomal segment inversions
Collaboration: Univ. de Montréal - LIRMM; [7, 8]
Implantation de l'automate d'évaluation des graines espacées sous-ensemble.
Study of the automaton of subset seeds.
[14]
Objectifs du projet pour les trois années de sa durée :
2004:
article sur la méthode de détection de répétitions en tandem approximative STAR
état de l'art sur les aspects algorithmiques de l'évolution des répétitions en tandem
première modélisation par des modèles markoviens de la population de microsatellites
article sur la méthode de détection de répétitions distantes YASS
2005:
méthode d'alignement multiple de cartes de minisatellites
étude de l'évolution de la plus grande famille de gènes répétées en tandem de l'arabette
lancement d'une thèse sur la modélisation des populations de microsatellites
détection et comparaison multiples des populations de microsatellites dans les principaux génomes eucaryotes modèles
article sur la méthode de détection de clusters de répétitions
inventaire et analyse des clusters de répétitions dans les génomes procaryotes
2006:
algorithmes de reconstruction de duplication en tandem sans contraintes de positions
mesures de distance entre arbres phylogénétiques et arbres de duplications
analyse du minisatellite INS et recherche d'événements mutationels qui discriminent les malades des contrôles
adaptation des méthodes de comparaison de minisatellites et du modèle évolutif aux cas bactériens
Ezekiel Adebiyi and Eric Rivals.
Detection of Recombination in Variable Number Tandem Repeat
Sequences.
South African Computer Journal, December 2007.
in press.
Ezekiel Adebiyi and Eric Rivals.
On the Detection of Recombination in Minisatellite Data.
In Scott Hazelhurst and Michèle Ramsay, editors, Proc. of the
first Southern African Bioinformatics Workshop, pages 25–32, University of
the Witwatersrand, Johannesburg, South Africa, January 2007.
C. Alkan, E. Tüzün, J. Buard, F. Lethiec, E.E. Eichler, J.A. Bailey, and
S.C. Sahinalp.
Manipulating Multiple Sequence Alignments via MaM and WebMaM.
Nucleic Acids Research, 33(suppl-2):W295–298, July 2005.
(Web Server issue).
Sèverine Bérard, François Nicolas, Jérôme Buard, Olivier Gascuel,
and Eric Rivals.
A fast and specific alignment method for minisatellite maps.
Evolutionary Bioinformatics, 2:327–344, 2006.
D. Bertrand and O. Gascuel.
Topological rearrangements and local search method for tandem
duplication trees.
In Lecture Notes in Computer Science. Proceeding of WABI 2004,
pages 374–387, 2004.
D. Bertrand and O. Gascuel.
Topological rearrangements and local search method for tandem
duplication trees.
Transactions on Computational Biology and Bioinformatics,
2(1):15–28, 2005.
Denis Bertrand, Mathieu Lajoie, Nadia El-Mabrouk, and Olivier Gascuel.
Evolution of tandemly repeated sequences through duplication and
inversion.
In Guillaume Bourque and Nadia El-Mabrouk, editors, Comparative
Genomics, volume 4205 of Lecture Notes in Computer Science, pages
129–140. Springer, 2006.
Denis Bertrand, Mathieu Lajoie, Nadia El-Mabrouk, and Olivier Gascuel.
Duplication and Inversion History of a Tandemly Repeated Genes
Family.
J. of Computational Biology, 14(4):462–478, 2007.
François Bonhomme, Eric Rivals, Annie Orth, Gemma R. Grant, Alec J.
Jeffreys, and Philippe R.J. Bois.
Species-wide distribution of highly polymorphic minisatellite
markers suggests past and present genetic exchanges among House Mouse
subspecies.
Genome Biology, 8:R80, 2007.
O. Gascuel, D. Bertrand, and O. Elemento.
Reconstructing the duplication history of tandemly repeated
sequences.
In O. Gascuel, editor, Mathematics of Evolution and Phylogeny,
pages 205–235. Oxford Univ. Press, 2005.
G. Kucherov, L. Noé, and M. Roytberg.
Multiseed Lossless Filtration.
IEEE/ACM Transactions on Computational Biology and
Bioinformatics, 2(1):51–61, Jan-Mar 2005.
G. Kucherov, L. Noé, and M. Roytberg.
A Unifying Framework for Seed Sensitivity and its Application to
Subset Seeds.
Journal of Bioinformatics and Computational Biology,
4(2):553–570, April 2006.
Gregory Kucherov, Laurent Noé, and Mikhail Roytberg.
Subset seed automaton.
In Jan Holub and Jan Zdárek, editors, Conference on Implementation and Application of Automata (CIAA'07), pages
151–160, Czech Technical University in Prague, Czech Republic, 2007.
François Nicolas and Eric Rivals.
Hardness of Optimal Spaced Seed Design.
In A. Apostolico, M. Crochemore, and K. Park, editors, Proc. of
the 16th Annual Symposium on Combinatorial Pattern Matching (CPM), volume
3537 of Lecture Notes in Computer Science, pages 144–155. Springer
Verlag, 2005.
E. Rivals, C. Bruyère, C. Toffano-Nioche, and A. Lecharny.
Formation of the Arabidopsis Pentatricopeptide Repeat Family.
Plant Physiology, 141:825–839, 2006.
Eric Rivals.
A Survey on Algorithmic Aspects of Tandem Repeats Evolution.
International J. of Foundations of Computer Science,
15(2):225–257, 2004.
Special Issue "Combinatorics on Words with Applications".
Sébastien Leclercq and Eric Rivals and Philippe Jarne.
Detecting microsatellites within genomes: significant variation among
algorithms.
BMC Bioinformatics, 8:125, 2007.
http://www.biomedcentral.com/1471-2105/8/125/abstract.
REPEVOL Project