The distribution of the expressed genotype is moved around in the population over time byevolution. Natural selection is one of the forces that act on the phenotype to change the patterns ofnucleotide variation underlying those distributions. How the phenotype changes over aheterogeneous environment describes the type of evolutionary force acting on this trait and thisshould be reflected in the variation at loci underlying this trait. While the variation in phenotypesand at the nucleotide level in a population indicates the same evolutionary force, it does notnecessarily mean that they are connected. In natural populations the continuous shifting of geneticmaterial through recombination events break down possible associations between loci facilitates theexamination of possible causal loci to single base pair differences in DNA-sequences. Connecting thegenotype and the phenotype thus provides an important step in the understanding the geneticarchitecture of complex traits and the forces that shape the observed patterns.This thesis examines the European aspen, Populus tremula, sampled from subpopulations overan extensive latitudinal gradient covering most of Sweden. Results show a clear geneticdifferentiation in the timing of bud set, a measure of the autumnal cessation of growth, betweendifferent parts of Sweden pointing at local adaptation. In the search for candidate genes thatunderlie the local adaptation found, most genes (25) in the photoperiodic gene network wereexamined for signals of selection. Genes in the photoperiodic network show an increase in theheterogeneity of differentiation between sampled subpopulations in Sweden. Almost half (12) of theexamined genes are under some form of selection. Eight of these genes show positive directionalselection on protein evolution and the gene that code for a photoreceptor, responsible for mediatingchanging light conditions to downstream targets in the network, has the hallmarks of a selectivesweep. The negative correlation between positive directional selection and synonymous diversityindicates that the majority of the photoperiod gene network has undergone recurrent selectivesweeps. A phenomenon that likely has occurred when P. tremula has readapted to the northern lightregimes during population expansion following retracting ice between periods of glaciations. Two ofthe genes under selection also have single nucleotide polymorphisms (SNP) that associate with budset, two in the PHYB2 gene and one in the LHY2 gene. Furthermore, there is an additional SNP inLHY1 that explain part of the variation in timing of bud set, despite the lack of a signal of selection atthe LHY1 gene. Together these SNPs explain 10-15% of the variation in the timing of bud set and 20-30% more if accounting for the positive co-variances between SNPs. There is thus rather extensiveevidence that genes in the photoperiod gene network control the timing of bud set, and reflect localadaptation in this trait.

Hemos analizado la variabilidad genética de una zona no codificante autosómica, el pseudogén homólogo al gen de la glucocerebrosidasa (psGBA). Parte del análisis se ha realizado desde la perspectiva de la genética de poblaciones humanas. Desde un punto de vista más genómico hemos establecido la dinámica de la región, a fin de entender las causas del espectro de variación. Hemos analizado el papel de la mutación, recombinación, conversión génica y, especialmente, selección. Por otra parte, psGBA es importante en la producción de alelos complejos GBA-psGBA, que provocan los tipos más severos de la enfermedad de Gaucher. Mostramos cómo el conocimiento de la variabilidad en psGBA ayuda al reconocimiento de estos alelos complejos. Finalmente, con los datos de variabilidad de dos regiones parálogas situadas en la misma región cromosómica (gen GBA / pseudogen psGBA) hemos comparado los patrones de mutación que presenta una misma secuencia bajo diferentes presiones selectivas. / We have analyzed the genetic variability in a non-coding autosomal region, the pseudogene homologous to the glucocerebrosidase gene (psGBA).Part of the analysis has been performed from the human populations point of view.From a more genomic perspective, we have established the region dynamics in order to understand the causes of the variability pattern. We have analyzed the role of mutation, recombination, gene conversion and, especially, selection.On the other hand, psGBA is important in the production of complex alleles GBA-psGBA, that lead to the most severe types of Gaucher disease. We show how the knowledge of psGBA variability helps to the identification of those complex alleles.Last, from the variability data from two paralogous regions located in the same chromosomal region (GBA gene /psGBA pseudogene) we have compared the mutation patterns shown by the same sequence under different selective pressures.

The purpose of this study was to investigate the use of mobile phones in organizing ad-hoc vehicle ridesharing based on hitch-hiking trips involving private car drivers and commuters in South Africa. A study was conducted to learn how hitch-hiking trips are arranged in the urban and rural areas of the Eastern Cape. This involved carrying out interviews with hitch-hikers and participating in several trips. The study results provided the design specifications for a Dynamic Ridesharing System (DRS) tailor-made to the hitch-hiking culture of this context. The design of the DRS considered the delivery of the ad-hoc ridesharing service to the anticipated mobile phones owned by people who use hitch-hiking. The implementation of the system used the available open source solutions and guidelines under the Siyakhula Living Lab project, which promotes the use of Information and Communication Technology (ICT) in marginalized communities of South Africa. The developed prototype was tested in both the simulated and live environments, then followed by usability tests to establish the viability of the system. The results from the tests indicate an initial breakthrough in the process of modernizing the ad-hoc ridesharing of hitch-hiking which is used by a section of people in the urban and rural areas of South Africa.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-26T21:57:37Z (GMT). No. of bitstreams: 1 Santos_DouglasOliveira_M.pdf: 1370671 bytes, checksum: 41f9ee952e593c7ed8fa83d738c343d5 (MD5) Previous issue date: 2014 / Resumo: Nesse trabalho é apresentado um framework que tem como objetivo facilitar o compartilhamento de veículos no dia a dia de uma grande cidade. O framework apresenta uma arquitetura cliente-servidor. O lado cliente é usado por passageiros para requerer uma viagem compartilhada e por motoristas, que podem ser donos de veículos privados ou taxistas, os quais estão dispostos a compartilharem seu veículo para redução de custos ou obtenção de lucro. O lado servidor precisa resolver um problema dinâmico de otimização que provamos ser NP-difícil. O problema em questão, denominado Ride-sharing Problem with Money Incentive (RSPMI), é modelado da seguinte forma: em cada instante de tempo, temos um conjunto de pessoas, as quais necessitam de uma viagem a partir de um ponto de origem até um ponto de destino, e um conjunto de veículos, onde cada um tem uma origem e um destino. É necessário considerar algumas restrições que os passageiros possam ter, que são: o horário mínimo de saída da origem, o horário máximo de chegada até o destino, o número de passageiros que devem viajar juntos e também o valor máximo que estão dispostos a pagar. Os veículos também apresentam restrições, já que estes podem ter um horário mínimo de saída e um horário máximo de chegada. O motorista define a capacidade máxima do veículo e o preço por quilômetro rodado. Dado todas as informações e restrições, o problema consiste em formar uma rota para cada veículo com o objetivo de maximizar o número de passageiros atendidos e de minimizar os custos. O RSPMI é um problema novo na literatura e difere dos demais problemas de compartilhamento de veículos por ser o único a considerar custos compartilhados, calculando o valor total a ser pago por cada passageiro e possibilitando cada um escolher o valor máximo a ser pago. O foco do trabalho se deu no estudo e desenvolvimento de métodos que possam resolver a versão dinâmica do RSPMI, em tempo real, e em larga escala. O método proposto necessita de uma heurística que resolva o problema estático e de um algoritmo que resolva, eficientemente, o Many to Many Shortest Path Problem. Desenvolvemos heurísticas GRASP para o problema estático e usamos um algoritmo baseado em Contraction Hierarchies, o qual é muito eficiente, para lidar com os caminhos mínimos. Experimentos computacionais foram realizados usando instâncias que simulam, a partir de dados reais, uma atividade de compartilhamento de táxis na cidade de São Paulo. Em nossas simulações, os passageiros pagaram, em média, quase 30% menos do que pagariam em uma viagem privada / Abstract: In this work, we present a framework for dynamic ride-sharing. The framework has a client-server architecture. The client is used by passengers to request rides and by drivers, including vehicle owners and taxi drivers, who are willing to share their vehicles in order to reduce costs or to earn money. The server needs to solve a dynamic optimization problem which is proved to be NP-Hard. The problem, called Ride-sharing Problem with Money Incentive (RSPMI), is modeled in the following manner: at each instant of time, there are a set of passengers needing to travel from a source to a destination point and a set of vehicles, each one having a source and a destination. Passengers have constraints that need to be considered, which are: an earliest departure time, a latest arrival time, the number of passengers that will travel together and the maximum value they are willing to pay for the ride. Vehicles can have an earliest departure time and a latest arrival time, as well. They also have a maximum capacity and a price per kilometer. The problem is to compute a route for each vehicle, with the goal of maximizing the number of attended requests and minimizing the total paid by passengers. RSPMI is a new problem in the literature, differing from others ride-sharing problems, because it is the only one that considers shared costs, having a constraint which allows people to set the maximum value for the ride. The main focus of the work is to develop methods that can solve the dynamic version of the RSPMI, in real time and large scale. The proposed method needs an heuristic to solve the static problem and an algorithm to solve the Many to Many Shortest Path Problem. We developed GRASP heuristics for the static problem and used Contraction Hierarchies to deal with the shortest path problem. Computational experiments were made to evaluate our method and heuristics. We used instances based on real data that simulates a day of taxis activity in the city of Sao Paulo. In our experiments, passengers paid, on average, almost 30% less than a private ride / Mestrado / Ciência da Computação / Mestre em Ciência da Computação