En bioinformatique, un des problèmes très étudiés est la reconstitution des événements évolutifs qui transforment un génome A en un autre génome B. L'ordre des gènes dans les génomes est souvent modélisé par des permutations signées. Dans ce travail, nous définissons des liens entre le problème de tri des permutations signées par inversions et la conservation des structures combinatoires communes aux génomes à comparer. En utilisant les arbres des intervalles forts (Bergeron et al. (3)), nous démontrons que même si le calcul d'un scénario parfait et parcimonieux est difficile (Figeac et Varré (11)), il peut se faire d'une façon efficace pour une grande classe de permutations. Nous avons appliqué ces résultats à la comparaison des chromosomes X de l'humain, de la souris et du rat, basée sur les données de l'article de Gibbs et al. (12). ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Génomique comparée, Scénarios d'évolution, Tri par inversions, Intervalles communs.

Le but principal de ce travail est d'apporter une synthèse des travaux effectués sur les algorithmes capables d'identifier des groupes de gènes, ou des segments de génomes, communs à différentes espèces. Nous nous limitons à une approche basée sur la modélisation des génomes à l'aide de permutations, où les groupes d'éléments conservés entre différents génomes sont définis par la notion d'intervalles communs. L'étude approfondie de cette problématique nous a aussi permis d'innover et de présenter un nouvel algorithme plus général. Ce travail comporte donc deux aspects principaux, bien que le second soit intercalé dans le premier : une partie synthèse et une partie innovatrice. Après un survol des notions de bases, la partie synthèse présente les premiers algorithmes qui permettent de calculer les intervalles communs, puis l'approche de Bergeron et al. (2005) qui a grandement simplifié les premières solutions. Cette partie comprend aussi les algorithmes des mêmes auteurs qui calculent les intervalles communs dits forts, et une discussion sur les avantages de leur utilisation par rapport aux intervalles communs classiques. La partie innovatrice présente un nouvel algorithme qui généralise deux algorithmes de Bergeron et al. (2005). Nous concluons cette étude en constatant l'extrême simplicité et la grande efficacité, autant théorique que pratique, des plus récents algorithmes et nous croyons peu vraisemblable qu'il soit possible d'en améliorer la performance de façon significative. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithmique, Génomique comparée, Intervalles communs, Permutations.

Dans ce travail, nous nous intéressons dans la première partie, constituée de cinq chapitres, aux mots de Yamanouchi et dans la deuxième partie, constituée d'un seul chapitre, aux permutations connexes et aux hypercartes pointées. Dans le premier chapitre, nous donnerons un résumé des résultats connus et utilisés dans cette thèse. Dans le chapitre 2, nous généraliserons l'expression donnant read(t) et row(t) pour t un tableau de Young standard aux tableaux gauches standards où read(t) et row(t) sont deux mots associés au tableau t. Nous donnerons une interprétation géométrique pour les standardisations à gauche et à droite d'un mot quelconque. Ensuite, nous utiliserons les arrangements de van Leeuwen pour donner une preuve naturelle à tous les résultats de ce chapitre. Nous définirons les paires de mots de Yamanouchi indécomposables ct nous montrerons qu'elles sont en bijection avec les permutations connexes. Dans le chapitre 3, nous élaborerons des algorithmes sur les mots de Yamanouchi qui sont en bijection avec les tableaux de Young standards. Ces algorithmes simileront les algorithmes connus sur les tableaux à savoir : la transposition, les glissements du jeu taquin de Schützenberger, l'évacuation et la correspondance de Schensted. Dans le chapitre 4, nous élaborerons un algorithme de redressement d'un mot qui n'est pas un mot de Yamanouchi. Cet algorithme similera l'algorithme connu de redressement d'un tableau gauche standard en un tableau de Young standard par une suite de glissements du jeu de taquin de Schützenberger. Nous montrerons que le mot de Yamanouchi obtenu par cet algorithme est identique au mot de Yamanouchi obtenu par un algorithme de Robinson. Nous généraliserons le résultat de van Leeuwen donnant le lien entre la correspondance de Robinson, entre les permutations et les paires de mots de Yamanouchi, et celle de Schensted, entre les permutations et les paires de tableaux de Young standards, des permutations aux mots arbitraires. Nous utiliserons le résultat obtenu pour donner une réponse à une question posée par Thomas. Nous utiliserons l'algorithme de Robinson pour donner une expression à l'évacué d'un mot de Yamanouchi. Nous utiliserons l'algorithme de redressement pour donner une nouvelle formule à la correspondance de Schensted. Dans le chapitre 5, nous poserons une nouvelle conjecture ayant un lien étroit avec une conjecture de Schützenberger qui concerne son opération d'évacuation d'un tableau de Young standard et avec la correspondance de Schensted. Nous montrerons que cette nouvelle conjecture implique celle de Schützenberger. Nous donnerons une solution pour cette nouvelle conjecture dans le cas particulier des tableaux ayant seulement deux lignes. Dans le dernier chapitre, nous utiliserons les formules de Dumont et Kreweras, qui ont étudié une famille particulière de fractions continues liée à la série hypergéométrique, pour donner une nouvelle preuve aux formules donnant les permutations connexes selon leur nombre et aussi selon leur nombre de cycles. Nous établirons deux nouvelles formules pour les permutations connexes. Nous montrerons que le résultat de Sillke et celui de Dumont et Kreweras sont équivalents ensuite nous généraliserons chacun des deux résultats en passant au type cyclique au lieu du nombre de cycles. Nous généraliserons une formule donnée par Cori qui concerne les hypercartes étiquetées à n points. Nous donnons une expression à chacune des deux séries formelles donnant le nombre des permutations selon leur type cyclique et aussi le nombre des permutations connexes selon leur type cyclique. Finalement, nous donnerons le nombre de sous-groupes normaux d'indice n dans le groupe libre à deux générateurs pour n un entier premier. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Tableaux de Young standards, tableaux gauches standards, mots de Yamanouchi, standardisation à gauche et à droite, transposition, glissements du jeu taquin de Schützenberger, évacuation, redressement d'un tableau gauche standard, correspondance de Schensted, correspondance de Robinson, relations de Knuth, monoïde palxique, permutations connexes, hypercartes pointées, sous-groupes du groupe libre à deux générateurs.

Thesis (M.S.)--Brigham Young University. Dept. of Mathematics, 2007. / Includes bibliographical references (p. 27-28).

We introduce and explore an approach to estimating statisticalsignificance of classification accuracy, which is particularly usefulin scientific applications of machine learning where highdimensionality of the data and the small number of training examplesrender most standard convergence bounds too loose to yield ameaningful guarantee of the generalization ability of theclassifier. Instead, we estimate statistical significance of theobserved classification accuracy, or the likelihood of observing suchaccuracy by chance due to spurious correlations of thehigh-dimensional data patterns with the class labels in the giventraining set. We adopt permutation testing, a non-parametric techniquepreviously developed in classical statistics for hypothesis testing inthe generative setting (i.e., comparing two probabilitydistributions). We demonstrate the method on real examples fromneuroimaging studies and DNA microarray analysis and suggest atheoretical analysis of the procedure that relates the asymptoticbehavior of the test to the existing convergence bounds.

I samband med en fastighetsöverlåtelse kan förvärvarens förfoganderätt över fastigheten inskränkas genom ett överlåtelseförbud. I de situationer då en tredje part blir involverad kan det uppstå komplikationer, därför är det viktigt att vara väl medveten om ett överlåtelseförbuds innebörd och rättsverkningar. Oavsett om överlåtelsen är benefik eller onerös, gör lagstiftningen på området ingen skillnad på villkorets giltighet. Däremot har det inom praxis utformats markanta skillnader på överlåtelseförbudens rättsverkningar beroende på vilken överlåtelseform som använts. Sker överlåtelsen genom gåva, medges överlåtelseförbudet betydligt mer långtgående rättsverkningar än vid ett köp. Vidare påverkar villkorets ordalydelse om det anses vara gällande för viss tid, eller för obegränsad tid. Under vissa förutsättningar kan ett överlåtelseförbud ändras eller upphävas, antingen av parterna själva eller genom ansökan om permutation. Det är dock till viss del oklart i vilken omfattning parterna själva kan vidta sådana åtgärder.

Judging goodness of fit in multidimensional scaling requires a comprehensive set of diagnostic tools instead of relying on stress rules of thumb. This article elaborates on corresponding strategies and gives practical guidelines for researchers to obtain a clear picture of the goodness of fit of a solution. Special emphasis will be placed on the use of permutation tests. The second part of the article focuses on goodness-of-fit assessment of an important variant of multidimensional scaling called unfolding, which can be applied to a broad range of psychological data settings. Two real-life data sets are presented in order to walk the reader through the entire set of diagnostic measures, tests, and plots. R code is provided as supplementary information that makes the whole goodness-of-fit assessment workflow, as presented in this article, fully reproducible.

In this paper limit theorems for the conditional distributions of linear test statistics are proved. The assertions are conditioned by the sigma-field of permutation symmetric sets. Limit theorems are proved both for the conditional distributions under the hypothesis of randomness and under general contiguous alternatives with independent but not identically distributed observations. The proofs are based on results on limit theorems for exchangeable random variables by Strasser and Weber. The limit theorems under contiguous alternatives are consequences of an LAN-result for likelihood ratios of symmetrized product measures. The results of the paper have implications for statistical applications. By example it is shown that minimum variance partitions which are defined by observed data (e.g. by LVQ) lead to asymptotically optimal adaptive tests for the k-sample problem. As another application it is shown that conditional k-sample tests which are based on data-driven partitions lead to simple confidence sets which can be used for the simultaneous analysis of linear contrasts. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

A superpattern is a string of characters of length n that contains as a subsequence, and in a sense that depends on the context, all the smaller strings of length k in a certain class. We prove structural and probabilistic results on superpatterns for preferential arrangements, including (i) a theorem that demonstrates that a string is a superpattern for all preferential arrangements if and only if it is a superpattern for all permutations; and (ii) a result that is reminiscent of a still unresolved conjecture of Alon on the smallest permutation on [n] that contains all k-permutations with high probability.

No description available.