Skip to main content.

    Master Informatique - Spécialité Science et Ingéniérie Informatique


Parcours Algorithmique, Bio-informatique et Combinatoire




        Navigation:Parcours Logiciel et Réseaux - IngéniérieParcours Logiciel et Réseaux - ScienceParcours Algo, Bio-info et Combinatoire

Objectifs

Le parcours Algorithmique, Bio-informatique et Combinatoire est un parcours "science" préparant à une poursuite en doctorat. Le but de ce parcours est de fournir aux étudiants les bases de la recherche actuelle en informatique théorique, en particulier dans les domaines de l'algorithmique du texte et de ses applications, ainsi qu'en combinatoire. Les enseignements sont dispensés par les enseignants-chercheurs et chercheurs du laboratoire d'informatique Gaspard-Monge appartenant aux équipes algorithmique et combinatoire algébrique.

Organisation

Le parcours débute au second semestre du master 1 et se poursuit pendant les deux semestres du master 2

Enseignements de Master 1:

Master 1 / Second Semestre


Algorithmique du texte

Ce cours présente les notions fondamentales en algorithmique des mots. Il débute par l'étude de combinatoire des mots: préfixes, suffixes, facteurs, sous-mots, distances, conjugaison, mot primitif. On présentera ensuite les algorihmes classiques de recherche de motifs (Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick), puis des algorithmes de calcul de plus long sous-mot commun ou de recherche approchée.


Informatique génomique


Les objectifs de ce cours sont de comprendre les principaux concepts et problèmes du domaine de l'algorithmique appliqués à la biologie, d'évaluer l'importance de ces concepts à travers un ensemble d'applications pratiques, de discerner quels sont les problèmes ayant des solutions algorithmiques efficaces et ceux qui ne peuvent pas en avoir; pour certains problèmes que l'on ne peut pas résoudre efficacement, on montrera comment les heuristiques tendent à donner des solutions, souvent de façon rapide mais approchée.

On s'intéressera en particulier dans ce cours aux problèmes d'alignement de séquence, de prédiction de structures d'ARN, de phylogénie et de réarrangements génomiques. Pour chacun de ces points, le cours présentera le problème biologique et son importance, la formulation du problème d'un point de vue algorithmique, les solutions existantes et les applications tant biologiques qu'algorithmiques mises en place.

Aucune connaissance en biologie n'est, a priori, requise pour suivre ce cours. Son contenu est hautement algorithmique orienté vers des problèmes réels de biologie.



Combinatoire


Présentation et dénombrement des objets combinatoires les plus courants : permutations , mots, combinaisons, arrangements, sous-ensembles, partitions et compositions d'entiers, partitions d'ensembles, divers types d'arbres. Nombres combinatoires classiques : coefficients binomiaux, nombres de Stirling, d'Euler, de Bell, de Catalan.
La présentation utilisera autant que possible les techniques de la combinatoire algébrique, qui seront introduites à partir d'un exemple : l'analyse des éxécutions du tri par bulles. Celle-ci conduit à la notion de standardisé d'un mot sur un alphabet ordonné, et à l'étude du langage des mots ayant un standardisé donné. Les séries formelles associées à ces langages forment une algèbre,dans laquelle on trouve des relèvements non commutatifs de nombreuses identités classiques. On expliquera ainsi le théorème d'André sur les nombres tangents et sécants, et l'interprétation combinatoire des polynômes eulériens.

    Enseignements de Master 2:



La seconde année de Master est divisée en deux semestres, le premier étant commun à tous les étudiants du parcours, le second étant spécialisé, soit en Bio-informatique et Automates, soit en Combinatoire

Master 2 / Premier Semestre

Master 2 / Second Semestre - Bio-informatique et Automates

Master 2 / Second Semestre - Combinatoire



Algorithmique et automates

L'objectif du cours est de présenter des algorithmes sur les automates finis et les structures pour index. Ce cours est divisé en deux parties de même volume.

La première partie du cours concerne l'utilisation des automates dans la recherche de motifs. Après avoir rappelé les notions élémentaires de combinatoire des mots (bords, périodes), on étudiera la construction efficace d'outils fondamentaux pour la recherche de motifs: le trie des suffixes, ainsi que des représentations plus compactes, comme l'automate des suffixes; ce sera l'occasion d'aborder des algorithmes spécifiques aux automates acycliques. Pour conclure cette partie, on introduira des notions de dynamique symbolique, telles que les mots interdits minimaux, les codes et codes circulaires.

La seconde partie présente des algorithmes classiques mais avancés sur les automates finis. On s'intéressera d'abord à la minimisation, la minimisation des automates déterministes dans un premier temps, l'unicité de l'automate minimal, les différents algorithmes de minimisation, puis la réduction des automates non déterministes à l'aide des notions de morphisme et de revêtement. Ensuite, on exminera les algorithmes de synthèse d'automates à partir d'expressions rationnelles : Thompson, Positions, Standard, Dérivées et on étudiera les relations entre les résultats de ces différents algorithmes.
  

Combinatoire 2

Introduire les idées fondamentales de la combinatoire algébrique. On montrera comment des questions élémentaires de combinatoire des mots amènent à introduire diverses structures (fonctions quasi-symétriques, tableaux de Young, fonctions symétriques, etc.) et algorithmes (Robinson-Schensted-Knuth), et on illustrera ces méthodes sur un exemple substantiel (la règle de Littlewood-Richardson).

L'objectif du cours est d'introduire et de motiver quelques objets fondamentaux de la combinatoire algébrique moderne. On commencera par l'algorithme de Robinson-Schensted, que l'on motivera par le problème du calcul de la longueur d'un sous-mot croissant maximal d'un mot sur un alphabet ordonné. L'étude des propriétés combinatoires de cet algorithme conduira naturellement à la notion de fonction de Schur, et à l'exposé des notions fondamentales de la théorie des représentations des groupes. On montrera ensuite comment diverses algèbres non commutatives récemment introduites permettent de donner une preuve simple de la célèbre règle de Littlewood-Richardson pour la multiplication des fonctions de Schur, et on en donnera diverses applications, par exemple au calcul des caractères du groupe symétrique.

    Bio-informatique et automates

Introduction à la Biologie Moléculaire et à l'Evolution Moléculaire

Ce cours est divisé en deux parties de même volume.

Partie I

L'objectif est de permettre aux étudiants de comprendre les problèmes actuels que peuvent se poser les biologistes qui utilisent des techniques d'étude à grande échelle (séquençage et annotation des génomes, mécanismes d' évolution des génomes, génomique comparative et évolutive) et de mettre en lumière les problèmes informatiques sous-jacents (algorithmique, gestion de masses de données) grâce à une bonne compréhension des analyses biologiques réalisées.

On rappelle d'abord des notions de bases de biologie (Réplication, Transcription, Traduction et Régulation de l'expression), les principes de l'évolution moléculaire (structures des gènes, substitutions de nucléotides, duplications de gènes, familles multigéniques, transposition, transfert horizontal etc..) On s'intéresse ensuite au séquençage des génomes et à la régulation de l'expression génique : épigénétique et par les petits ARN non codants (miRNA et SiRNA).

Partie II

La génomique comparée étudie les similitudes structurelles entre les génomes, afin de mettre en évidence des organisations fonctionnelles de gènes ou de séquences communes, ou bien des relations phylogénétiques entre espèces.

Les approches classiques en génomique comparée intègrent à l'heure actuelle l'ordre des gènes, car l'information portée par celui-ci est loin d'être négligeable. Dans ce contexte, les génomes sont représentés par des permutations signées et il s'agit de transformer une permutation signée en une autre par un nombre minimum d'opérations (scénario d'évolution parcimonieux) ou de mesurer la similarité entre deux permutations signées. Nous aborderons dans ce cours les principales opérations: renversements et transpositions pour le calcul d'un scénario d'évolution parcimonieux et nombre de points de cassures et nombre d'intervalles communs pour mesurer la similarité entre deux génomes.

Génération aléatoire, graphes réguliers et automates infinis

La description d'une famille d'objets ou de séquences ne donne pas toujours une façon simple d'engendrer aléatoirement et uniformément des objets ou séquences de cette famille. On présente dans ce cours diverses méthodes de génération aléatoire : méthode récursive, générateurs de Boltzmann. Ces méthodes s'appuie sur une bonne compréhension de la manière dont ces familles sont engendrées, via en particulier l'étude de leurs séries génératrices.

La seconde partie du cours traite de graphes et automates ayant un ensemble dénombrable de sommets et de présentation finie. On montre comment les automates à pile, qui reconnaissent les langages algébriques, sont descriptibles dans ce contexte. On étudiera les extensions des graphes et automates finies aux graphes et automates réguliers: propriétés de fermeture, algorithmes de cheminement, arbre couvrant régulier,...

Transducteurs et codage

Une première partie traite de la modélisation des canaux de transmission, des erreurs que peuvent subir les messages envoyés dans ces canaux. On étudiera les algorithmes de codage de canal, qu'on analysera au moyen de la notion d'entropie. On modélisera ces contraintes sous forme de systèmes dynamiques symboliques; on étudiera en particulier les systèmes de type fini et les systèmes sofiques.

La seconde partie du cours portera sur les transducteurs, c'est-à-dire les automates avec sortie qui interviennent en codage, mais aussi en linguistique. On verra comment les composer, décider si la relation qu'un transducteur réalise est une fonction et, le cas échéant, si cette relation peut être réalisée par un transducteur déterministe en entrée séquentiel, lettre-à-lettre, et la possibilité de minimiser ces représentations. On étudiera comment extraire une fonction à partir d'une relation réalisée par transducteurs.

Mots et automates

Le cours porte sur les codes à longueur variable et les automates finis. Une attention spéciale sera portée aux aspects liés aux applications en codage et compression. On considérera en particulier les codes préfixes optimaux (algorithmes de Huffman, Garsia-Wachs et Itai ), codes synchronisés, codes bifixes, codes pour sources contraintes, et codes pour canaux contraints.

Algorithmique des Réseaux d'Interactions Biologiques

L'objectif de ce cours est d'introduire quelques aspects algorithmiques de la comparaison et de l'analyse des réseaux d'interaction de protéines (RIP). Dans une première partie, des techniques algorithmiques sont introduites pour la recherche de pathways (chemins) dans les RIP. La seconde partie concerne la comparaison de RIP et considère plusieurs modélisations permettant d'aborder ces problèmes sous des angles différents.

Cet enseignement ne nécessite aucun pré-requis en biologie.

La relation entre génotype (ensemble des gènes) et phénotype (ensemble des caractères observés) est complexe. Une des voies qui se développe actuellement est l'étude systématique des interactions entre les molécules présentes dans une cellule. Ces interactions peuvent être directes (interactions physiques de protéines) ou indirectes (un facteur de transcription régule un autre gène). Si on considère toutes ces interactions, on parle de réseau d'interactions (chaque sommet représente une protéine et deux sommets sont connectés s'il existe une interaction directe ou indirecte entre les deux protéines). Dans ce contexte, la recherche de motifs dans un réseau d'interactions a pour but d'intifier des parties importantes dans ces grands réseaux.

Le contenu du cours est orienté algorithmique. Les objectifs de ce cours sont: (1) de comprendre les principaux concepts des réseaux d'interactions, (2) de donner un panaroma des différentes approches pour analyser les réseaux d'interactions et (3) d'introduire des techniques algorithmiques (essentiellement de complexité paramétrée) pour la recherche de motifs dans les réseaux d'interactions.

Le cours est organisé en 9 séances de 2 heures chacune et débutera par une mise à niveau en complexité (NP-complétude, approximation et complexité paramétrée). La recherche de motifs et la comparaison de deux réseaux d'interactions seront ensuite abordées. Une attention particulière sera portée tout au long de ce cours à la technique dite du "color coding".

    Combinatoire

Fonctions spéciales, groupes et ondelettes

La combinatoire algébrique a de nombreux rapports avec la théorie des représentations des groupes. Le but de ce cours est de familiariser les étudiants avec cette théorie en expliquant de manière détaillée, et à partir de zéro, quelques exemples fondamentaux comme les séries de Fourier sphériques et les ondelettes. Ce cours peut être un complément utile pour les étudiants souhaitant se spécialiser en image ou traitement du signal.

Les fonctions symétriques de Schur, introduites dans le cours précédent, jouent un rôle central dans la combinatoire moderne, et admettent de nombreuses variantes ou généralisations, en particulier les polynômes de Macdonald. Les applications de ces diverses fonctions proviennent du fait qu'elles sont interprétables comme fonctions sphériques zonales attachées à certains groupes. Le cours a pour objet de présenter une introduction à ces questions, en particulier les fonctions sphériques classiques, et les diverses fonctions spéciales qui apparaissent avec les groupes les plus simples. On étudiera ainsi la fonction Gamma, associée au groupe affine de la droite, qui conduira lui-même à la théorie des ondelettes. L'étude de l'oscillateur harmonique quantique conduira aux polynômes d'Hermite, au groupe de Heisenberg et aux ondelettes de Gabor. Une seconde partie présentera des applications des ondelettes en traitement d'images et de signaux. Ce cours pourra être suivi avec profit par les étudiants d'autres filières.

Algèbre de Hopf combinatoires

Il a été découvert récemment que bon nombre d'algorithmes classiques (parfois ausssi simples que le tri par bulles ou l'insertion dans un arbre binaire de recherche) pouvaient s'interpréter dans un formalisme algébrique moderne. Cette interprétation conduit à une présentation extrêmement simple d'une bonne partie de la combinatoire classique, et trouve des applications dans des domaines variés.

Hyperdéterminants et intégrales multiples

Les hyperdéterminants sont des généralisations des déterminants à des tableaux multidimensionnels. Leur définition remonte au XIXème siècle, mais leur étude a été rapidement abandonnée à cause de la complexité des calculs. Avec l'augmentation régulière de la puissance de calcul des ordinateurs, on commence à être en mesure d'expérimenter sur ces objets et d'en découvrir des propriétés. C'est d'autant plus intéressant qu'on sait les utiliser pour exprimer diverses quantités (par exemples des intégrales) importantes en physique mais actuellement incalculables.