Groupe de travail
Algorithmes, Bio-informatique et Combinatoire

A structural graph was used to mathematically represent the large ribosomal subunit crystallographic structure. A minimal cycle basis of the ribosome structural graph was determined and analyzed. Redundant cycles were found, some of which correspond to acknowledged structural and functional motifs. In this presentation, I will introduce the RNA structural graph, the minimal cycle basis, the distance metric used in the clustering, and the results of applying this approach to the large ribosomal subunit.

Etant donné un langage fini L, on va dénombrer (à l'aide des séries formelles) le nombre de mots finis de longueur n n'admettant aucun mot de L pour facteur.
En application, on va retrouver la formule de Conway, montrer que l'algorithme KMP est asymptotiquement optimal et on verra ensuite si il reste du temps.

Les algorithmes de partitionnement ont souvent permis d'obtenir des algorithmes simples pour divers problemes. Le prix à payer est parfois un surcoût de log n par rapport à la complexité linéaire. C'était le cas pour la décomposition modulaire. Nous montrerons comment en changeant légèrement de point de vue on peut retrouver une complexité linéaire sans perdre la simplicité de l'algorithme.

L'analyse dynamique d'algorithmes consiste en un ensemble de techniques d'études issues d'un formalisme tiré des systèmes dynamiques (systèmes dynamiques de l'intervalle, opérateur de Ruelle,...). L'intérêt, en théorie de l'information, de l'utilisation d'un tel formalisme est que l'on peut modéliser des phénomènes qui possèdent un fort degré de corrélation. Dans le cadre des problèmes sur les mots, deux symboles quelconques du mots peuvent être corrélés. Ce type de "sources" trouve donc des applications naturelles en bio-informatique en terme de modélisation des séquences du génomes et plus généralement dans l'étude des langues naturelles.

Au cours de l'exposé, je présenterai les sources dynamiques et je montrerai comment ces sources peuvent être utilisées pour étudier, de manière statistique, un problème général de recherche de motifs.

Travail en commun avec C. Gavoille (LaBRI).

A toute famille de graphes à n sommets, nous pouvons associer une matrice universelle des distances. C'est une matrice carrée contenant en sous-matrice, la matrice des distances de tout graphe de la famille d'origine. La dimension de cette matrice universelle peut-être vue comme une mesure de complexité de cette famille de graphes.
Nous montrons que la famille des graphes d'intervalles à n sommets admet une telle matrice de dimension n⁵ et prouvons une borne inférieure en n^5/2. Pour montrer la borne supérieure nous construisons un étiquetage des distances affectant à chaque sommet des étiquettes de taille 5log n+1 bits de telle sorte que la distance entre deux sommets quelconque puisse être calculée en temps constant en ne considérant que les étiquettes de ces deux sommets. Ces étiquettes peuvent être calculées en O(n).

Etant donné un graphe connexe G=(V,E) muni d'une fonction de poids f sur ses arètes E, le problème de MinCut (ou de coupe minimum) consiste à trouver un ensemble d'arètes déconnectant G et dont la somme des poids est minimum. Note : n=|V| et m=|E|.

1. Nous regarderons d'abord la combinatoire de ce problème sur la base de quelques exemples et d'un algorithme randomisé dû à Karger & Stein qui tourne en O(n^2log n).
2. Nous verrons ensuite un algorithme déterministe permettant de trouver un mincut en un temps O(mn+n^2log n).
3. Nous nous intéresserons ensuite à des algorithmes pour trouver *tous* les mincut d'un graphe. Nous verrons un probleme de bioinformatique (reconstruction de "superarbres") constituant une des applications possibles de ce problème.
4. Sur la base de quelques lemmes et exemples, nous verrons qu'il existe pas mal de redondance entre les différents mincut d'un graphe. Cette redondance a donné naissance à plusieurs structures permettant de représenter l'ensemble des mincuts, dont les arbres de Gomory-Hu et les Cactus (aye aye aye, ouïe), que nous examinerons. Nous verrons que la taille de ces cactus est linéaire en fonction de n et m.
5. Si le temps le permet, nous verrons aussi comment construire ces représentations avec une complexité O(nm log(n^2/m)).

On s'est intéressé aux traitements graphiques de données d'expression de gènes suivant l'approche de Eisen et al., (1998). On a repris dans ce contexte les approches de sériation utilisées principalement en archéologie (Robinson, 1951). On a, en particulier, étudié différentes méthodes algorithmiques pour organiser de façon optimale les feuilles d'un dendrogramme issu d'une classification ascendante hiérarchique. On a introduit un critère assimilable à un critère d'inertie et dont la minimisation donne de bons résultats. On étudiera les propriétés de ce critère dans une perspective algorithmique. On montrera également l'analogie des résultats obtenus par ce critère avec l'analyse statistique du positionnement multidimensionnel. L'exposé prendra appui sur l'analyse d'un jeu de données biologiques. On montrera combien notre approche semble justifiée dans le contexte de l'analyse de données d'expression. On présentera, tout au long de l'exposé, les sorties d'un logiciel développé sous Windows et qui reprend les méthodes exposées.

Eisen, M. B., Spellman, P. T., Brown, P. O., and Botstein, D. (1998), "Cluster Analysis and Display of Genome-Wide Expression Patterns," Proceeding of the National academy of sciences of the United States of America, 95, 14863--14868.

Robinson, W. S. (1951), "A Method for Chronologically Ordering Archaeological Deposits," American Antiquity, 16, 293-301.

An important goal in the field of graph algorithms is to find large classes of graphs for which large classes of problems are solvable efficiently with practical algorithms. The arguably strongest results in this direction are achieved by the class of graphs of bounded treewidth, containing for example the control-flow graphs of structured programs. Such a graph G has a tree-decomposition (T,X) of constant width k, and algorithms for many NP-hard problems on G proceed by dynamic programming along the tree-structure T, computing a table of size exponential in k for each node of the tree T. The large size of the tables means that these algorithms are memory-intensive, and for practical running times we need to minimize the number of tables stored in memory simultaneously. It turns out that the number of tables needed lies between the pathwidth of T and twice the pathwidth of T. The natural issue that arises is therefore to study the tradeoff between the width k and the pathwidth of tree-decompositions, in the hope that I/O to external memory can be avoided or minimized. In this talk we present the catwidth parameter of a graph G that reflects the lowest width obtainable when we restrict the tree T of the tree-decomposition to have pathwidth 1, i.e. only 2 tables in memory. Such trees are called caterpillars, and the catwidth of a graph lies between the treewidth and the pathwidth of the graph. Just as treewidth relates to chordal graphs and pathwidth relates to interval graphs, catwidth relates to what we call catval graphs. A well-known concept in the study of graphs with a linear structure is that of an asteroidal triple (AT) and here we introduce the related concept of extended asteroidal triples (XAT) to characterize catval graphs as exactly the XAT-free chordal graphs.

Notre exposé traitera essentiellement des problèmes de pavages des régions bornées du plan par un jeu fini de tuiles, avec pour but d'introduire deux approches "récentes" du sujet : l'approche de Thurston, Conway et Lagarias qui vise à interpréter les problèmes de pavages en termes d'appartenance d'un mot à un groupe de présentation, chaque objet étant ici associé à un mot par le codage de son bord; et mon approche consistant à associer aux tuiles des polynômes (de manière assez naturelle) de telle sorte que le problème de pavage s'identifie à un problème d'appartenance à un idéal d'un anneau de polynômes. Ces deux approches bien que fondamentalement différentes donnent des théorèmes équivalents et jette de facto un pont intéressant entre certains problèmes à priori difficiles de réduction de mot et des problèmes de géométrie effective plus simple.

L'arboricité d'un graphe G est une mesure de la densité des arètes: max_H |E(H)|/(|V(H)|-1) pour tout sous-graphe H de G. Nous verrons une preuve du théorème de Nash-Williams qui indique que l'arboricité est aussi le plus petit nombre de forêt qui partionnent les arètes de G.

Nous montrerons ensuite comment il est possible de maintenir pour des graphes dynamiques d'arboricité bornée, des étiquettes de tailles O(log n) par sommet de tel sorte que l'adjacence puisse être testée en n'utilisant que ces étiquettes. Ce résultat est issus du papier de Brodal et Fagerberg Dynamic representation of sparse graphs, WADS'99.

Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are ``not too far'' in all genomes. In this paper, we propose a unifying concept, called << gene teams >>, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by N genes placed on M linear chromosomes. The first one runs in O(M^2N^2) time, and follows a ``natural'' and simple approach. The second one is more tricky, but its running time is O(MNlog^2(N)). Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity.
This work has been done by Anne Bergeron, Sylvie Corteel and Mathieu Raffinot and partially published in WABI'2002. We refer the interested reader to: http://www-igm.univ-mlv.fr/~raffinot/geneteam.html.

La suite de Kolakoski est la suite K à valeurs dans {1,2} telle que K₁=2 et K_n est égal à la longueur du n-ième bloc de symboles identiques consécutifs dans K :

Fixed-parameter algorithms offer a constructive and powerful approach to obtaining practical solutions despite the (almost inevitable) intractability of certain problems. The essential idea is to identify one or more aspects of the input to a problem as the parameters, and to confine the combinatorial explosion of computational difficulty to an additive function of the parameters so that the costs are polynomial in the non-parameterized part of the input. Fixed-parameter tractable algorithms have become standard in a variety of application areas such as computational biology. There is a number of design techniques for fixed-parameter algorithms, among them bounded search trees. In computational biology, however, examples of bounded search tree algorithms are, so far, rare. In this talk, I give an introduction into the concept of parameterized complexity and the design of bounded search tree algorithms and I present some examples where this technique was applied to consensus problems in the analysis of DNA and RNA data.

Cet exposé présentera un outil ensembliste , les Décompositions Partitives, ainsi que des extensions de cette notion. Il s'agit de familles de parties (ou de bipartitions) d'un ensemble possédant certaines propriétés de fermeture pour l'union, la différence et l'intersection. Ces familles possèdent une structure arborescente : une quantité potentiellement exponentielle de membres est générée par un arbre d'inclusion de parties.

Il existe sans doute un grand nombre d'objets du monde des idées qui se trouvent être des familles partitives. Un des buts du groupe de travail sera de rallonger la liste actuelle! Citons:

• modules des graphes, des graphes orientés, et généralisations diverses
• décomposition disjonctive des fonctions booléennes
• split decomposition (décomposition en coupes des graphes)
• décomposition en composantes 3-connexes
• décomposition homogène des weak-bisplits graphs (graphes bipartis)
• etc etc...

On va essayer de donner une interprétation combinatoire de diverses notions basiques en physique statistique quantique. On ira peut-être même jusqu'à parler de nombres colorés. En tous cas, on comptera et on fera des moyennes.

Le mot de Kolakoski est un mot lisse car il est point fixe de l'opérateur qui compte le nombre de consécutifs égaux:

Étant donnés un graphe G et une famille F de chaînes élémentaires dans G, nous cherchons une coloration des chaînes de F de sorte que

• 2 chaînes qui partagent une même arête du graphe G n'aient pas la même couleur;
• le nombre total de couleurs utilisées soit le plus petit possible.

Lorsque l'on s'intéresse aux systèmes de numération du point de vue de la théorie des langages formels, un thème central est l'étude des connexions pouvant exister entre les propriétés arithmétiques des nombres et les propriétés syntaxiques de leurs représentations. Dans la hiérarchie de Chomsky, les langages les plus simples sont les langages réguliers (reconnus par automate fini). Ainsi un thème largement étudié est de déterminer si un ensemble de nombres entiers donne lieu à un ensemble de représentations régulier. On parlera alors d'ensemble reconnaissable d'entiers. En particulier, on demande souvent que le système de numération soit tel que l'ensemble N de tous les entiers soit reconnaissable. En effet, de cette manière, on peut tester facilement (i.e., au moyen d'un automate) si un mot est ou non une représentation valide.
Partant de cette constatation, nous pouvons construire des systèmes de numération satisfaisant trivialement cette requête en considérant un langage régulier infini L sur un alphabet totalement ordonné. En effet, l'ordre total sur l'alphabet induit naturellement un ordre généalogique sur les mots du langage. L'énumération des mots de L fournit donc une bijection entre N et L. Cette manière de procéder généralise de nombreux systèmes classiques de position comme les systèmes à base entière ou le système de Fibonacci. Dans cet exposé, nous nous proposons de présenter les principales propriétés de ces systèmes généralisés. Les thémes évoqués seront : la préservation du caractère reconnaissable vis-à-vis d'opérations arithmétiques, les suites automatiques, la représentation des nombres réels.

La notion de graphe sandwich a été introduite en 1995 par Golumbic: il s'agit d'un graphe compris entre un graphe G et un des sous-graphes de G. L'étude de problèmes d'analyse de séquence d'ADN ou encore de synchronisation de processeurs peut se traduire en une recherche d'un graphe sandwich vérifiant une propriété particulière. Nous nous sommes intéressés aux sandwich modules, le problème est de trouver un graphe sandwich contenant un module, en cherchant à les énumérer nous corrigeons un théorème faux publié à ce sujet. Puis nous avons cherché à adapter la notion aux graphes orientés, et donc aux ordres, en découvrant d'intéressants problèmes, comme celui de l'ordre sandwich de permutation.

Les "arbres de duplication" permettent de décrire l'histoire des duplications en tandem de séquences longues (gènes ou minisatellites). Ils ont été proposés par Walter Fitch (1977), sans que leurs propiétés combinatoires et algorithmiques soient étudiées, puis perdus de vue jusqu'à une époque très récente, où il est devenu évident que la duplication constitue l'un des mécanismes majeurs d'évolution des génomes. D'un point informatique, les arbres de duplication constituent une généralisation des arbres de recherche. Dans l'exposé nous présenterons le modèle, donnerons les raisons qui soutiennent sa validité biologique, ainsi que les premiers résultats combinatoires (issus d'un travail collectif avec la Nouvelle-Zelande): comptage, formule asymptotique, propriétés, algorithmes de génération uniforme et de reconnaissance.

Un mot infini sur l'alphabet A est dit équilibré si pour tout couple de facteurs de même longueur (\omega,\omega') et pour toute lettre a,
|(|\omega|_a - |\omega'|_a)|< 2, où |\omega|_a désigne le nombre d'occurences de la lettre a dans le mot omega. Nous généraliserons cette notion en intoduisant différentes mesures d'équilibre pour les mots infinis. Nous établierons certains liens entre l'existence et l'approximation de fréquences et les propriétés d'équilibre d'un mot infini. Dans le cas des points fixes de substitutions primitives, nous montrerons que le comportement asymptotique de ces mesures est en partie imposé par le spectre de la matrice d'incidence associée à la substitution.

Très souvent, la structure du web est modélisée par un graphe où les pages web représentent les sommets et les hyperliens les arcs (orientés). On capture ainsi la façon dont les pages sont reliées les unes aux autres. Mais une telle représentation ne tient pas compte de la structure des URLs des pages, qui forme un arbre. Après avoir défini une famille de fonctions permettant d'avoir une mesure rapide de la qualité d'une partition en sites, nous allons mettre en place une nouvelle entité, l'arbre-graphe. Nous essaierons ensuite de tirer profit de cette nouvelle structure pour effectuer une partition intelligente du web en entités qui se rapprochent le plus possible de la vision intuitive que l'on a d'un site.