Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Characterizing Dynamic Optimization Benchmarks for the Comparison of Multi-Modal Tracking Algorithms

Population-based metaheuristics, such as particle swarm optimization (PSO), have been employed to solve many real-world optimization problems. Although it is of- ten sufficient to find a single solution to these problems, there does exist those cases where identifying multiple, diverse solutions can be beneficial or even required. Some of these problems are further complicated by a change in their objective function over time. This type of optimization is referred to as dynamic, multi-modal optimization. Algorithms which exploit multiple optima in a search space are identified as niching algorithms. Although numerous dynamic, niching algorithms have been developed, their performance is often measured solely on their ability to find a single, global optimum. Furthermore, the comparisons often use synthetic benchmarks whose landscape characteristics are generally limited and unknown. This thesis provides a landscape analysis of the dynamic benchmark functions commonly developed for multi-modal optimization. The benchmark analysis results reveal that the mechanisms responsible for dynamism in the current dynamic bench- marks do not significantly affect landscape features, thus suggesting a lack of representation for problems whose landscape features vary over time. This analysis is used in a comparison of current niching algorithms to identify the effects that specific landscape features have on niching performance. Two performance metrics are proposed to measure both the scalability and accuracy of the niching algorithms. The algorithm comparison results demonstrate the algorithms best suited for a variety of dynamic environments. This comparison also examines each of the algorithms in terms of their niching behaviours and analyzing the range and trade-off between scalability and accuracy when tuning the algorithms respective parameters. These results contribute to the understanding of current niching techniques as well as the problem features that ultimately dictate their success.

Properties and Algorithms of the KCube Interconnection Networks

The KCube interconnection network was first introduced in 2010 in order to exploit the good characteristics of two well-known interconnection networks, the hypercube and the Kautz graph. KCube links up multiple processors in a communication network with high density for a fixed degree. Since the KCube network is newly proposed, much study is required to demonstrate its potential properties and algorithms that can be designed to solve parallel computation problems. In this thesis we introduce a new methodology to construct the KCube graph. Also, with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k). Moreover, we will find its connectivity followed by an optimal broadcasting scheme in which a source node containing a message is to communicate it with all other processors. In addition to KCube networks, we have studied a version of the routing problem in the traditional hypercube, investigating this problem: whether there exists a shortest path in a Qn between two nodes 0n and 1n, when the network is experiencing failed components. We first conditionally discuss this problem when there is a constraint on the number of faulty nodes, and subsequently introduce an algorithm to tackle the problem without restrictions on the number of nodes.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Life Insurance and Genetics: A Comparative International Overview

La possibilité d'utiliser l'information génétique dans le domaine de l'assurance vie a soulevé des discussions autour des politiques et des législations, et ce, au niveau international, régional et national. Dans certains pays offrant des services de santé universels, le débat sur la génétique et l'assurance vie a envisagé de possibles restrictions quant à l'utilisation de l’information génétique en matière d’assurance.

Physicians, genetics and life insurance

Par contraste avec de nombreux pays européens qui ont clarifié leur position vis-à-vis la génétique et l’assurance vie, le Canada en est encore à établir la sienne. Toute initiative en ce domaine doit être basée sur une compréhension des mécanismes de l’assurance vie, de la nature de l’information génétique, de l’historique du débat au sujet de la génétique et de l’assurance vie au Canada et, finalement, des raisons pour lesquelles un groupe de travail canadien a décidé de relever le défi.

Genetics and Life Insurance in Canada: Points to Consider

Par contraste avec de nombreux pays européens qui ont clarifié leur position vis-à-vis la génétique et l’assurance vie, le Canada en est encore à établir la sienne. Toute initiative en ce domaine doit être basée sur une compréhension des mécanismes de l’assurance vie, de la nature de l’information génétique, de l’historique du débat au sujet de la génétique et de l’assurance vie au Canada et, finalement, des raisons pour lesquelles un groupe de travail canadien a décidé de relever le défi.

Genetics and Life Insurance: A Comparative Analysis

The debate surrounding the role of life insurance, the necessity of risk rating, and the notion of “acceptable discrimination” has raised questions about the larger social role of insurance. Recent developments in the field of genetics, allowing insurers to make use of genetic testing technology as a new underwriting tool, have reinvigorated this debate. This article presents a comparative study of positions taken in countries on issues in genetics and life insurance. We will analyze the 43 selected countries and comment on their potential for ensuring a more equitable access for life insurance applicants.

Models, algorithms, and heuristics for multiobjetive commercial territory design.

Tesis (Doctor en Ingeniería de Sistemas) UANL, 2010.

Models and algorithms for transit network planning.

Tesis (Doctor en Ingeniería con Especialidad en Ingeniería de Sistemas) UANL, 2012.

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Genetics of amyotrophic lateral sclerosis

La sclérose latérale amyotrophique (SLA) est la maladie des neurones moteurs la plus fréquente, affectant 4-6 individus par 100,000 habitants à l’échelle mondiale. La maladie se caractérise par une faiblesse et une atrophie musculaire suite à la dégénérescence des neurones du cortex moteur, tronc cérébral et moelle épinière. Les personnes atteintes développent les premiers symptômes à l’âge adulte et la maladie progresse sur une période de trois à cinq ans. Il a été répertorié qu’environ 10% des patients ont une histoire familiale de SLA; 90% des gens affectés le sont donc de façon sporadique. La découverte il y a 19 ans de mutations dans le gène zinc/copper superoxide dismutase (SOD1), présentes dans 15-20% des cas familiaux de SLA et environ 2% du total des individus affectés, a été l’événement déclencheur pour la découverte de variations génétiques responsables de la maladie. La recherche sur la génétique de la SLA a connu une progression rapide ces quatre dernières années avec l’identification de mutations dans de nouveaux gènes. Toutefois, même si certains de ces gènes ont été démontrés comme réellement liés à la maladie, la contribution d’autres gènes demeure incertaine puisque les résultats publiés de ceux-ci n’ont pas, à ce jour, été répliqués. Une portion substantielle de cas reste cependant à être génétiquement expliquée, et aucun traitement à ce jour n’a été démontré comme étant efficace pour remédier, atténuer ou prévenir la maladie. Le but du projet de recherche de doctorat était d’identifier de nouveaux gènes mutés dans la SLA, tout en évaluant la contribution de gènes nouvellement identifiés chez une importante cohorte multiethnique de cas familiaux et sporadiques. Les résultats présentés sont organisés en trois sections différentes. Dans un premier temps, la contribution de mutations présentes dans le gène FUS est évaluée chez les patients familiaux, sporadiques et juvéniles de SLA. Précisément, de nouvelles mutations sont rapportées et la proportion de mutations retrouvées chez les cas familiaux et sporadiques de SLA est évaluée. De plus, une nouvelle mutation est rapportée dans un cas juvénile de SLA; cette étude de cas est discutée. Dans un deuxième temps, de nouvelles avenues génétiques sont explorées concernant le gène SOD1. En effet, une nouvelle mutation complexe est rapportée chez une famille française de SLA. De plus, la possibilité qu’une mutation présente dans un autre gène impliqué dans la SLA ait un impact sur l’épissage du gène SOD1 est évaluée. Finalement, la dernière section explique la contribution de nouveaux gènes candidats chez les patients atteints de SLA. Spécifiquement, le rôle des gènes OPTN, SIGMAR1 et SORT1 dans le phénotype de SLA est évalué. Il est souhaité que nos résultats combinés avec les récents développements en génétique et biologie moléculaire permettent une meilleure compréhension du mécanisme pathologique responsable de cette terrible maladie tout en guidant le déploiement de thérapies suite à l’identification des cibles appropriées.

Clustering algorithms and shape factor methods to discriminate among small GTPase phenotypes using DIC image analysis.

Naïvement perçu, le processus d’évolution est une succession d’événements de duplication et de mutations graduelles dans le génome qui mènent à des changements dans les fonctions et les interactions du protéome. La famille des hydrolases de guanosine triphosphate (GTPases) similaire à Ras constitue un bon modèle de travail afin de comprendre ce phénomène fondamental, car cette famille de protéines contient un nombre limité d’éléments qui diffèrent en fonctionnalité et en interactions. Globalement, nous désirons comprendre comment les mutations singulières au niveau des GTPases affectent la morphologie des cellules ainsi que leur degré d’impact sur les populations asynchrones. Mon travail de maîtrise vise à classifier de manière significative différents phénotypes de la levure Saccaromyces cerevisiae via l’analyse de plusieurs critères morphologiques de souches exprimant des GTPases mutées et natives. Notre approche à base de microscopie et d’analyses bioinformatique des images DIC (microscopie d’interférence différentielle de contraste) permet de distinguer les phénotypes propres aux cellules natives et aux mutants. L’emploi de cette méthode a permis une détection automatisée et une caractérisation des phénotypes mutants associés à la sur-expression de GTPases constitutivement actives. Les mutants de GTPases constitutivement actifs Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V ont été analysés avec succès. En effet, l’implémentation de différents algorithmes de partitionnement, permet d’analyser des données qui combinent les mesures morphologiques de population native et mutantes. Nos résultats démontrent que l’algorithme Fuzzy C-Means performe un partitionnement efficace des cellules natives ou mutantes, où les différents types de cellules sont classifiés en fonction de plusieurs facteurs de formes cellulaires obtenus à partir des images DIC. Cette analyse démontre que les mutations Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V induisent respectivement des phénotypes amorphe, allongé, rond et large qui sont représentés par des vecteurs de facteurs de forme distincts. Ces distinctions sont observées avec différentes proportions (morphologie mutante / morphologie native) dans les populations de mutants. Le développement de nouvelles méthodes automatisées d’analyse morphologique des cellules natives et mutantes s’avère extrêmement utile pour l’étude de la famille des GTPases ainsi que des résidus spécifiques qui dictent leurs fonctions et réseau d’interaction. Nous pouvons maintenant envisager de produire des mutants de GTPases qui inversent leur fonction en ciblant des résidus divergents. La substitution fonctionnelle est ensuite détectée au niveau morphologique grâce à notre nouvelle stratégie quantitative. Ce type d’analyse peut également être transposé à d’autres familles de protéines et contribuer de manière significative au domaine de la biologie évolutive.

Revisiting optimization algorithms for maximum likelihood estimation

Parmi les méthodes d’estimation de paramètres de loi de probabilité en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions l´egères, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problèmes de maximum de vraisemblance peuvent être traités comme des problèmes de programmation non linéaires, éventuellement non convexe, pour lesquels deux grandes classes de méthodes de résolution sont les techniques de région de confiance et les méthodes de recherche linéaire. En outre, il est possible d’exploiter la structure de ces problèmes pour tenter d’accélerer la convergence de ces méthodes, sous certaines hypothèses. Dans ce travail, nous revisitons certaines approches classiques ou récemment d´eveloppées en optimisation non linéaire, dans le contexte particulier de l’estimation de maximum de vraisemblance. Nous développons également de nouveaux algorithmes pour résoudre ce problème, reconsidérant différentes techniques d’approximation de hessiens, et proposons de nouvelles méthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linéaire. Il s’agit notamment d’algorithmes nous permettant de changer d’approximation de hessien et d’adapter la longueur du pas dans une direction de recherche fixée. Finalement, nous évaluons l’efficacité numérique des méthodes proposées dans le cadre de l’estimation de modèles de choix discrets, en particulier les modèles logit mélangés.