Understanding transcriptional regulation quantitatively is a crucial step towards uncovering and ultimately utilizing the regulatory semantics encoded in the genome. Transcription of a gene is induced by the binding of site-specific transcription factors (TFs) to so-called cis-regulatory-modules (CRMs). The frequency and duration of the binding events are influenced by the concentrations of the TFs, the binding affinities and location of the transcription factor binding sites (TFBSs) in the CRM as well as the properties of the TFs themselves (e.g. effectiveness, competitive interaction with other TFs). Modeling these interactions using a mathematical approach, based on sound biochemical and thermodynamic foundations, enables the understanding and quantitative prediction of transcriptional output of a target gene. In the thesis I introduce the developed framework for modeling, visualizing, and predicting the regulation of the transcription rate of a target gene. Given the concentrations of a set of TFs, the TFBSs in a regulatory DNA region, and the transcription rate of the target gene, the method will optimize its parameters to generate a predictive model that incorporates the regulatory mechanism of the observed gene. I demonstrate the generalization ability of the model by subjecting it to standard machine learning and hypothesis testing procedures. Furthermore, I demonstrate the potential of the approach by training the method on a gene in D. melanogaster and predicting the output of the homologous genes in 12 other Drosophila species where the regulatory sequence has evolved substantially but the regulatory mechanism was conserved. Finally, I investigate the proposed role-switching behaviour of TFs regulating the development of D. melanogaster, which suggests that SUMOylation is the biological mechanism facilitating the switch.

Understanding transcriptional regulation quantitatively is a crucial step towards uncovering and ultimately utilizing the regulatory semantics encoded in the genome. Transcription of a gene is induced by the binding of site-specific transcription factors (TFs) to so-called cis-regulatory-modules (CRMs). The frequency and duration of the binding events are influenced by the concentrations of the TFs, the binding affinities and location of the transcription factor binding sites (TFBSs) in the CRM as well as the properties of the TFs themselves (e.g. effectiveness, competitive interaction with other TFs). Modeling these interactions using a mathematical approach, based on sound biochemical and thermodynamic foundations, enables the understanding and quantitative prediction of transcriptional output of a target gene. In the thesis I introduce the developed framework for modeling, visualizing, and predicting the regulation of the transcription rate of a target gene. Given the concentrations of a set of TFs, the TFBSs in a regulatory DNA region, and the transcription rate of the target gene, the method will optimize its parameters to generate a predictive model that incorporates the regulatory mechanism of the observed gene. I demonstrate the generalization ability of the model by subjecting it to standard machine learning and hypothesis testing procedures. Furthermore, I demonstrate the potential of the approach by training the method on a gene in D. melanogaster and predicting the output of the homologous genes in 12 other Drosophila species where the regulatory sequence has evolved substantially but the regulatory mechanism was conserved. Finally, I investigate the proposed role-switching behaviour of TFs regulating the development of D. melanogaster, which suggests that SUMOylation is the biological mechanism facilitating the switch.

Orientador: Geraldo Nunes Silva / Banca: Luis Antônio Fernandes de Oliveira / Banca: Yurilev Chalco Cano / Resumo: Neste trabalho, estamos interessados em apresentar uma abordagem relacionando a análise não suave com a otimização. Primeiramente, é realizado um estudo sobre conceitos da análise não suave, como cones normais, cone tangente de Bouligand, subdiferenciais proximal, estrita, limite e de clarke. Com esses conceitos exibimos uma série de resultados, por exemplo, uma caracterização par funções de Lipschitz, subdiferencais da soma, produto e máximo de funções semi-contínuas inferior, uma versão não suave dos multiplicadores de Lagrange, i.e., condições de primeira ordem para otimalidade de problemas de otimização não suaves. Também é feito um estudo sobre as condições de segunda ordem para otimalidade em problemas de otimização não suaves e para isso, foi necessário a apresentação de outros conceitos e propriedades como os de Hessiana generalizada, Jacobiana aproximada a Hessiana proximada. Após a apresentação desses resultados, é feita uma análise sobre dois Teoremas que fornecem, com abordagens distintas, condições suficiente de segunda ordem para problemas de otimização não suaves e este trabalho é finalizado com a aprsentação de um resultado que é considerado uma "unificação" desses dois Teoremas / Abstract: In this work we are interested in the presentation of an approach relating Nonsmooth Analysis to Optimization. First we make a study about concepts of nonsmooth analysis such as, normal cone, Bouligand's tangent cone, proximal, strict and limiting Subdiferential, as well as Clarke's Suddifferential. After these, we exhibit a series of results, for example, a characterization of Lipschitz functions, Subdifferential sum, product and maxium rules of lower semicontinuous functions and a nonsmooth version of Lagrange's multiplier rule, that is, a first order necessary condition of optimality for nonsmooth optimization problems. We also made a study about second order optimality conditions for nonsmooth optimization problems. In order to do that, it was necessary to present other concepts and properties about generalized Hessian, approximate Jacobian and approximate Hessian. After presenting these concepts and results, an analysis of two theorems that provide, with different approches, second order conditions for optimality for nonsmooth problems is made. Finally, this dissertation is completed with the exposition of a result that is considered a "unification" of these two theorems / Mestre

O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens. / The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.

abstract: We live in a networked world with a multitude of networks, such as communication networks, electric power grid, transportation networks and water distribution networks, all around us. In addition to such physical (infrastructure) networks, recent years have seen tremendous proliferation of social networks, such as Facebook, Twitter, LinkedIn, Instagram, Google+ and others. These powerful social networks are not only used for harnessing revenue from the infrastructure networks, but are also increasingly being used as “non-conventional sensors” for monitoring the infrastructure networks. Accordingly, nowadays, analyses of social and infrastructure networks go hand-in-hand. This dissertation studies resource allocation problems encountered in this set of diverse, heterogeneous, and interdependent networks. Three problems studied in this dissertation are encountered in the physical network domain while the three other problems studied are encountered in the social network domain. The first problem from the infrastructure network domain relates to distributed files storage scheme with a goal of enhancing robustness of data storage by making it tolerant against large scale geographically-correlated failures. The second problem relates to placement of relay nodes in a deployment area with multiple sensor nodes with a goal of augmenting connectivity of the resulting network, while staying within the budget specifying the maximum number of relay nodes that can be deployed. The third problem studied in this dissertation relates to complex interdependencies that exist between infrastructure networks, such as power grid and communication network. The progressive recovery problem in an interdependent network is studied whose goal is to maximize system utility over the time when recovery process of failed entities takes place in a sequential manner. The three problems studied from the social network domain relate to influence propagation in adversarial environment and political sentiment assessment in various states in a country with a goal of creation of a “political heat map” of the country. In the first problem of the influence propagation domain, the goal of the second player is to restrict the influence of the first player, while in the second problem the goal of the second player is to have a larger market share with least amount of initial investment. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2016

O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens. / The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2017-11-06T12:17:01Z No. of bitstreams: 1 PDF - Josenildo da Cunha Lima.pdf: 21330682 bytes, checksum: b04b7f38635dc46f7b4cfbfc949c318b (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-11-08T16:45:20Z (GMT) No. of bitstreams: 1 PDF - Josenildo da Cunha Lima.pdf: 21330682 bytes, checksum: b04b7f38635dc46f7b4cfbfc949c318b (MD5) / Made available in DSpace on 2017-11-08T16:45:20Z (GMT). No. of bitstreams: 1 PDF - Josenildo da Cunha Lima.pdf: 21330682 bytes, checksum: b04b7f38635dc46f7b4cfbfc949c318b (MD5) Previous issue date: 2017-05-05 / This work presents activities that can be carried out with the High School classes and that do have basic notions of the functions, area, volume and means inequality. We present a didactic sequence, composed of several activities, with the use of GeoGebra software, so that in each of them the student can conjecture an optimization result in a classroom application. In some activities aim the elaboration of a file of type .ggb to discover an optimal value for a certain geometric element. In each activities we seek to optimize geometric elements such as segments, angles, areas and volumes. By performing these activities, students will learn geometry contents dynamically and this will provide them with a view next of what actually occurs in search to optimize of elements such geometric elements. This study aims to show that optimization problems can be worked on in High School and the results found in resolutions of these problems are demonstrated with theorems involving mathematical contents of Basic Education. / Neste trabalho apresentamos atividades que podem ser realizadas com turmas do Ensino Médio e que tenham noções básicas de funções, área, volume e desigualdade das médias. Apresentamos uma sequência didática, composta por diversas atividades, com a utilização do software GeoGebra, de modo que em cada uma delas, o aluno possa conjecturar um resultado de otimização numa aplicação em sala de aula. Algumas dessas atividades têm como objetivo a elaboração de um arquivo do tipo .ggb para se descobrir um valor ótimo para determinado elemento geométrico. Em todas as atividades buscamos otimizar elementos geométricos como segmentos, ângulos, áreas e volumes. Realizando essas atividades, os estudantes aprenderão conteúdos de geometria de forma dinâmica e isso os proporcionará uma visão próxima do que concretamente ocorre na busca por otimizar tais elementos geo- métricos. Este estudo tem como finalidade mostrar que problemas de otimização podem ser trabalhados no Ensino Médio e que os resultados usados nas resoluções desses problemas são demonstrados com teoremas envolvendo conteúdos matemáticos do Ensino Básico.

O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens. / The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.

Multi-agent systems are extensively used in several applications. An important class of applications involves the optimal spatial distribution of a group of mobile robots on a given area, where the optimality refers to the assignment of subregions to the robots, in such a way that a suitable coverage metric is maximized. Typically the coverage metric encodes a risk distribution defined on the area, and a measure of the performance of individual robots with respect to points inside the region of interest. The coverage metric will be maximized when the set of mobile robots configure themselves as the centroids of the Voronoi tessellation dictated by the risk density. In this work we advance on this result by considering a generalized area control problem in which the coverage metric is non-autonomous, that coverage metric is time varying independently of the states of the robots. This generalization is motivated by the study of coverage control problems in which the coordinated motion of a set of mobile robots accounts for the kinematics of objects penetrating from the outside. Asymptotic convergence and optimality of the non-autonmous system are studied by means of Barbalat's Lemma, and connections with the kinematics of the moving intruders is established. Several numerical simulation results are used to illustrate theoretical predictions.

Cache replacement policies have applications that are nearly ubiquitous in technology. Among these is an interesting subset which occurs when referentially transparent functions are memoized, eg. in compilers, in dynamic programming, and other software caches. In many applications the least recently used (LRU) approach likely preserves items most needed by memoized function calls. However, despite its popularity LRU is expensive to implement, which has caused a spate of research initiatives aimed at approximating its cache miss performance in exchange for faster and more memory efficient implementations. We present a novel caching algorithm, Far From Recently Used (FFRU), which offers a simple, but highly configurable mechanism for providing lower bounds on the usage recency of items evicted from the cache. This algorithm preserves the constant time amortized cost of insertions and updates and minimizes the memory overhead needed to administer the eviction guarantees. We study the cache miss performance of several memoized optimization problems which vary in the number of subproblems generated and the access patterns exhibited by their recursive calls. We study their cache miss performance using LRU cache replacement, then show the performance of FFRU in these same problem scenarios. We show that for equivalent minimum eviction age guarantees, FFRU incurs fewer cache misses than LRU, and does so using less memory. We also present some variations of the algorithms studied (Fibonacci, KMP, LCS, and Euclidean TSP) which exploit the characteristics of the cache replacement algorithms being employed, further resulting in improved cache miss performance. We present a novel implementation of a well known approximation algorithm for the Euclidean Traveling Salesman Problem due to Sanjeev Arora. Our implementation of this algorithm outperforms the currently known implementations of the same. It has long remained an open question whether or not algorithms relying on geometric divisions of space can be implemented into practical tools, and our powerful implementation of Arora's algorithm establishes a new benchmark in that arena. / Computer and Information Science