Pol II docking and pausing at growth and stress genes in C. elegans.

Fluctuations in nutrient availability profoundly impact gene expression. Previous work revealed postrecruitment regulation of RNA polymerase II (Pol II) during starvation and recovery in Caenorhabditis elegans, suggesting that promoter-proximal pausing promotes rapid response to feeding. To test this hypothesis, we measured Pol II elongation genome wide by two complementary approaches and analyzed elongation in conjunction with Pol II binding and expression. We confirmed bona fide pausing during starvation and also discovered Pol II docking. Pausing occurs at active stress-response genes that become downregulated in response to feeding. In contrast, "docked" Pol II accumulates without initiating upstream of inactive growth genes that become rapidly upregulated upon feeding. Beyond differences in function and expression, these two sets of genes have different core promoter motifs, suggesting alternative transcriptional machinery. Our work suggests that growth and stress genes are both regulated postrecruitment during starvation but at initiation and elongation, respectively, coordinating gene expression with nutrient availability.

Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.