Planning des exposés
Lundi 20/01
10h30 - 11h15
Franck Delaplace (Universite d'Evry)
TAGCC : un langage dédié à
l'annotation des séquences
11h20 - 12h05
Andrei Zinovyev (IHES)
CAI and the most biased genes
Déjeuner
14h15 - 15h00
Colin de la Higuera (Universite de St Etienne)
Automates stochastiques : utilisation et inférence
15h05 - 15h50
Francois Nicolas (LIRMM, Montpelier)
Problèmes du centre et de la médiane
pour la distance d'édition
Pause café
16h20 - 17h05
Helene Touzet (Universite de Lille)
Analyse de regions cis-regulatrices
Mardi 21/01
9h00 - 9h45
Richard Groult (Universite de Rouen)
Méthodes de détection de répétitions
en tandem avec évolution
9h50 - 10h35
Séverine Bérard (LIRMM, Montpelier)
Comparaison de minisatellites
Pause café
11h05 - 11h50
Beshad Behzadi (LIX)
An Improved Algorithm for Comparison of Minisatellites
11h55 - 12h40
Grégory Kucherov (LORIA, Nancy)
Nouvelles de mreps
Déjeuner
14h00 - 14h45
Pierre Pudlo (Universite Claude Bernard Lyon 1)
Principe de grandes deviations exactes pour des
sequences biologiques
14h50 - 15h35
Laurent Noé (LORIA, Nancy)
YASS : recherche de similarités
dans les séquences d'ADN
15h40 - 16h15
Christophe Moan (Universite de Nantes)
Recherche exhaustive de similarités
Résumés
TAGCC : un langage dédié à l'annotation des séquences
Nous présentons dans cet exposé le langage Tagcc, acronyme
de Transducteur pour l'Annotation des Génomes par des méthodes
fondées sur des Contraintes et des Coûts.
Il s'agit d'un langage spécialisé dans le domaine de la prédiction
de gènes. Tagcc permet d'implanter rapidement des programmes issus
de modèles heuristiques fondés sur le recoupement de connaissances
biologiques et statistiques. Son style est équationnel et sa sémantique
se fonde sur les relations rationnelles augmentées de contraintes
logiques.
La compilation d'un programme Tagcc conduit à la définition
d'un automate pondéré non déterministe auquel s'ajoute
des conditions. Cette implantation permet de réaliser des programmes
de prédictions très efficaces. Il offre un cadre unifié
de développement pour différentes méthodes utilisées
dans le domaine de la prédiction de gènes.
Des informations complémentaires sont accessibles sur le site http://tagcc.lami.univ-evry.fr/
Franck Delaplace (Universite d'Evry)
The notion of codon bias is one of the fundamental ones in genetic sequence
analysis of most of bacteria and some eukaryotes.
The CAI (Codon Adaptation Index) is one of the popular entropy-like measure
to get quantative characteristic of translational codon bias in a given gene.
In this work notion of "the most biased" set of genes is introduced.
We propose a simple procedure to detect a small set (about 1% of the whole
number of genes) of the most biased genes with respect to the dominating (main)
codon biaswhich is not neccessary translational.
In this case one can still use CAI to have measure of codon bias with respect
to the dominating codon bias.
Also we show that a given genome can contain several "the most biased" small
sets of genes of the same size.
Andrei Zinovyev (IHES)
Automates stochastiques : utilisation et inférence
les automates stochastiques ou probabilistes sont utilisés pour
décrire des distributions rationnelles sur Sigma*.
Ils sont utilisés dans une variété de domaines dont
en particulier la bio-informatique et la reconnaissance de la parole pour
modéliser des classes de protéines, ou des langages.
Nous explorerons les problèmes usuels : reconnaissance, équivalence
entre modèles, consistance, puis des problèmes liés aux
applications de ces automates : peut-on les apprendre, les inférer
à partir d'un ensemble de mots généré aléatoirement.
Colin de la Higuera (Universite de St Etienne)
Principe de grandes deviations exactes pour des sequences biologiques
Il s'agit d'un resultat de grandes deviations exactes sur des processus
de Markov additifs vectoriels. Ce résultat s'applique au
comptage des occurences de mots dans les sequences biologiques.
En particulier, il permet d'obtenir un resultat de grandes deviations exactes
des occurences d'un mot w' lorsqu'on conditionne le modele par la sur-representation
d'un mot w.
Pierre Pudlo (Universite Claude Bernard Lyon 1)
Analyse de regions cys-regulatrices
Une des applications privilegiees de la recherche de motifs approches est
la detection de site de fixation de facteurs de transcription dans l'ADN,
ce qui est un debut d'explication pour l'expression des genes.
Le probleme est que les programmes existants sont pratiquement inexploitables
en l'etat, a cause notamment du tres grand nombre de faux positifs.
Notre demarche consiste a chercher comment exploiter rationnellement les
sorties des programmes de prediction en presence de plusieurs genes co-exprimes.
Pour cela, nous avons sommes partis de la problematique du facteur de transcription
C-rel de la famille NF-KappaB chez l'homme.
Nous disposons d'une part de puces à ADN dans differentes conditions
experimentales (sur-expression ou pas de C-Rel), ainsi que de references de
genes connus pour etre controles par C-Rel (bibliographie).
Sur ces donnees, nous montrons que l'on peut observer des regularites au
sein des predictions, ainsi que des correlations entre entre differentes familles
de facteurs qui ne sont pas dues au hasard.
Le but de ce travail est maintenant de degager une strategie generale d'analyse
en produisant un algorithme ad hoc.
Helene Touzet (Universite de Lille)
Les minisatellites appartiennent à la classe des séquences répétées en tandem que l'on trouve dans l'ADN. Ils sont polymorphes et sont des outils utiles pour le séquençage génétique et les études médico-légales. Les minisatellites sont constitués de courtes unités répétées placées côte à côte. Ces unités légèrement différentes sont appelées variants. Les minisatellites évoluent principalement au travers de duplications en tandem et de délétions en tandem de variants. Jeffreys et al. ont mis au point une méthode pour obtenir la séquence des variants le long du minisatellite et l'ont appelée carte. Les cartes de minisatellites donnent accès au détail du processus de mutation en oeuvre sur de tels sites. L'exposé présentera un algorithme pour comparer deux cartes sous un modèle évolutif qui inclut les délétions, insertions, mutation, duplication en tandem et délétion en tandem d'un variant. Notre méthode calcule un alignement optimal en temps raisonnable ; et le score d'alignement, i.e., la somme des coûts de ses opérations élémentaires, est une distance métrique entre les cartes. La principale difficulté est que la séquence optimale des opérations dépend de l'ordre dans lequel elles sont appliquées sur la carte. Sur un jeu de 609 cartes de minisatellites de MSY1, nous avons calculé toutes les distances deux à deux et reconstruit un arbre évolutif de ces individus. MSY1 (DYF155S1) est un site hypervariable du chromosome Y. Dans notre arbre, les populations de certains haplogroupes sont monophylétiques, ce qui montre que nous pouvons déchiffrer un signal micro-évolutif en utilisant la comparaison de cartes de minisatellites.
Séverine Bérard (LIRMM, Montpelier)
Problèmes du centre et de la médiane pour la distance d'édition
La distance d'édition est une mesure couramment utilis\ée
de la différence entre deux mots. Etant donnés deux mots
x et y, on appelle distance d'édition entre
x et y (notée lev(x, y)), le nombre minimal d'opérations
d'édition (insertion, déléetion ou substitution
d'une lettre) nécessaires pour changer x en y.
Mon exposé va consister en la démonstration de la np-complétude
des deux problèmes de consensus suivants :
Francois Nicolas (LIRMM, Montpelier)
YASS : Recherche de similarites dans les sequences d'ADN
La recherche heuristique de sous sequences similaires (alignement
local) est un des outils les plus utilisés pour obtenir des information
concernant une séquence
non annotée. Pour mener à bien cette tâche, de nombreux
algorithmes utilisent une technique basé sur la recherche de petites
répétitions exactes (graines) qu'ils tentent
d'étendre en des répétitions approchées selon
des critères déterminés.
Nous proposons une autre méthode (implantée dans YASS),
qui cherche à regrouper les graines et à considerer un "hit
distribué" à la manière de FASTA tout en se voulant
aussi rapide et sensible que BLAST.
Recherche exhaustive de similarités
Contacts : {Moan, Rusu}@irin.univ-nantes.fr
Etant donnés t sequences S_1,...,S_t de longueur n sur un alphabet
A et les entiers d,k,
le "Closest Substring Problem" demande de trouver un mot M et des mots s_i
appartenant à
S_i, tous de longueur k, tels que Dh(M,s_i)<=d pour tout i, où Dh
est la distance de Hamming.
Une version plus complexe consiste à introduire un paramètre
q et à demander de trouver
tous les mots M de longueur k tels qu'au moins q des t séquences contiennent
des mots s_i
tels que Dh(M,s_i)<=d. Closest Substring, dans ces deux versions, est
un problème NP-dur[1].
Seule la deuxième version est concernée par la suite. La référence
de base est l'algorithme
de Marsan-Sagot[2], dont la complexité est O(n.N^2.V(e,k)) pour obtenir
toutes les solutions.
Cet algorithme est basé sur un parcours en parallèle d'un arbre
des suffixes et d'un arbre
des modèles. Nous améliorons ici cet algorithme en introduisant
la possibilité de descendre
de Z niveaux à la fois, au lieu d'un seul, dans l'arbre des suffixes
et dans l'arbre des
modèles. Nous discuterons de la complexité de notre algorithme,
de son comportement face à
l'algorithme de Marsan-Sagot, ainsi que des valeurs de Z pour lesquelles nous
obtenons les
meilleurs résultats.
[1] J. K. Lanctot, M. Li, B. Ma, S. Wang, L. Zhang: Distinguishing string
selection
problems, Proceedings of 10th SODA (1999), 633-642.
[2] L. Marsan, M.F. Sagot: Extracting structured motifs using a suffix
tree-algorithms
and application to promoter consensus identification (RECOMB 2000).
Christophe Moan (Universite de Nantes)