In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case.<p>Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one. <p><p>We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval. <p><p>Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set. <p><p>We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable.<p>Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set.<p><p>Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances. <p> / Doctorat en sciences, Orientation recherche opérationnelle / info:eu-repo/semantics/nonPublished

股票市場對投資者而言是以極大化自有資產為目的，因此如何辨別不同景氣區間對股市的影響為投資者感興趣的議題。傳統上，使用統計資料來幫助我們比較不同景氣區間之差異，然而股票市場之複雜、非線性及不可預測性也經常成為各統計資料失準的關鍵，因此，本篇論文以複雜網路作為分析股票市場之模型，並將各個股票表示成節點、股價變化之關聯性作為連結下，建立出複雜網路，藉此探討股市中的景氣差異。 　　在本研究中，先利用國發會制定的景氣對策信號，來幫助我們選取四段景氣區間，接著將台積電作為網路核心建構個股的相關網路。並以最小生成樹(Minimum Spanning Tree) 將複雜的股票網路簡單化。同時我們計算出各股相關網路之全域網路參數(Global Network Parameters)及區域網路參數(Regional Network Parameters)，以利我們討論兩段景氣好區間與兩段景氣差區間之差異。最後，我們將股市相關網路以分層樹(Hierarchical Tree)來表示，以了解網路分群的結果。 　　結果顯示，我們建構的個股相關網路符合小世界網路特性，在全域網路參數中，景氣好相關網路之常規化平均特徵路徑(Normalization Average Characteristic Path Length)及景氣差相關網路中之平均群聚係數(Average Clustering Coefficient)、平均特徵路徑(Average Characteristic Path Length)、常規化平均特徵路徑(Normalization Average Characteristic Path Length)有顯著差異。 在區域網路參數中，在景氣好相關網路中，被選為網路樞紐並有顯著差異之個股有台達化、宜進與華通，景氣差相關網路則有瑞利、日月光、矽品及萬企。在景氣好相關網路比較時，台積電的連結度與點效率皆具有顯著差異。

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-11T17:36:54Z No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:21Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:27Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Made available in DSpace on 2016-10-21T13:03:34Z (GMT). No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) Previous issue date: 2016-08-12 / Não recebi financiamento / Cluster analysis is the organization of a collection of patterns into clusters based on similarity which is determined by using properties of data. Clustering techniques can be useful in a variety of knowledge domains such as biotechnology, computer vision, document retrieval and many others. An interesting area of biology involves the concept of microRNAs (miRNAs) that are approximately 22 nucleotide-long non-coding RNA molecules that play important roles in gene regulation. Clustering miRNA sequences can help to understand and explore sequences belonging to the same cluster that has similar biological functions. This research work investigates and explores seven unsupervised clustering algorithms based on graphs that can be divided into three categories: algorithm based on region of influence, algorithm based on minimum spanning tree and spectral algorithm. To assess the contribution of the proposed algorithms, data from miRNA families stored in the online miRBase database were used in the conducted experiments. The results of these experiments were presented, analysed and evaluated using clustering validation indexes as well as visual analysis. / A análise de agrupamento é uma organização de coleção de padrões em grupos, baseando-se na similaridade das propriedades pertencentes aos dados. A técnica de agrupamento pode ser utilizado em muitas áreas de conhecimento como biotecnologia, visão computacional, recuperação de documentos, entre outras. Uma área interessante da biologia envolve o conceito de microRNAs (miRNAs), que são moléculas não-codificadas de RNA com aproximadamente 22 nucleotídeos e que desempenham um papel importante na regulação dos genes. O agrupamento de sequências de miRNA podem ajudar em sua exploração e entendimento, pois as sequências que pertencem ao mesmo grupo possuem uma função biológica similar. Esse trabalho explora e investiga sete algoritmos de agrupamentos não-supervisionados baseados em grafos que podem ser divididos em três categorias: algoritmos baseados em região de influência, algoritmos baseados em árvore spanning minimal e algoritmo espectral. Para avaliar a contribuição dos algoritmos propostos, os experimentos conduzidos utilizaram os dados das famílias de miRNAs disponíveis no banco de dados denominado miRBase. Os resultados dos experimentos foram apresentados, analisados e avaliados usando índices de validação de agrupamento e análise visual.

Stem cells differentiate through an organized hierarchy of intermediate cell types to terminally differentiated cell types. This process is largely guided by master transcriptional regulators, but it also depends on the expression of many other types of genes. The discrete cell types in the differentiation hierarchy are often identified based on the expression or non-expression of certain marker genes. Historically, these have often been various cell-surface proteins, which are fairly easy to assay biochemically but are not necessarily causative of the cell type, in the sense of being master transcriptional regulators. This raises important questions about how gene expression across the whole genome controls or reflects cell state, and in particular, differentiation hierarchies. Traditional approaches to understanding gene expression patterns across multiple conditions, such as principal components analysis or K-means clustering, can group cell types based on gene expression, but they do so without knowledge of the differentiation hierarchy. Hierarchical clustering and maximization of parsimony can organize the cell types into a tree, but in general this tree is different from the differentiation hierarchy. Using hematopoietic differentiation as an example, we demonstrate how many genes other than marker genes are able to discriminate between different branches of the differentiation tree by proposing two models for detecting genes that are up-regulated or down-regulated in distinct lineages. We then propose a novel approach to solving the following problem: Given the differentiation hierarchy and gene expression data at each node, construct a weighted Euclidean distance metric such that the minimum spanning tree with respect to that metric is precisely the given differentiation hierarchy. We provide a set of linear constraints that are provably sufficient for the desired construction and a linear programming framework to identify sparse sets of weights, effectively identifying genes that are most relevant for discriminating different parts of the tree. We apply our method to microarray gene expression data describing 38 cell types in the hematopoiesis hierarchy, constructing a sparse weighted Euclidean metric that uses just 175 genes. These 175 genes are different than the marker genes that were used to identify the 38 cell types, hence offering a novel alternative way of discriminating different branches of the tree. A DAVID functional annotation analysis shows that the 175 genes reflect major processes and pathways active in different parts of the tree. However, we find that there are many alternative sets of weights that satisfy the linear constraints. Thus, in the style of random-forest training, we also construct metrics based on random subsets of the genes and compare them to the metric of 175 genes. Our results show that the 175 genes frequently appear in the random metrics, implicating their significance from an empirical point of view as well. Finally, we show how our linear programming method is able to identify columns that were selected to build minimum spanning trees on the nodes of random variable-size matrices.