La programmation génétique (GP) est une hyperheuristique d’optimisation ayant été appliquée avec succès à un large éventail de problèmes. Cependant, son intérêt est souvent considérablement diminué du fait de son utilisation élevée en ressources de calcul et de sa convergence laborieuse. Ces problèmes sont causés par une croissance immodérée de la taille des solutions et par l’apparition de structures inutiles dans celles-ci. Dans ce mémoire, nous présentons HARM-GP, une nouvelle approche résolvant en grande partie ces problèmes en permettant une adaptation dynamique de la distribution des tailles des solutions, tout en minimisant l’effort de calcul requis. Les performances de HARM-GP ont été testées sur un ensemble de douze problèmes et comparées avec celles de neuf techniques issues de la littérature. Les résultats montrent que HARM-GP excelle au contrôle de la croissance des arbres et du surapprentissage, tout en maintenant de bonnes performances sur les autres aspects. / Genetic programming is a hyperheuristic optimization approach that has been applied to a wide range of problems involving symbolic representations or complex data structures. However, the method can be severely hindered by the increased computational resources required and premature convergence caused by uncontrolled code growth. We introduce HARM-GP, a novel operator equalization approach that adaptively shapes the genotype size distribution of individuals in order to effectively control code growth. Its probabilistic nature minimizes the overhead on the evolutionary process while its generic formulation allows this approach to remain independent of the problem and genetic operators used. Comparative results are provided over twelve problems with different dynamics, and over nine other algorithms taken from the literature. They show that HARM-GP is excellent at controlling code growth while maintaining good overall performances. Results also demonstrate the effectiveness of HARM-GP at limiting overtraining and overfitting in real-world supervised learning problems.

Le traitement des données de séquençage pour les rendre utilisables dans une analyse phylogénétique est long et répétitif. De plus, certaines analyses plus complexes peuvent difficilement être entreprises sans l'automatisation de certaines tâches. La création d'outils bioinformatiques permettrait de diminuer le temps consacré à la préparation des données. Le but de cette recherche est de développer des outils informatiques permettant d'automatiser le traitement de données provenant du séquençage d'organites. Pour ce faire, il a été nécessaire de créer: item des bases de données de gènes d'organites; item des outils pour l'extraction des séquences génétiques dans différents formats; item des outils pour l'identification des gènes d'organismes nouvellement séquencés; item des outils de préparation des données pour l'utilisation lors d'analyses phylogénétiques. Finalement, le bon fonctionnement des outils a été vérifié par l'exécution d'une analyse phylogénétique dont les résultats ont déjà été publiés.

Le but de ce mémoire était d’élaborer des outils informatiques et de les intégrer à une chaîne de traitement et d’analyse des données de biopuces. La chaîne d’analyse mise en place dans ce projet consiste d’abord en SLIMS, un logiciel conçu en PHP et MySQL utilisant des termes compatibles avec les standards MIAME. Il permet le suivi des expériences et des échantillons préalablement à l’extraction des ARN pour les expériences de biopuces. Les données sont prises en charge, à l’aide d’une procédure de transfert, par le logiciel BASE qui gère l’information relative aux biopuces. Finalement, les analyses de données sont réalisées avec différents outils disponibles dans Bioconductor et TM4. Un algorithme a été développé pour annoter tous les gènes de la biopuces. L’analyse d’une d’expérience comparant des épinettes transgéniques surexprimant le gène LIM2 a été faite à l’aide de la chaîne de traitement et d’analyse présentée dans ce mémoire. / The goal of this dissertation was to design and implement a microarray analysis pipeline. The first tool of the microarray pipeline is a web-based LIMS: SLIMS. It allows the storage of all data related to experiments and samples from harvest to RNA extraction. This tool was designed in PHP and MySQL allowing easy access and manipulation of the data. A tranfer algorithm was designed to allow stored data to be automatically integrated into the BASE software, a tool that allows storage and analysis of microarray data. An annotation algorithm was also designed in order to annotate genes that are on the microarrays. A lignin/cellwall annotation was also included to enable the rapid indentification of all the genes related to the lignin biosynthesis pathway and cell wall assembly. This pipeline was used to analyze transgenic spruce overexpressing the pine LIM2 gene.

"Une très grande quantité de données est présentement générée par le séquençage de génomes et doit être analysée à l'aide d'outils informatiques. Il est donc nécessaire de développer certains programmes permettant de faire les analyses désirées et d'automatiser les tâches informatiques redondantes pour accélérer le processus d'analyse des génomes. Les données de séquençage obtenues se doivent également d'être classées efficacement et d'être facilement accessibles, de même que les outils informatiques nécessaires à leur analyse. Une base de données a donc été développée, ainsi qu'un site Web permettant de la consulter et d'utiliser les divers programmes requis. Finalement, des analyses phylogénétiques sont couramment effectuées sur les génomes séquences. Toutefois, peu d'outils permettent d'utiliser l'ordre de gènes de ces génomes à cette fin. Un programme permettant de déterminer les blocs de gènes conservés entre différents génomes et d'utiliser les paires de gènes communes pour construire des arbres phylogénétiques a donc été développé."

Différentes stratégies permettent de tirer des conclusions à partir des données générées par des biopuces d'ADN dans l'étude de la dynamique de l'estradiol (E2) sur le transcriptome de la glande mammaire de souris vierges. Nous avons retenu 2 stratégies soit effectuer un classement des processus cellulaires des gènes régulés et tirer profit des courbes de régulation en fonction du temps. Nous avons de plus, utilisé 2 méthodes de normalisation des données (MAS5.0 et RMA) afin d'évaluer leurs similitudes et leurs disparités, ce qui a permis d'aller vers une meilleure compréhension de leurs impacts sur les résultats obtenus. Par l'observation des patrons d' expression suite à l'action de l'E2, les similarités entre MAS5.0 et RMA sont correctes. Cependant, c'est lorsque l'écart entre les intensités du traitement et du contrôle est faible que les dissemblances sont les plus manifestes c' est-àdire là où discriminer entre la variabilité biologique et technique est la moins évidente.

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.<p><p>Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations.<p><p>Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class.<p>/<p>La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes.<p><p>Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées.<p><p>Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

La disponibilité limitée de vaisseaux sanguins autologues pour les chirurgies vasculaires telles que le pontage coronarien ou périphérique et les performances cliniques insuffisantes des prothèses vasculaires pour le remplacement de vaisseaux sanguins de petit diamètre (Ø &lt; 6 mm) justifie la recherche dans le domaine du génie tissulaire vasculaire. L’une des stratégies explorées – le génie tissulaire fonctionnel – vise à régénérer un vaisseau sanguin in vitro dans un environnement contrôlé appelé bioréacteur. L’objectif de cette thèse est de concevoir un bioréacteur à perfusion et de développer un système de contrôle pour ce bioréacteur afin d’interagir de manière dynamique avec une construction artérielle dans le but de guider et de stimuler la maturation de constructions artérielles. La principale question étudiée dans ce projet est de déterminer comment choisir les conditions de culture à l’intérieur d’un bioréacteur le plus efficacement possible. Deux grands enjeux ont été identifiés : d’abord, le besoin de comprendre les différents phénomènes physiques et biologiques qui se déroulent à l’intérieur du bioréacteur. Ensuite, la nécessité de diriger la régénération du tissu vasculaire. Une commande utilisant le concept de programmation génétique fut développé afin de modéliser en temps réel la régénération du tissu vasculaire. En utilisant les modèles générés, la commande recherche une stratégie optimale de culture (déformation circonférentielle, cisaillement longitudinal et fréquence du débit pulsé) en considérant un processus de décision Markovien résolu par programmation dynamique. Par simulation numérique, on montre que cette méthode a le potentiel de favoriser une croissance plus rapide et plus sécuritaire des tissus en culture et permet d’identifier plus efficacement les paramètres importants pour la croissance et le remodelage des constructions artérielles. La commande est capable de gérer des modèles de croissance non linéaires. Expérimentalement, le système développé permet de mieux comprendre l’évolution des propriétés mécaniques d’une construction artérielle dans un bioréacteur. / The limited availability of autologous blood vessels for bypass surgeries (coronary or peripheral) and the poor patency rate of vascular prosthesis for the replacement of small diameter vessels (Ø &lt; 6 mm) motivate researches in the domain of vascular tissue engineering. One of the possible strategies named functional tissue engineering aims to regenerate a blood vessel in vitro in a controlled environment. The objective of this thesis is to design a perfusion bioreactor and develop a control system able to dynamically interact with a growing blood vessel in order to guide and stimulate the maturation of the vascular construct. The principal question addressed in this work is: How to choose culture conditions in a bioreactor in the most efficient way? Two main challenges have been identified: first, the need to develop a better comprehension of the physical and biological phenomenon occurring in bioreactors; second, the need to influence and optimize vascular tissue maturation. A controller based on the concept of genetic programming was developed for real-time modeling of vascular tissue regeneration. Using the produced models, the controller searches an optimal culture strategy (circumferential strain, longitudinal shear stress and frequency of the pulsed pressure signal) by the mean of a Markov decision process solved by dynamic programming. Numerical simulations showed that the method has the potential to improve growth, safety of the process, and information gathering. The controller is able to work with common nonlinearities in tissue growth. Experimental results show that the controller is able to identify important culture parameters for the growth and remodelling of tissue engineered blood vessels. Furthermore, this bioreactor represents an interesting tool to study the evolution of the mechanical properties of a vascular construct during maturation.

One of the most important and challenging ``knowledge extraction' tasks in bioinformatics is the reverse engineering of gene regulatory networks (GRNs) from DNA microarray gene expression data. Indeed, as a result of the development of high-throughput data-collection techniques, biology is experiencing a data flood phenomenon that pushes biologists toward a new view of biology--systems biology--that aims at system-level understanding of biological systems.<p><p>Unfortunately, even for small model organisms such as the yeast Saccharomyces cerevisiae, the number p of genes is much larger than the number n of expression data samples. The dimensionality issue induced by this ``small n, large p' data setting renders standard statistical learning methods inadequate. Restricting the complexity of the models enables to deal with this serious impediment. Indeed, by introducing (a priori undesirable) bias in the model selection procedure, one reduces the variance of the selected model thereby increasing its accuracy.<p><p>Gaussian graphical models (GGMs) have proven to be a very powerful formalism to infer GRNs from expression data. Standard GGM selection techniques can unfortunately not be used in the ``small n, large p' data setting. One way to overcome this issue is to resort to regularization. In particular, shrinkage estimators of the covariance matrix--required to infer GGMs--have proven to be very effective. Our first contribution consists in a new shrinkage estimator that improves upon existing ones through the use of a Monte Carlo (parametric bootstrap) procedure.<p><p>Another approach to GGM selection in the ``small n, large p' data setting consists in reverse engineering limited-order partial correlation graphs (q-partial correlation graphs) to approximate GGMs. Our second contribution consists in an inference algorithm, the q-nested procedure, that builds a sequence of nested q-partial correlation graphs to take advantage of the smaller order graphs' topology to infer higher order graphs. This allows us to significantly speed up the inference of such graphs and to avoid problems related to multiple testing. Consequently, we are able to consider higher order graphs, thereby increasing the accuracy of the inferred graphs.<p><p>Another important challenge in bioinformatics is the prediction of gene function. An example of such a prediction task is the identification of genes that are targets of the nitrogen catabolite repression (NCR) selection mechanism in the yeast Saccharomyces cerevisiae. The study of model organisms such as Saccharomyces cerevisiae is indispensable for the understanding of more complex organisms. Our third contribution consists in extending the standard two-class classification approach by enriching the set of variables and comparing several feature selection techniques and classification algorithms.<p><p>Finally, our fourth contribution formulates the prediction of NCR target genes as a network inference task. We use GGM selection to infer multivariate dependencies between genes, and, starting from a set of genes known to be sensitive to NCR, we classify the remaining genes. We hence avoid problems related to the choice of a negative training set and take advantage of the robustness of GGM selection techniques in the ``small n, large p' data setting. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this work, we present a way to extend Ant Colony Optimization (ACO), so that it can be applied to both continuous and mixed-variable optimization problems. We demonstrate, first, how ACO may be extended to continuous domains. We describe the algorithm proposed, discuss the different design decisions made, and we position it among other metaheuristics.<p>Following this, we present the results of numerous simulations and testing. We compare the results obtained by the proposed algorithm on typical benchmark problems with those obtained by other methods used for tackling continuous optimization problems in the literature. Finally, we investigate how our algorithm performs on a real-world problem coming from the medical field—we use our algorithm for training neural network used for pattern classification in disease recognition.<p>Following an extensive analysis of the performance of ACO extended to continuous domains, we present how it may be further adapted to handle both continuous and discrete variables simultaneously. We thus introduce the first native mixed-variable version of an ACO algorithm. Then, we analyze and compare the performance of both continuous and mixed-variable<p>ACO algorithms on different benchmark problems from the literature. Through the research performed, we gain some insight into the relationship between the formulation of mixed-variable problems, and the best methods to tackle them. Furthermore, we demonstrate that the performance of ACO on various real-world mixed-variable optimization problems coming from the mechanical engineering field is comparable to the state of the art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

This thesis addresses the use of machine learning techniques to develop clinical diagnostic tools for breast cancer using molecular data. These tools are designed to assist physicians in their evaluation of the clinical outcome of breast cancer (referred to as prognosis).<p>The traditional approach to evaluating breast cancer prognosis is based on the assessment of clinico-pathologic factors known to be associated with breast cancer survival. These factors are used to make recommendations about whether further treatment is required after the removal of a tumor by surgery. Treatment such as chemotherapy depends on the estimation of patients' risk of relapse. Although current approaches do provide good prognostic assessment of breast cancer survival, clinicians are aware that there is still room for improvement in the accuracy of their prognostic estimations.<p>In the late nineties, new high throughput technologies such as the gene expression profiling through microarray technology emerged. Microarrays allowed scientists to analyze for the first time the expression of the whole human genome ("transcriptome"). It was hoped that the analysis of genome-wide molecular data would bring new insights into the critical, underlying biological mechanisms involved in breast cancer progression, as well as significantly improve prognostic prediction. However, the analysis of microarray data is a difficult task due to their intrinsic characteristics: (i) thousands of gene expressions are measured for only few samples; (ii) the measurements are usually "noisy"; and (iii) they are highly correlated due to gene co-expressions. Since traditional statistical methods were not adapted to these settings, machine learning methods were picked up as good candidates to overcome these difficulties. However, applying machine learning methods for microarray analysis involves numerous steps, and the results are prone to overfitting. Several authors have highlighted the major pitfalls of this process in the early publications, shedding new light on the promising but overoptimistic results. <p>Since 2002, large comparative studies have been conducted in order to identify the key characteristics of successful methods for class discovery and classification. Yet methods able to identify robust molecular signatures that can predict breast cancer prognosis have been lacking. To fill this important gap, this thesis presents an original methodology dealing specifically with the analysis of microarray and survival data in order to build prognostic models and provide an honest estimation of their performance. The approach used for signature extraction consists of a set of original methods for feature transformation, feature selection and prediction model building. A novel statistical framework is presented for performance assessment and comparison of risk prediction models.<p>In terms of applications, we show that these methods, used in combination with a priori biological knowledge of breast cancer and numerous public microarray datasets, have resulted in some important discoveries. In particular, the research presented here develops (i) a robust model for the identification of breast molecular subtypes and (ii) a new prognostic model that takes into account the molecular heterogeneity of breast cancers observed previously, in order to improve traditional clinical guidelines and state-of-the-art gene signatures./Cette thèse concerne le développement de techniques d'apprentissage (machine learning) afin de mettre au point de nouveaux outils cliniques basés sur des données moleculaires. Nous avons focalisé notre recherche sur le cancer du sein, un des cancers les plus fréquemment diagnostiqués. Ces outils sont développés dans le but d'aider les médecins dans leur évaluation du devenir clinique des patients cancéreux (cf. le pronostique).<p>Les approches traditionnelles d'évaluation du pronostique d'un patient cancéreux se base sur des critères clinico-pathologiques connus pour être prédictifs de la survie. Cette évaluation permet aux médecins de décider si un traitement est nécessaire après l'extraction de la tumeur. Bien que les outils d'évaluation traditionnels sont d'une aide importante, les cliniciens sont conscients de la nécessité d'améliorer de tels outils.<p>Dans les années 90, de nouvelles technologies à haut-débit, telles que le profilage de l'expression génique par biopuces à ADN (microarrays), ont été mises au point afin de permettre aux scientifiques d'analyser l'expression de l'entièreté du génôme de cellules cancéreuses. Ce nouveau type de données moléculaires porte l'espoir d'améliorer les outils pronostiques traditionnels et d'approfondir nos connaissances concernant la génèse du cancer du sein. Cependant ces données sont extrêmement difficiles à analyser à cause (i) de leur haute dimensionalité (plusieurs dizaines de milliers de gènes pour seulement quelques centaines d'expériences); (ii) du bruit important dans les mesures; (iii) de la collinéarité entre les mesures dûe à la co-expression des gènes.<p>Depuis 2002, des études comparatives à grande échelle ont permis d'identifier les méthodes performantes pour l'analyse de groupements et la classification de données microarray, négligeant l'analyse de survie pertinente pour le pronostique dans le cancer du sein. Pour pallier ce manque, cette thèse présente une méthodologie originale adaptée à l'analyse de données microarray et de survie afin de construire des modèles pronostiques performants et robustes. <p>En termes d'applications, nous montrons que cette méthodologie, utilisée en combinaison avec des connaissances biologiques a priori et de nombreux ensembles de données publiques, a permis d'importantes découvertes. En particulier, il résulte de la recherche presentée dans cette thèse, le développement d'un modèle robuste d'identification des sous-types moléculaires du cancer du sein et de plusieurs signatures géniques améliorant significativement l'état de l'art au niveau pronostique. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished