In recent years it has been shown that the folding pattern of an RNA molecule plays an important role in its function, likened to a lock and key system. γ-structures are a subset of RNA pseudoknot structures filtered by topological genus that lend themselves nicely to combinatorial analysis. Namely, the coefficients of their generating function can be approximated for large n. This paper is an investigation into the length-spectrum of the longest block in random γ-structures. We prove that the expected length of the longest block is on the order n - O(n^1/2). We further compare these results with a similar analysis of the length-spectrum of rainbows in RNA secondary structures, found in Li and Reidys (2018). It turns out that the expected length of the longest block for γ-structures is on the order the same as the expected length of rainbows in secondary structures. / Master of Science / Ribonucleic acid (RNA), similar in composition to well-known DNA, plays a myriad of roles within the cell. The major distinction between DNA and RNA is the nature of the nucleotide pairings. RNA is single stranded, to mean that its nucleotides are paired with one another (as opposed to a unique complementary strand). Consequently, RNA exhibits a knotted 3D structure. These diverse structures (folding patterns) have been shown to play important roles in RNA function, likened to a lock and key system. Given the cost of gathering data on folding patterns, little is known about exactly how structure and function are related. The work presented centers around building the mathematical framework of RNA structures in an effort to guide technology and further scientific discovery. We provide insight into the prevalence of certain important folding patterns.

No

Les travaux présentés dans ce mémoire s’inscrivent dans un projet visant à fabriquer des valves aortiques bioartificielles de remplacement pour des patients atteints de maladies cardiaques. La méthode globale étudiée consiste à produire un moule sacrificiel en sucre vitrifié produit par fabrication additive, prenant la forme d’une valve aortique et injecté avec un échafaudage cellulaire. En soumettant la valve moulée aux conditions physiologiques ressenties par une valve aortique réelle, il est espéré qu’une valve aortique fonctionnelle sera développée. Un des éléments importants dans ce procédé est l’échafaudage cellulaire. Puisque ce biomatériau contient des cellules vivantes, il doit être à l’abri de toutes sources de contamination. De plus, il doit permettre aux cellules de survivre et de sécréter de la matrice extracellulaire, dans le but d’éventuellement transformer l’échafaudage cellulaire en un tissu biologique fiable. Ce mémoire présente une technique de fabrication d’échafaudages cellulaires qui tient compte des enjeux liés à l’utilisation de cellules vivantes. Il s’agit d’une preuve de concept visant à s’intégrer au projet de valves aortiques bioartificielles. Afin de tester la méthode, une expérience in vitro de fabrication et de culture dynamique fut menée. Celle-ci démontra que cette méthode de fabrication fut adaptée au contexte de travail en environnement stérile, que les cellules ensemencées dans les spécimens furent distribuées de manière homogène, et que les moules en sucre vitrifié fabriqués par impression 3D ne causèrent pas de mortalité cellulaire dans ce contexte. Toutefois, des dommages mineurs furent observés après plusieurs semaines de culture, et les taux de viabilité cellulaire furent plus bas qu’attendu à cause d’un défaut au niveau de la perfusion des spécimens. Ainsi, la technique développée est prometteuse pour le projet de fabrication de valves aortiques, mais des améliorations doivent être apportées au niveau de la perfusion et du maintien de l’intégrité physique des tissus. / The work presented in this thesis is part of a project which aims at fabricating bioartificial aortic replacement valves for patients suffering from cardiac diseases. The global method studied to achieve this consists of fabricating sacrificial molds made of carbohydrate glass, produced by additive manufacturing, replicating the geometry of an aortic valve, and injected with a cellular scaffold. By exposing the molded valve to the physiological conditions a real aortic valve would experience, it is hoped that a functional aortic valve will be developed. One important aspect of this process is the cellular scaffold. Since this biomaterial contains live cells, it has to be isolated from all possible sources of contamination. Moreover, it has to favor cell survival, as well as extracellular matrix secretion, in order to eventually transform the scaffold into a reliable biological tissue. This thesis presents a fabrication technique for cellular scaffold that takes into account all the challenges linked to the use of live cells. It is a proof of concept with the aim of being included to the artificial aortic valve project. To validate this process and its aspects, an in vitro experiment of fabrication and dynamic culture was conducted. The results of this experiment showed that this method is adapted to the sterile work environment context, and that the cells seeded in the specimens were distributed homogeneously. This experience also demonstrated that the carbohydrate molds fabricated by additive manufacturing did not cause cell mortality in this context. However, minor damage was observed after several weeks of dynamic culture, and the cell viability rates were lower than expected because of suboptimal perfusion rates. This fabrication technique for cellular scaffolds is promising for the artificial aortic valves project, but improvements in terms of perfusion and preservation of physical integrity should be made.

Une structure dénombrable du premier ordre est dite homogène si tout isomorphisme entre deux sous-Structures finiment engendrées s’étend en un automorphisme de la structure globale.C’est équivalent à une propriété d’amalgamation des sous-Structures finiment engendrées, et les structures homogènes dénombrables sont aussi appelées limites de Fraïssé, en lien avec les travaux de Roland Fraïssé sur l’ordre des rationnels. Cette thèse concerne les groupes d’automorphismesdes structures homogènes, avec la question centrale suivante: est-Ce que le groupe automorphismes d’une structure homogène est universel pour la classe des groupes d’automorphismes de ces sous-Structures ? Nous répondons positivement à cette question pour les structures homogènesdans un langage relationnel et avec la propriété d’amalgamation libre, à l’aide d’une construction par tour assez similaire à une construction de Katetov et Uspenskij dans le cas de l’espace d’Urysohn. Avec des techniques similaires, nous obtenons toute sous-Structure dénombrable comme points fixes d’un automorphisme d’ordre fini pré-Déterminé. Cela nous permet par ailleurs d’étudier la complexité de la relation d’isomorphisme entre sous-Structures dénombrables, et de montrer qu’elle se réduit boreliennement à la relation de conjugaison dans le groupe d’automorphismes. Nous continuons avec les éléments d’ordre fini, en supposant de plus que les sous-Structures finies satisfont une version forte de la propriété d’extension de Hrushovski-Lascar-Herwig, et des arguments topologiques nous permettent alors de montrer que dans le groupe d’automorphismes tout élément est produit de quatre conjugués de certains éléments d’ordre fini. Nous montrons aussi des résultats similaires pour le groupe d’isométries de l’espace d’Urysohn,ou sa version bornée, la sphère d’Urysohn, en utilisant le fait que ces derniers sont très bien approximés par des espaces métriques rationnels. Enfin, revenant à la question de l’universalité du groupe automorphismes de la limite de Fraïssé, nous considérons la question plus fine de savoirsi toute sous-Structure dénombrable s’injecte de manière rigide, c’est-À-Dire de sorte chacun de ces automorphismes s’étende en un unique automorphisme de la limite de Fraïssé. D’abord, nous introduisons une construction de telle injections rigides dans le cas des graphes homogènes. Ensuite, nous modifions cette construction dans diverses classes de graphes orientés et de structures relationnelles homogènes, pour enfin la faire fonctionner dans un contexte très general de structures dans un langage relationnel fini et avec la propriété d’amalgamation libre. / A countable first-Order structure is called homogneous when each isomorphism between twofinitely generated substructures extends to an automorphism of the whole structure. This is equivalentto an amalgamation property of finitely generated substructures, and countable homogeneousstructures are also called Fraïssé limits, in connection to the work of Roland Fraïssé on theorder of rational numbers. The present thesis concerns automorphism groups of homogeneousstructures, with the following central question: is it the case that the automorphism group of a homogeneousstructure is universal for the class of automorphism groups of its substructures? Weanswer positively this question for homogeneous structures in a relational langage and with thefree amalgamation property, by using a construction rather similar to a construction of Katetov andUspenskij in the case of the Urysohn space.With similar techniques, we obtain any countable substructureas the set of fixed points of an automorphism of a given finite order. Besides, this allowsus to study the complexity of the isomorphism relation between countable substructures, and toshow that it Borel reduces to the conjugacy relation in the automorphism group. We continue withelements of finite order, assuming further that finite substructures satisfy a strong version of theHrushovski-Lascar-Herwig extension property, and topological arguments then allow us to showthat in the automorphism group any element is the product of four conjugates of certain elementsof finite order. We also show similar results for the isometry group of the Urysohn space, or itsbounded version, the Urysohn sphere, by using the fact that they are well approximated by rationalmetric spaces. Finally, concerning the question of the universality of the automorphism groupof a Fraïssé limit, we consider the finer question to know whether any countable substructure embedsin a rigid way, that is, in such a way that each of its automorphisms extends in a uniqueautomorphism of the Fraïssé limit. First, we introduce a construction of such rigid embeddings inthe case of homogeneous graphs. Then, we modify this construction in various classes of orientedgraphs and of homogeneous relational structures, ultimately to make it work in a very generalcontext of structures in a finite relational langage and with the free amalgamation property.

Abstract not available

Thesis (Ph. D.)--University of Missouri-Columbia, 2002. / Typescript. Vita. Includes bibliographical references (leaves 207-211). Also available on the Internet.

Thesis (Ph. D.)--University of Missouri-Columbia, 2002. / Typescript. Vita. Includes bibliographical references (leaves 207-211). Also available on the Internet.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2004. / Supervisor: Katherine A. Liapi. Vita. Includes bibliographical references. Also available from UMI.

Actuellement, la majorité des architectures de processeurs sont fondées sur une mémoire partagée avec cohérence de caches. Des prototypes intégrant de grandes quantités de cœurs, reliés par une infrastructure de transmission de messages, indiquent que, dans un proche avenir, les architectures de processeurs vont probablement avoir ces caractéristiques. Ces deux tendances exigent que les processus s'exécutent en parallèle et rendent la programmation concurrente nécessaire. Cependant, la difficulté inhérente du raisonnement sur la concurrence peut rendre ces nouvelles machines difficiles à programmer. Nous explorons trois approches ayant pour but de faciliter la programmation concurrente. Nous proposons WFR-TM, une approche fondé sur la mémoire transactionnelle (TM), un paradigme de programmation concurrente qui utilise des transactions afin de synchroniser l'accès aux données partagées. Une transaction peut soit terminer (commit), rendant visibles ses modifications, soit échouer (abort), annulant toutes ses modifications. WFR-TM tente de combiner des caractéristiques désirables des TM optimistes et pessimistes. Une TM pessimiste n'échoue jamais aucune transaction; néanmoins les algorithmes existants utilisent des verrous pour exécuter de manière séquentielle les transactions qui contiennent des opérations d'écriture. Les algorithmes TM optimistes exécutent toutes les transactions en parallèle mais les terminent seulement si elles n'ont pas rencontré de conflit au cours de leur exécution. WFR-TM fournit des transactions en lecture seule qui sont wait-free, sans jamais exécuter d'opérations de synchronisation coûteuse (par ex. CAS, LL\SC, etc) ou sacrifier le parallélisme entre les transactions d'écriture. Nous présentons également Dense, une implémentation concurrente de graphe. Les graphes sont des structures de données polyvalentes qui permettent la mise en oeuvre d'une variété d'applications. Cependant, des applications multi-processus qui utilisent des graphes utilisent encore largement des versions séquentielles. Nous introduisons un nouveau modèle de graphes concurrents, permettant l'ajout ou la suppression de n'importe quel arc du graphe, ainsi que la traversée atomique d'une partie (ou de l'intégralité) du graphe. Dense offre la possibilité d'effectuer un snapshot partiel d'un sous-ensemble du graphe défini dynamiquement. Enfin, nous ciblons les futures architectures. Dans l'intérêt de la réutilisation du code il existe depuis quelques temps une tentative d'adaptation des environnements d'exécution de logiciel - comme par ex. JVM, l'environnement d'exécution de Java - initialement prévus pour mémoire partagée, à des machines sans cohérence de caches. Nous étudions des techniques générales pour implémenter des structures de données distribuées en supposant qu'elles vont être utilisées sur des architectures many-core, qui n'offrent qu'une cohérence partielle de caches, voir pas de cohérence du tout. / Though a majority of current processor architectures relies on shared, cache-coherent memory, current prototypes that integrate large amounts of cores, connected through a message-passing substrate, indicate that architectures of the near future may have these characteristics. Either of those tendencies requires that processes execute in parallel, making concurrent programming a necessary tool. The inherent difficulty of reasoning about concurrency, however, may make the new processor architectures hard to program. In order to deal with issues such as this, we explore approaches for providing ease of programmability. We propose WFR-TM, an approach based on transactional memory (TM), which is a concurrent programming paradigm that employs transactions in order to synchronize the access to shared data. A transaction may either commit, making its updates visible, or abort, discarding its updates. WFR-TM combines desirable characteristics of pessimistic and optimistic TM. In a pessimistic TM, no transaction ever aborts; however, in order to achieve that, existing TM algorithms employ locks in order to execute update transactions sequentially, decreasing the degree of achieved parallelism. Optimistic TMs execute all transactions concurrently but commit them only if they have encountered no conflict during their execution. WFR-TM provides read-only transactions that are wait-free, without ever executing expensive synchronization operations (like CAS, LL/SC, etc), or sacrificing the parallelism between update transactions. We further present Dense, a concurrent graph implementation. Graphs are versatile data structures that allow the implementation of a variety of applications. However, multi-process applications that rely on graphs still largely use a sequential implementation. We introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. Dense achieves wait-freedom by relying on light-weight helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph. We finally aim at predicted future architectures. In the interest of ode reuse and of a common paradigm, there is recent momentum towards porting software runtime environments, originally intended for shared-memory settings, onto non-cache-coherent machines. JVM, the runtime environment of the high-productivity language Java, is a notable example. Concurrent data structure implementations are important components of the libraries that environments like these incorporate. With the goal of contributing to this effort, we study general techniques for implementing distributed data structures assuming they have to run on many-core architectures that offer either partially cache-coherent memory or no cache coherence at all and present implementations of stacks, queues, and lists.