A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Neuron participation in a synchrony-encoding assembly

Affiliation: Svetlana Shumikhina &Stéphane Molotchnikoff : Département de Sciences Biologiques, Université de Montréal

A Type-Preserving Compiler from System F to Typed Assembly Language

L'utilisation des méthodes formelles est de plus en plus courante dans le développement logiciel, et les systèmes de types sont la méthode formelle qui a le plus de succès. L'avancement des méthodes formelles présente de nouveaux défis, ainsi que de nouvelles opportunités. L'un des défis est d'assurer qu'un compilateur préserve la sémantique des programmes, de sorte que les propriétés que l'on garantit à propos de son code source s'appliquent également au code exécutable. Cette thèse présente un compilateur qui traduit un langage fonctionnel d'ordre supérieur avec polymorphisme vers un langage assembleur typé, dont la propriété principale est que la préservation des types est vérifiée de manière automatisée, à l'aide d'annotations de types sur le code du compilateur. Notre compilateur implante les transformations de code essentielles pour un langage fonctionnel d'ordre supérieur, nommément une conversion CPS, une conversion des fermetures et une génération de code. Nous présentons les détails des représentation fortement typées des langages intermédiaires, et les contraintes qu'elles imposent sur l'implantation des transformations de code. Notre objectif est de garantir la préservation des types avec un minimum d'annotations, et sans compromettre les qualités générales de modularité et de lisibilité du code du compilateur. Cet objectif est atteint en grande partie dans le traitement des fonctionnalités de base du langage (les «types simples»), contrairement au traitement du polymorphisme qui demande encore un travail substantiel pour satisfaire la vérification de type.

Towards the nanomechanical actuation and controlled assembly of nanomaterials using charge-transfer reactions in electroactive self-assembled monolayers

Les microcantileviers fonctionnalisés offrent une plateforme idéale pour la nano- et micro-mécanique et pour le développement de (bio-) capteurs tres sensible. Le principe d’opération consiste dans des évènements physicochimiques qui se passent du côté fonctionnalisé du microcantilevier induisant une différence de stress de surface entre les deux côtés du cantilevier qui cause une déflexion verticale du levier. Par contre, les facteurs et les phénomènes interfacials qui régissent la nature et l'intensité du stress de surface sont encore méconnus. Pour éclaircir ce phénomène, la première partie de cette thèse porte sur l'étude des réactions de microcantileviers qui sont recouverts d'or et fonctionnalisés par une monocouche auto-assemblée (MAA) électroactive. La formation d'une MAA de ferrocènylundécanethiol (FcC11SH) à la surface d'or d'un microcantilevier est le modèle utilisé pour mieux comprendre le stress de surface induit par l’électrochimie. Les résultats obtenus démontrent qu'une transformation rédox de la MAA de FcC11SH crée un stress de surface qui résulte dans une déflexion verticale du microcantilevier. Dépendamment de la flexibilité du microcantilevier, cette déflexion peut varier de quelques nanomètres à quelques micromètres. L’oxydation de cette MAA de FcC11SH dans un environnement d'ions perchlorate génère un changement de stress de surface compressive. Les résultats indiquent que la déflexion du microcantilevier est due à une tension latérale provenant d'une réorientation et d'une expansion moléculaire lors du transfért de charge et de pairage d’anions. Pour vérifier cette hypothèse, les mêmes expériences ont été répéteés avec des microcantileviers qui ont été couverts d'une MAA mixte, où les groupements électroactifs de ferrocène sont isolés par des alkylthiols inactifs. Lorsqu’un potentiel est appliqué, un courant est détecté mais le microcantilevier ne signale aucune déflexion. Ces résultats confirment que la déflexion du microcantilevier est due à une pression latérale provenant du ferrocènium qui se réorganise et qui crée une pression sur ses pairs avoisinants plutôt que du couplage d’anions. L’amplitude de la déflexion verticale du microcantilevier dépend de la structure moléculaire de la MAA et du le type d’anion utilisés lors de la réaction électrochimique. Dans la prochaine partie de la thèse, l’électrochimie et la spectroscopie de résonance de plasmon en surface ont été combinées pour arriver à une description de l’adsorption et de l’agrégation des n-alkyl sulfates à l’interface FcC11SAu/électrolyte. À toutes les concentrations de solution, les molécules d'agent tensio-actif sont empilées perpendiculairement à la surface d'électrode sous forme de monocouche condensé entrecroisé. Cependant, la densité du film spécifiquement adsorbé s'est avérée être affectée par l'état d'organisation des agents tensio-actifs en solution. À faible concentration, où les molécules d'agent tensio-actif sont présentes en tant que monomères solvatés, les monomères peuvent facilement s'adapter à l’évolution de la concentration en surface du ferrocènium lors du balayage du potential. Cependant, lorsque les molécules sont présentes en solution en tant que micelles une densité plus faible d'agent tensio-actif a été trouvée en raison de l'incapacité de répondre effectivement à la surface de ferrocenium générée dynamiquement.

Self-assembly of PS-PVP block copolymers and their complexes at the air/water interface

Une compréhension approfondie et un meilleur contrôle de l'auto-assemblage des copolymères diblocs (séquencés) et de leurs complexes à l'interface air/eau permettent la formation contrôlée de nanostructures dont les propriétés sont connues comme alternative à la nanolithographie. Dans cette thèse, des monocouches obtenues par les techniques de Langmuir et de Langmuir-Blodgett (LB) avec le copolymère dibloc polystyrène-poly(4-vinyl pyridine) (PS-PVP), seul ou complexé avec de petites molécules par liaison hydrogène [en particulier, le 3-n-pentadécylphénol (PDP)], ont été étudiées. Une partie importante de notre recherche a été consacrée à l'étude d'une monocouche assemblée atypique baptisée réseau de nanostries. Des monocouches LB composées de nanostries ont déjà été rapportées dans la littérature mais elles coexistent souvent avec d'autres morphologies, ce qui les rend inutilisables pour des applications potentielles. Nous avons déterminé les paramètres moléculaires et les conditions expérimentales qui contrôlent cette morphologie, la rendant très reproductible. Nous avons aussi proposé un mécanisme original pour la formation de cette morphologie. De plus, nous avons montré que l'utilisation de solvants à haut point d’ébullition, non couramment utilisés pour la préparation des films Langmuir, peut améliorer l'ordre des nanostries. En étudiant une large gamme de PS-PVP avec des rapports PS/PVP et des masses molaires différents, avec ou sans la présence de PDP, nous avons établi la dépendance des types principaux de morphologie (planaire, stries, nodules) en fonction de la composition et de la concentration des solutions. Ces observations ont mené à une discussion sur les mécanismes de formation des morphologies, incluant la cinétique, l’assemblage moléculaire et l’effet du démouillage. Nous avons aussi démontré pour la première fois que le plateau dans l'isotherme des PS-PVP/PDP avec morphologie de type nodules est relié à une transition ordre-ordre des nodules (héxagonal-tétragonal) qui se produit simultanément avec la réorientation du PDP, les deux aspects étant clairement observés par AFM. Ces études ouvrent aussi la voie à l'utilisation de films PS-PVP/PDP ultraminces comme masque. La capacité de produire des films nanostructurés bien contrôlés sur différents substrats a été démontrée et la stabilité des films a été vérifiée. Le retrait de la petite molécule des nanostructures a fait apparaître une structure interne à explorer lors d’études futures.

Poly(ethylene-co-acrylic acid) random copolymers : amphiphilic properties and self-assembly in aqueous medium

Les travaux de recherche présentés ici avaient pour objectif principal la synthèse de copolymères statistiques à base d’éthylène et d’acide acrylique (AA). Pour cela, la déprotection des groupements esters d’un copolymère statistique précurseur, le poly(éthylène-co-(tert-butyl)acrylate), a été effectuée par hydrolyse à l’aide d’iodure de triméthylsilyle. La synthèse de ce précurseur est réalisée par polymérisation catalytique en présence d’un système à base de Palladium (Pd). Le deuxième objectif a été d’étudier et de caractériser des polymères synthétisés à l’état solide et en suspension colloïdale. Plusieurs copolymères précurseurs comprenant différents pourcentages molaires en tert-butyl acrylate (4 à 12% molaires) ont été synthétisés avec succès, puis déprotégés par hydrolyse pour obtenir des poly(éthylène-coacide acrylique) (pE-co-AA) avec différentes compositions. Seuls les copolymères comprenant 10% molaire ou plus de AA sont solubles dans le Tétrahydrofurane (THF) et uniquement dans ce solvant. De telles solutions peuvent être dialysées dans l’eau, ce qui conduit à un échange lent entre cette dernière et le THF, et l’autoassemblage du copolymère dans l’eau peut ensuite être étudié. C’est ainsi qu’ont pu être observées des nanoparticules stables dans le temps dont le comportement est sensible au pH et à la température. Les polymères synthétisés ont été caractérisés par Résonance Magnétique Nucléaire (RMN) ainsi que par spectroscopie Infra-Rouge (IR), avant et après déprotection. Les pourcentages molaires d’AA ont été déterminés par combinaison des résultats de RMN et ii de titrages conductimètriques. A l’état solide, les échantillons ont été analysés par Calorimétrie différentielle à balayage (DSC) et par Diffraction des rayons X. Les solutions colloïdales des polymères pE-co-AA ont été caractérisées par Diffusion dynamique de la lumière et par la DSC-haute sensibilité. De la microscopie électronique à transmission (TEM) a permis de visualiser la forme et la taille des nanoparticules.

Mass spectrometry as a tool to dissect the role of chromatin assembly factors in regulating nucleosome assembly

L'assemblage des nucléosomes est étroitement couplée à la synthèse des histones ainsi qu’à la réplication et la réparation de l’ADN durant la phase S. Ce processus implique un mécanisme de contrôle qui contribue soigneusement et de manière régulée à l’assemblage de l’ADN en chromatine. L'assemblage des nucléosomes durant la synthèse de l’ADN est crucial et contribue ainsi au maintien de la stabilité génomique. Cette thèse décrit la caractérisation par spectrométrie de masse(SM) des protéines jouant un rôle critique dans l’assemblage et le maintien de la structure chromatinienne. Plus précisément, la phosphorylation de deux facteurs d’assemblage des nucléosome, le facteur CAF-1, une chaperone d’histone qui participe à l'assemblage de la chromatine spécifiquement couplée à la réplication de l'ADN, ainsi que le complexe protéique Hir, jouant de plus un rôle important dans la régulation transcriptionelle des gènes d’histones lors de la progression normale du cycle cellulaire et en réponse aux dommages de l'ADN, a été examiné. La caractérisation des sites de phosphorylation par SM nécéssite la séparation des protéines par éléctrophorèse suivi d’une coloration a l’argent. Dans le chapitre 2, nous demontrons que la coloration à l’argent induit un artéfact de sulfatation. Plus précisément, cet artéfact est causé par un réactif spécifiquement utilisé lors de la coloration. La sulfatation présente de fortes similitudes avec la phosphorylation. Ainsi, l’incrément de masse observé sur les peptides sulfatés et phosphorylés (+80 Da) nécéssite des instruments offrant une haute résolution et haute précision de masse pour différencier ces deux modifications. Dans les chapitres 3 et 4, nous avons d’abord démontré par SM que Cac1, la plus grande sous-unité du facteur CAF-1, est cible de plusieurs sites de phosphorylation. Fait intéréssant, certains de ces sites contiennent des séquences consensus pour les kinases Cdc7-Dbf4 et CDKs. Ainsi, ces résultats fournissent les premières évidences que CAF-1 est potentiellement régulé par ces deux kinases in vivo. La fonction de tous les sites de phosphorylation identifiés a ensuite été évaluée. Nous avons démontré que la phosphorylation de la Ser-503, un site consensus de la DDK, est essentielle à la répréssion transcriptionelle des gènes au niveau des télomères. Cependant, cette phosphorylation ne semble pas être nécéssaire pour d’autres fonctions connues de CAF-1, indiquant que le blocage de la phsophorylation de Cac1 Ser-503 affecte spécifiquement la fonction de CAF-1 aux structures hétérochromatiques des télomères. Ensuite, nous avons identifiés une intéraction physique entre CAF-1 et Cdc7-Dbf4. Des études in vitro ont également demontré que cette kinase phosphoryle spécifiquement Cac1 Ser-503, suggérant un rôle potential pour la kinase Cdc7-Dbf4 dans l’assemblage et la stabilité de la structure hétérochromatique aux télomères. Finalement, les analyses par SM nous ont également permi de montrer que la sous-unité Hpc2 du complexe Hir est phosphorylée sur plusieurs sites consensus des CDKs et de Cdc7-Dbf4. De plus, la quantification par SM d’un site spécifique de phosphorylation de Hpc2, la Ser-330, s’est révélée être fortement induite suite à l’activation du point de contrôle de réplication (le “checkpoint”) suite au dommage a l’ADN. Nous montrons que la Ser-330 de Hpc2 est phopshorylée par les kinases de point de contrôle de manière Mec1/Tel1- et Rad53-dépendante. Nos données préliminaires suggèrent ainsi que la capacité du complex Hir de réguler la répréssion transcriptionelle des gènes d'histones lors de la progression du cycle cellulaire normal et en réponse au dommage de l'ADN est médiée par la phosphorylation de Hpc2 par ces deux kinases. Enfin, ces deux études mettent en évidence l'importance de la spectrométrie de masse dans la caractérisation des sites de phosphorylation des protéines, nous permettant ainsi de comprendre plus précisement les mécanismes de régulation de l'assemblage de la chromatine et de la synthèse des histones.

Molecular tectonics : supramolecular 2D nanopatterning of surfaces by self-assembly

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Controlled Self-assembly of p-Phenyleneethynylene Derivatives to Diverse Supramolecular Architectures

Regional Research Laboratory

Effect of self assembly on the nonlinear optical characteristics of ZnO thin films

In the present work, we report the third order nonlinear optical properties of ZnO thin films deposited using self assembly, sol gel process as well as pulsed laser ablation by z scan technique. ZnO thin films clearly exhibit a negative nonlinear index of refraction at 532 nm and the observed nonlinear refraction is attributed to two photon absorption followed by free carrier absorption. Although the absolute nonlinear values for these films are comparable, there is a change in the sign of the absorptive nonlinearity of the films. The films developed by dip coating and pulsed laser ablation exhibit reverse saturable absorption whereas the self assembled film exhibits saturable absorption. These different nonlinear characteristics in the self assembled films can be mainly attributed to the saturation of linear absorption of the ZnO defect states.

Multi-objective assembly job shop scheduling using genetic algorithm and tabu search

Assembly job shop scheduling problem (AJSP) is one of the most complicated combinatorial optimization problem that involves simultaneously scheduling the processing and assembly operations of complex structured products. The problem becomes even more complicated if a combination of two or more optimization criteria is considered. This thesis addresses an assembly job shop scheduling problem with multiple objectives. The objectives considered are to simultaneously minimizing makespan and total tardiness. In this thesis, two approaches viz., weighted approach and Pareto approach are used for solving the problem. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. Two metaheuristic techniques namely, genetic algorithm and tabu search are investigated in this thesis for solving the multiobjective assembly job shop scheduling problems. Three algorithms based on the two metaheuristic techniques for weighted approach and Pareto approach are proposed for the multi-objective assembly job shop scheduling problem (MOAJSP). A new pairing mechanism is developed for crossover operation in genetic algorithm which leads to improved solutions and faster convergence. The performances of the proposed algorithms are evaluated through a set of test problems and the results are reported. The results reveal that the proposed algorithms based on weighted approach are feasible and effective for solving MOAJSP instances according to the weight assigned to each objective criterion and the proposed algorithms based on Pareto approach are capable of producing a number of good Pareto optimal scheduling plans for MOAJSP instances.

Programmable Self-Assembly: Constructing Global Shape using Biologically-inspire

In this thesis I present a language for instructing a sheet of identically-programmed, flexible, autonomous agents (``cells'') to assemble themselves into a predetermined global shape, using local interactions. The global shape is described as a folding construction on a continuous sheet, using a set of axioms from paper-folding (origami). I provide a means of automatically deriving the cell program, executed by all cells, from the global shape description. With this language, a wide variety of global shapes and patterns can be synthesized, using only local interactions between identically-programmed cells. Examples include flat layered shapes, all plane Euclidean constructions, and a variety of tessellation patterns. In contrast to approaches based on cellular automata or evolution, the cell program is directly derived from the global shape description and is composed from a small number of biologically-inspired primitives: gradients, neighborhood query, polarity inversion, cell-to-cell contact and flexible folding. The cell programs are robust, without relying on regular cell placement, global coordinates, or synchronous operation and can tolerate a small amount of random cell death. I show that an average cell neighborhood of 15 is sufficient to reliably self-assemble complex shapes and geometric patterns on randomly distributed cells. The language provides many insights into the relationship between local and global descriptions of behavior, such as the advantage of constructive languages, mechanisms for achieving global robustness, and mechanisms for achieving scale-independent shapes from a single cell program. The language suggests a mechanism by which many related shapes can be created by the same cell program, in the manner of D'Arcy Thompson's famous coordinate transformations. The thesis illuminates how complex morphology and pattern can emerge from local interactions, and how one can engineer robust self-assembly.

Assembly Design and Evaluation in an Augmented Reality Environment

The technologies and methodologies of assembly design and evaluation in the early design stage are highly significant to product development. This paper looks at a promising technology to mix real components (e.g. physical prototypes, assembly tools, machines, etc.) with virtual components to create an Augmented Reality (AR) interface for assembly process evaluation. The goal of this paper is to clarify the methodologies and enabling technologies of how to establish an AR assembly simulation and evaluation environment. The architecture of an AR assembly system is proposed and the important functional modules including AR environment set-up, design for assembly (DFA) analysis and AR assembly sequence planning in an AR environment are discussed in detail.

Assembly Guidance in Augmented Reality Environments Using a Virtual Interactive Tool

The application of augmented reality (AR) technology for assembly guidance is a novel approach in the traditional manufacturing domain. In this paper, we propose an AR approach for assembly guidance using a virtual interactive tool that is intuitive and easy to use. The virtual interactive tool, termed the Virtual Interaction Panel (VirIP), involves two tasks: the design of the VirIPs and the real-time tracking of an interaction pen using a Restricted Coulomb Energy (RCE) neural network. The VirIP includes virtual buttons, which have meaningful assembly information that can be activated by an interaction pen during the assembly process. A visual assembly tree structure (VATS) is used for information management and assembly instructions retrieval in this AR environment. VATS is a hierarchical tree structure that can be easily maintained via a visual interface. This paper describes a typical scenario for assembly guidance using VirIP and VATS. The main characteristic of the proposed AR system is the intuitive way in which an assembly operator can easily step through a pre-defined assembly plan/sequence without the need of any sensor schemes or markers attached on the assembly components.