Institut de Mathématiques de Luminy

THÈSES 2004-2005


Dates soutenances Noms et titres équipes Photos
27 mai 2005

Nicolas BEDARIDE
Étude du billard dans un polyŤdre.

DAC
7 décembre 2004 Tristan COLOMBO
Algorithmes pour la recherche de classes de gènes en relations fonctionnelles par analyse de proximités et de similarités de séquences.
MMG


Nicolas BEDARIDE
(thème DAC)

Titre : Étude du billard dans un polyèdre.

Directeur(s) de thèse : Serge TROUBETZKOY

Rapporteurs : Jörg Schmeling, Anton Zorich.

Jury : Pierre Arnoux, Jean Berstel, Valérie Berthé, Serge Troubetzkoy, Jörg
Schmeling.

Date : 27 mai 2005

Université d'inscription : Aix-Marseille II

Résumé : Dans cette thèse, on s'intéresse au billard dans un polyèdre. On étudie cette application en codant les orbites sur un alphabet fini. On étudie alors deux problèmes : la complexité des mots infinis obtenus, et l'existence de trajectoires périodiques. On montre que la complexité est reliée à la notion de diagonale généralisée : une diagonale généralisée est une trajectoire de billard, qui part d'une arête et qui arrive à une arête. On obtient alors, au premier chapitre, une nouvelle preuve de calcul de la complexité d'une rotation dr tore T2, totalement irrationnelle. Cette preuve permet de plus, d'obtenir une estimation de la complexité directionnelle du billard dans certains prismes droits. Au deuxième chapitre, on obtient, grâce aux diagonales généralisées, une estimation de la complexité globale du billard cubique. On donne alors au chapitre trois une estimation valable dans n'importe quel polyhèdre convexe. On montre en fait que le billard est d'entropie topologique nulle. Le chapitre quatre traite alors du problème des orbites périodiques. On donne une condition suffisante pour qu'un mot soit stable. On montre de plus l'existence d'une trajectoire périodique dans le tétraèdre régulier. Pour finir, on s'intéresse dans le chapitre cinq à une sous classe d'échange de rectangles. On montre que ces applications sont ergodiques et de complexité quadratique. Ces applications sont reliées au billard puisque, à direction fixée, l'application de premier retour est une application affine par morceaux.

Mots-clés : théorie ergodique, billard, complexité, échange de polygones.

Title : Polyhedral billiard.

Abstract : In this work, we study polyhedral billiard. We code the orbit of a point with a letter by face. Then we study two sorts of problems: the complexity function of the billiard words, and the existence of periodic orbits. We show that the complexity function is related to the notion of generalized diagonal: a generalized diagonal is a billiard trajectory between two edges of the polyhedron. First we show a new proof for the computation of the complexity of a rotation of the torus T2 . This proof allows us to obtain estimates for the complexity in some right prisms. Then we search for bounds of the global complexity in the case of the cube. Then we prove that the billiard in any convex polyhedron is a zero topological entropy. Then we study the periodic orbits. We find a sufficient condition for the existence of stable periodic words, and we obtain periodic trajectories of length four in a tetrahedron. Then we obtain ergodicity and equivalent for the complexity of a subclass of rectangle exchanges. This is related to the billiard map, since they represent the first return map to a transverse set.

Keywords :
ergodic theory, billiard, complexity, polygonal exchanges.

Fichier / File

(1,26 M)


Page personnelle (homepage) : http://iml.univ-mrs.fr/bedaride/



Tristan COLOMBO
(thème MMG)

Titre : Algorithmes pour la recherche de classes de gènes en relations fonctionnelles par analyse de proximités et de similarités de séquences.

Directeur(s) de thèse : Alain GUENOCHE, Yves QUENTIN

Rapporteurs : Guy Perrière, Thomas Schiex.

Jury : François Denis, Guy Perrière, Thomas Schiex.

Date : 7 décembre 2004

Université d'inscription : Aix-Marseille II (discipline : informatique)

Résumé : Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L’analyse bioinformatique du répertoire de ces systèmes comprend l’identification des partenaires, l’assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l’identification du substrat transporté. Cette thèse propose des outils permettant l’étude de ces problèmes par l’utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s’ils ont été conservés au cours de l’évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction.

Trois études ont été menées sur le répertoire des transporteurs ABC :

– L’exploration du voisinage chromosomique. D’après l’hypothèse selon laquelle plus les gènes conservés dans le voisinage d’un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d’identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes.

– La classification. Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu’ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d’homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat.

– La reconstitution des systèmes incomplets. Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n’est pas respectée, on utilise une stratégie développée à partir d’une méthode d’analyse de graphes pour assembler les domaines et prédire des systèmes actifs.

Ces méthodes, en complément de l’identification des partenaires et de l’assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d’autres systèmes biologiques.

Mots-clés : bioinformatique, transporteur ABC, partitionnement de graphe, synténie, satisfaction de contraintes.

Title : Algorithms for the research of functionnaly related classes of genes by the analysis of proximities and of the similarities of sequences.

Abstract : Our study focuses on ABC transporters in complete bacterial genomes. The bioinformatic analysis of these systems includes the identification of partners, the assembly, the reconstruction of incomplete systems, the classification in sub-families, and the identification of the carried substrate. This thesis proposes tools allowing the study of these problems by using computational methods. The biological hypotheses employed are : (i) neighbor genes on the chromosome can be implicated in a same metabolic process if they are conserved during evolution, and (ii) genes with similarities of sequences can allow the synthesis of proteins of the same function.

Three studies have been made on ABC transporters :

– The exploration of chromosomical neighborhood. According to the hypothesis which says that the closer the genes conserved in the neighborhood of a transporter are, the stronger their functionnal link with the transporter is, we try to identify the carried substrate or associations between genes. This problem is treated by a resolution method stemming from the constraints satisfaction problems.

– Classification. ABC transporters are classified into big categories in function of the molecules they carry (sugars, ...). For each domain, by representing the homological relations by a graph, the research for the high density areas allow us to determine sub-classes of substrate.

– The reconstitution of incomplete systems. ABC transporters are assembled using the chromosomical proximity of the genes coding for the domains, and the compatibility of the sub-families of the domains. When the proximity is not respected, we use a strategy developped from a method of graph analysis to assemble the domains and predict the active systems.

These methods, complementary to the identification of partners and of the assembly process, allow a functional study of the ABC transporters. They could be applied to other biological systems. .

Keywords :
bioinformatics, ABC transporter, graph partitionning, syntenie, constraints satisfaction.

Fichier / File

(1,91 M)

Page personnelle (homepage) : http://tristan.colombo.free.fr/


Last update : october 19, 2006, EL.