m

Documents  92D20 | enregistrements trouvés : 25

O

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

68Q25 ; 68Q42 ; 90C39 ; 92D20 ; 92E10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Localisation : Salle de manutention

bout d'un groupe # calcul stochastique sur les variétés # chaîne d'Ising # conformation spatiale de l'ADN # fonction hypergéométrique de plusieurs variables # géométrie symplectique # intégration sur algèbre de Gelfand # isomorphisme de De Rham pour variétés singulières # noeud cablé # ondelette et probabilité # pliage de papier # polynôme de Legendre # suite de Rudin-Shapiro # équation de Fredhom hyperfine

33Cxx ; 42C10 ; 42Cxx ; 58G32 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology;Probability and Statistics

Les Acides RiboNucléiques (ARN) sont des biopolymères linéaires omniprésents dans notre organisme, pouvant être codés comme des séquences sur un alphabet A,C,G,U. Ces molécules se replient sur elles-mêmes, établissant des liaisons hydrogènes d'où découlent l'appariement de certaines des positions, selon des règles de compatibilité des lettres n'autorisant que les paires dans l'ensemble A,U,C,G,G,U. De ce mécanisme d'appariements résulte l'adoption d'une ou plusieurs conformations, appelées structures secondaires, au passage bijectif avec les mots de Motzkin sans-pic. De nombreuses applications, en nanotechnologie, médecine, ou biostatistique, nécessitent de compter, ou encore engendrer aléatoirement, des séquences d'ARN simultanément compatibles avec un ensemble donné de structures secondaires. Un algorithme exponentiel, basé sur une décomposition (ear decomposition) du graphe de dépendance induit par l'union des paires, a ainsi été proposé par Höner zu Siederdissen et al [A]. Cet algorithme utilise la méthode récursive/programmation dynamique pour précalculer les nombres d'affectations compatibles avant/après chacun des choix locaux. Une phase de génération utilise ensuite ces nombres pour garantir l'uniformité de la génération. Cependant, cet algorithme ne permettait pas la prise en compte de critères énergétiques plus complexes, nécessitant l'utilisation d'un formalisme plus expressif que les graphes de dépendance (hypergraphes). De plus, la complexité de l'algorithme, théoriquement exponentielle sur un paramètre non-borné et parfois élevée en pratique, soulevait la question de la complexité du problème de comptage.
Dans un travail récent avec Hammer, Wang et Will [B], nous établissons la #P complétude, et la complexité d'approximation, du problème de comptage des séquences compatibles. Notre preuve repose sur une bijection simple entre les séquences compatibles et les stables du graphes de dépendance. Nous proposons une approche alternative, basée sur la décomposition arborescente, pour contrôler de façon probabiliste [C] l'énergie moyenne des séquences pour les différentes structures, ou la composition en les différentes lettres. Ces résultats fournissent un cadre flexible et expressif pour le design d'ARN, et soulèvent des questions sur l'utilisation de stratégies alternatives (génération de Boltzmann, simulation parfaite) pour la génération aléatoire, ainsi sur le concept d'analyse en moyenne dans un contexte où la donnée en entrée est plus complexe que la taille de l'objet engendré.
Les Acides RiboNucléiques (ARN) sont des biopolymères linéaires omniprésents dans notre organisme, pouvant être codés comme des séquences sur un alphabet A,C,G,U. Ces molécules se replient sur elles-mêmes, établissant des liaisons hydrogènes d'où découlent l'appariement de certaines des positions, selon des règles de compatibilité des lettres n'autorisant que les paires dans l'ensemble A,U,C,G,G,U. De ce mécanisme d'appariements résulte ...

05A05 ; 05B45 ; 60C05 ; 68Q87 ; 68Q45 ; 68R05 ; 68W32 ; 90C27 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

92C40 ; 92D10 ; 92D20 ; 92E10 ; 68T05 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

92C40 ; 92D10 ; 92D20 ; 92E10 ; 68T05 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

92C40 ; 92D20 ; 92E10 ; 68Q10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Mathematics in Science and Technology;Probability and Statistics

In this presentation, we shall discuss the reconstruction of demographic parameters based on the genetic variability observed within a sample of individual DNA. In the family of models that we consider, the statistics describing this genetic diversity (number of mutations, distribution of the mutations amongst individuals in the sample) depend on a more or less coarse ‘resolution of (i.e., level of information on) the hidden genealogical tree that relates the sampled individuals. Considering the optimal resolution thus allows to greatly improve the exploration of the space of possible genealogies when computing the likelihood of demographic parameters, compared to classical methods based on full labelled trees such as Kingmans coalescent. We shall focus on two examples, based on works with Raazesh Sainudiin (Uppsala Univ.) and with Julia Palacios (Stanford Univ.), Sohini Ramachandran (Brown Univ.) and John Wakeley (Harvard Univ.). In this presentation, we shall discuss the reconstruction of demographic parameters based on the genetic variability observed within a sample of individual DNA. In the family of models that we consider, the statistics describing this genetic diversity (number of mutations, distribution of the mutations amongst individuals in the sample) depend on a more or less coarse ‘resolution of (i.e., level of information on) the hidden genealogical tree ...

92D15 ; 92D20 ; 60J10 ; 60J27

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

68Q25 ; 68Q42 ; 68Q87 ; 90C39 ; 92D20 ; 92C40

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xx; 280 p.
ISBN 978-1-4939-1558-3

Interdisciplinary applied mathematics , 0019

Localisation : Ouvrage RdC (KIMM)

processus de ramification # processus de Galton-Watson # processus dépendant de l'âge # processus de Bellman-Harris # processus multitype # réaction en chaîne par polymérase # mutation du cancer # amplification de gènes # séquence répétée d'ADN

91B70 ; 92Cxx ; 92C37 ; 92Dxx ; 92D10 ; 92D15 ; 92D20 ; 92D25 ; 93C95 ; 60J80 ; 60J85

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- ix; 467 p.
ISBN 978-0-8218-6863-8

Clay mathematics proceedings , 0015

Localisation : Colloque 1er étage

probabilités # évolution de Schramm-Loewner # fractales # équilibre statistique # ADN

60-06 ; 60G60 ; 60K35 ; 60K37 ; 82B20 ; 82B27 ; 82B28 ; 82B41 ; 82B43 ; 82B44 ; 28A80 ; 82Bxx ; 92D20 ; 00B25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xviii; 846 p.
ISBN 978-981-4383-00-4

Series on knots and everything , 0053

Localisation : Ouvrage RdC (KAUF)

noeud # algèbre de Hopf # entrelacs # équation de Yang-Baxter # groupe quantique # matrice r # mécanique statistique # modèle statistique # polynôme de Jones # tenseur # tresse # réseau de spins # modèle de Potts # polynôme HOMFLY # polynôme d'Alexander # invariant de Reshetikhin-Turaev

57-01 ; 81-01 ; 92D20 ; 81R10 ; 57M25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- viii; 159 p.
ISBN 978-0-89871-380-0

CBMS-NSF regional conference series in applied mathematics , 0069

Localisation : Collection 1er étage

probabilité # optimisation # inégalité isopérimétrique

90C27 ; 90C35 ; 90-02 ; 92D20

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xiv; 500 p.
ISBN 978-0-470-47059-6

Wiley series on bioinformatics: computational techniques and engineering

Localisation : Ouvrage RdC (INTR)

bioinformatique

92D20 ; 92C40 ; 92C05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 538 p.
ISBN 978-3-540-69394-9

Bolyai society mathematical studies , 0018

Localisation : Ouvrage RdC (HAND)

graphes aléatoires # biologie neurale # probabilités combinatoires # réseau # arbre aléatoire # point critique

05A16 ; 05Cxx ; 05C80 ; 60C05 ; 60J80 ; 68R10 ; 92B20 ; 92D20 ; 92D25 ; 92E10 ; 94C15 ; 92C20 ; 05-02

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- x, 253 p.
ISBN 978-3-540-69391-8

Lecture notes in mathematics , 1953

Localisation : Collection 1er étage

application statistique # fonctionnelle densité # modèle statistique # perturbation # processus de Poisson

53B50 ; 60D05 ; 62B10 ; 62P35 ; 92D20 ; 74E35

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- xi; 376 p.
ISBN 978-0-387-09685-8

the IMA volumes in mathematics and its applications , 0149

Localisation : Ouvrage RdC (EMER)

géométrie algébrique # algèbre commutative # statistiques # biologie # arbre phylogénique

13P10 ; 14P10 ; 44A60 ; 52B12 ; 52C45 ; 62-09 ; 62H17 ; 90C22 ; 90C26 ; 92-08 ; 92D20 ; 93B25 ; 93B28

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 165 p.
ISBN 978-0-8218-3752-8

DIMACS series in discrete mathematics and theoretical computer science , 0073

Localisation : Collection 1er étage

stockage et récupération de l'information # codage de l'information # séquence ADN # séquence de protéines # dynamique symbolique # estimation # modulation # démodulation # théorie de l'information

68P20 ; 68P30 ; 92D20 ; 37B10 ; 93E10 ; 94A14 ; 94A15 ; 94A17 ; 94A40 ; 94B12

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 431 p.
ISBN 978-3-540-33282-4

Mathématiques & applications , 0057

Localisation : Collection 1er étage

modèle aléatoire # biologie # biomathématique # chaine de Markov à temps discret # modèle discret # processus de Galton-Watson # ADN # modèle continu # chaine de Markov à temps continu # file d'attente # fiabilité

60J10 ; 60J27 ; 60J80 ; 60K20 ; 60G70 ; 49L20 ; 62F12 ; 62N05 ; 90C15 ; 90B22 ; 90B25 ; 90B05 ; 92D20 ; 92D25 ; 92B15

... Lire [+]

Z