|
Archives année 2002-2003 |
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 n5 et prouvons
une borne inférieure en n5/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|.
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: maxH |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 K1=2 et Kn 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:
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
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.