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.

Quantifying historical, capital mobility in Canada : an error correction approach.

Rapport de recherche

Allocation via Deferred-Acceptance under Responsive Priorities

In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource- monotonicity with two-agent consistent con ict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

Évolution de familles de gènes par duplications et pertes : algorithmes pour la correction d’arbres bruités

Les gènes sont les parties du génome qui codent pour les protéines. Les gènes d’une ou plusieurs espèces peuvent être regroupés en "familles", en fonction de leur similarité de séquence. Cependant, pour connaître les relations fonctionnelles entre ces copies de gènes, la similarité de séquence ne suffit pas. Pour cela, il est important d’étudier l’évolution d’une famille par duplications et pertes afin de pouvoir distinguer entre gènes orthologues, des copies ayant évolué par spéciation et susceptibles d’avoir conservé une fonction commune, et gènes paralogues, des copies ayant évolué par duplication qui ont probablement développé des nouvelles fonctions. Étant donnée une famille de gènes présents dans n espèces différentes, un arbre de gènes (obtenu par une méthode phylogénétique classique), et un arbre phylogénétique pour les n espèces, la "réconciliation" est l’approche la plus courante permettant d’inférer une histoire d’évolution de cette famille par duplications, spéciations et pertes. Le degré de confiance accordé à l’histoire inférée est directement relié au degré de confiance accordé à l’arbre de gènes lui-même. Il est donc important de disposer d’une méthode préliminaire de correction d’arbres de gènes. Ce travail introduit une méthodologie permettant de "corriger" un arbre de gènes : supprimer le minimum de feuilles "mal placées" afin d’obtenir un arbre dont les sommets de duplications (inférés par la réconciliation) sont tous des sommets de "duplications apparentes" et obtenir ainsi un arbre de gènes en "accord" avec la phylogénie des espèces. J’introduis un algorithme exact pour des arbres d’une certaine classe, et une heuristique pour le cas général.

DECOR : détection et correction des défauts dans les systèmes orientés objet

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

Les différences entre la correction de textes manuscrits et la correction de textes dactylographiés et imprimés par ordinateur

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

L'apport des correcticiels pour la correction de textes d'élèves du secondaire

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Characterization of in vivo vertebral growth modulation by shape memory alloy staples on a porcine model for the correction of the scoliosis

La recherche de nouvelles voies de correction de la scoliose idiopathique a une longue histoire. Le traitement conventionnel de la scoliose idiopathique est présenté par le port du corset ou par la correction opératoire de la déformation. Depuis leur introduction, les deux méthodes ont prouvé leur efficacité. Cependant, malgré des caractéristiques positives évidentes, ces méthodes peuvent causer un nombre important d'effets indésirables sur la santé du patient. Les techniques sans fusion pour le traitement de la scoliose semblent être une alternative perspective de traitement traditionnel, car ils apportent moins de risques et des complications chirurgicales que les méthodes conventionnelles avec la conservation de la mobilité du disque intravertébral. Cependant, l'utilisation de techniques mentionnées exige une connaissance profonde de la modulation de croissance vertébrale. L'objectif principal de la présente étude est d'estimer le potentiel d'agrafes à l’AMF de moduler la croissance des vertèbres porcines en mesurant la croissance osseuse sur la plaque de croissance de vertèbres instrumentées en comparaison avec le groupe contrôle. La méthode est basée sur la loi de Hueter-Volkmann. Nous avons choisi NiTi agrafes à l’AMF pour notre étude et les porcs de race Landrace comme un animal expérimental. Les agrafes ont été insérés sur 5 niveaux thoracique de T6 à T11. En outre, les radiographies ont été prises toutes les 2 semaines. La présence d'agrafes en alliage à mémoire de forme a produit la création de courbes scoliotiques significatives dans 4 de 6 animaux chargés et le ralentissement considérable de la croissance osseuse (jusqu'à 35,4%) comparativement aux groupes contrôle et sham. L'étude a démontré in vivo le potentiel d'agrafes en alliage à mémoire de formes de moduler la croissance des vertèbres en créant des courbes scoliotiques sur les radiographies et en ralentissant le taux de croissance sur les plaques de croissance instrumenté. La position précise de l'agrafe est essentielle pour la modulation de croissance osseuse et le développement de la scoliose expérimentale.

Strategy-proofness makes the difference: deferred-acceptance with responsive priorities

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB)procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

House allocation via deferred-acceptance

We study the simple model of assigning indivisible and heterogenous objects (e.g., houses, jobs, offi ces, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. For this model, known as the house allocation model, we characterize the class of rules satisfying unavailable object invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness: any rule with these properties must allocate objects based on (implicitly induced) objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm.

La fiscalité et l'inflation au Rwanda: Une analyse empirique basée sur le modèle à correction d'erreur.

Rapport de recherche présenté à la Faculté des arts et des sciences en vue de l'obtenion du grade de Maîtrise en sciences économiques.