Approximation Algorithms for Network Design and Orienteering

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for single-sink network design problems with high vertex-connectivity requirements; we give an O(k log n)-approximation for the problem of k-connecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct low-cost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertex-disjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a low-cost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salesperson-like problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)-approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning.

Microfluidic platforms for the characterization of in meso membrane protein crystallization

Membrane proteins, which reside in the membranes of cells, play a critical role in many important biological processes including cellular signaling, immune response, and material and energy transduction. Because of their key role in maintaining the environment within cells and facilitating intercellular interactions, understanding the function of these proteins is of tremendous medical and biochemical significance. Indeed, the malfunction of membrane proteins has been linked to numerous diseases including diabetes, cirrhosis of the liver, cystic fibrosis, cancer, Alzheimer's disease, hypertension, epilepsy, cataracts, tubulopathy, leukodystrophy, Leigh syndrome, anemia, sensorineural deafness, and hypertrophic cardiomyopathy.1-3 However, the structure of many of these proteins and the changes in their structure that lead to disease-related malfunctions are not well understood. Additionally, at least 60% of the pharmaceuticals currently available are thought to target membrane proteins, despite the fact that their exact mode of operation is not known.4-6 Developing a detailed understanding of the function of a protein is achieved by coupling biochemical experiments with knowledge of the structure of the protein. Currently the most common method for obtaining three-dimensional structure information is X-ray crystallography. However, no a priori methods are currently available to predict crystallization conditions for a given protein.7-14 This limitation is currently overcome by screening a large number of possible combinations of precipitants, buffer, salt, and pH conditions to identify conditions that are conducive to crystal nucleation and growth.7,9,11,15-24 Unfortunately, these screening efforts are often limited by difficulties associated with quantity and purity of available protein samples. While the two most significant bottlenecks for protein structure determination in general are the (i) obtaining sufficient quantities of high quality protein samples and (ii) growing high quality protein crystals that are suitable for X-ray structure determination,7,20,21,23,25-47 membrane proteins present additional challenges. For crystallization it is necessary to extract the membrane proteins from the cellular membrane. However, this process often leads to denaturation. In fact, membrane proteins have proven to be so difficult to crystallize that of the more than 66,000 structures deposited in the Protein Data Bank,48 less than 1% are for membrane proteins, with even fewer present at high resolution (< 2Å)4,6,49 and only a handful are human membrane proteins.49 A variety of strategies including detergent solubilization50-53 and the use of artificial membrane-like environments have been developed to circumvent this challenge.43,53-55 In recent years, the use of a lipidic mesophase as a medium for crystallizing membrane proteins has been demonstrated to increase success for a wide range of membrane proteins, including human receptor proteins.54,56-62 This in meso method for membrane protein crystallization, however, is still by no means routine due to challenges related to sample preparation at sub-microliter volumes and to crystal harvesting and X-ray data collection. This dissertation presents various aspects of the development of a microfluidic platform to enable high throughput in meso membrane protein crystallization at a level beyond the capabilities of current technologies. Microfluidic platforms for protein crystallization and other lab-on-a-chip applications have been well demonstrated.9,63-66 These integrated chips provide fine control over transport phenomena and the ability to perform high throughput analyses via highly integrated fluid networks. However, the development of microfluidic platforms for in meso protein crystallization required the development of strategies to cope with extremely viscous and non-Newtonian fluids. A theoretical treatment of highly viscous fluids in microfluidic devices is presented in Chapter 3, followed by the application of these strategies for the development of a microfluidic mixer capable of preparing a mesophase sample for in meso crystallization at a scale of less than 20 nL in Chapter 4. This approach was validated with the successful on chip in meso crystallization of the membrane protein bacteriorhodopsin. In summary, this is the first report of a microfluidic platform capable of performing in meso crystallization on-chip, representing a 1000x reduction in the scale at which mesophase trials can be prepared. Once protein crystals have formed, they are typically harvested from the droplet they were grown in and mounted for crystallographic analysis. Despite the high throughput automation present in nearly all other aspects of protein structure determination, the harvesting and mounting of crystals is still largely a manual process. Furthermore, during mounting the fragile protein crystals can potentially be damaged, both from physical and environmental shock. To circumvent these challenges an X-ray transparent microfluidic device architecture was developed to couple the benefits of scale, integration, and precise fluid control with the ability to perform in situ X-ray analysis (Chapter 5). This approach was validated successfully by crystallization and subsequent on-chip analysis of the soluble proteins lysozyme, thaumatin, and ribonuclease A and will be extended to microfluidic platforms for in meso membrane protein crystallization. The ability to perform in situ X-ray analysis was shown to provide extremely high quality diffraction data, in part as a result of not being affected by damage due to physical handling of the crystals. As part of the work described in this thesis, a variety of data collection strategies for in situ data analysis were also tested, including merging of small slices of data from a large number of crystals grown on a single chip, to allow for diffraction analysis at biologically relevant temperatures. While such strategies have been applied previously,57,59,61,67 they are potentially challenging when applied via traditional methods due to the need to grow and then mount a large number of crystals with minimal crystal-to-crystal variability. The integrated nature of microfluidic platforms easily enables the generation of a large number of reproducible crystallization trials. This, coupled with in situ analysis capabilities has the potential of being able to acquire high resolution structural data of proteins at biologically relevant conditions for which only small crystals, or crystals which are adversely affected by standard cryocooling techniques, could be obtained (Chapters 5 and 6). While the main focus of protein crystallography is to obtain three-dimensional protein structures, the results of typical experiments provide only a static picture of the protein. The use of polychromatic or Laue X-ray diffraction methods enables the collection of time resolved structural information. These experiments are very sensitive to crystal quality, however, and often suffer from severe radiation damage due to the intense polychromatic X-ray beams. Here, as before, the ability to perform in situ X-ray analysis on many small protein crystals within a microfluidic crystallization platform has the potential to overcome these challenges. An automated method for collecting a "single-shot" of data from a large number of crystals was developed in collaboration with the BioCARS team at the Advanced Photon Source at Argonne National Laboratory (Chapter 6). The work described in this thesis shows that, even more so than for traditional structure determination efforts, the ability to grow and analyze a large number of high quality crystals is critical to enable time resolved structural studies of novel proteins. In addition to enabling X-ray crystallography experiments, the development of X-ray transparent microfluidic platforms also has tremendous potential to answer other scientific questions, such as unraveling the mechanism of in meso crystallization. For instance, the lipidic mesophases utilized during in meso membrane protein crystallization can be characterized by small angle X-ray diffraction analysis. Coupling in situ analysis with microfluidic platforms capable of preparing these difficult mesophase samples at very small volumes has tremendous potential to enable the high throughput analysis of these systems on a scale that is not reasonably achievable using conventional sample preparation strategies (Chapter 7). In collaboration with the LS-CAT team at the Advanced Photon Source, an experimental station for small angle X-ray analysis coupled with the high quality visualization capabilities needed to target specific microfluidic samples on a highly integrated chip is under development. Characterizing the phase behavior of these mesophase systems and the effects of various additives present in crystallization trials is key for developing an understanding of how in meso crystallization occurs. A long term goal of these studies is to enable the rational design of in meso crystallization experiments so as to avoid or limit the need for high throughput screening efforts. In summary, this thesis describes the development of microfluidic platforms for protein crystallization with in situ analysis capabilities. Coupling the ability to perform in situ analysis with the small scale, fine control, and the high throughput nature of microfluidic platforms has tremendous potential to enable a new generation of crystallographic studies and facilitate the structure determination of important biological targets. The development of platforms for in meso membrane protein crystallization is particularly significant because they enable the preparation of highly viscous mixtures at a previously unachievable scale. Work in these areas is ongoing and has tremendous potential to improve not only current the methods of protein crystallization and crystallography, but also to enhance our knowledge of the structure and function of proteins which could have a significant scientific and medical impact on society as a whole. The microfluidic technology described in this thesis has the potential to significantly advance our understanding of the structure and function of membrane proteins, thereby aiding the elucidation of human biology, the development of pharmaceuticals with fewer side effects for a wide range of diseases. References (1) Quick, M.; Javitch, J. A. P Natl Acad Sci USA 2007, 104, 3603. (2) Trubetskoy, V. S.; Burke, T. J. Am Lab 2005, 37, 19. (3) Pecina, P.; Houstkova, H.; Hansikova, H.; Zeman, J.; Houstek, J. Physiol Res 2004, 53, S213. (4) Arinaminpathy, Y.; Khurana, E.; Engelman, D. M.; Gerstein, M. B. Drug Discovery Today 2009, 14, 1130. (5) Overington, J. P.; Al-Lazikani, B.; Hopkins, A. L. Nat Rev Drug Discov 2006, 5, 993. (6) Dauter, Z.; Lamzin, V. S.; Wilson, K. S. Current Opinion in Structural Biology 1997, 7, 681. (7) Hansen, C.; Quake, S. R. Current Opinion in Structural Biology 2003, 13, 538. (8) Govada, L.; Carpenter, L.; da Fonseca, P. C. A.; Helliwell, J. R.; Rizkallah, P.; Flashman, E.; Chayen, N. E.; Redwood, C.; Squire, J. M. J Mol Biol 2008, 378, 387. (9) Hansen, C. L.; Skordalakes, E.; Berger, J. M.; Quake, S. R. P Natl Acad Sci USA 2002, 99, 16531. (10) Leng, J.; Salmon, J.-B. Lab Chip 2009, 9, 24. (11) Zheng, B.; Gerdts, C. J.; Ismagilov, R. F. Current Opinion in Structural Biology 2005, 15, 548. (12) Lorber, B.; Delucas, L. J.; Bishop, J. B. J Cryst Growth 1991, 110, 103. (13) Talreja, S.; Perry, S. L.; Guha, S.; Bhamidi, V.; Zukoski, C. F.; Kenis, P. J. A. The Journal of Physical Chemistry B 2010, 114, 4432. (14) Chayen, N. E. Current Opinion in Structural Biology 2004, 14, 577. (15) He, G. W.; Bhamidi, V.; Tan, R. B. H.; Kenis, P. J. A.; Zukoski, C. F. Cryst Growth Des 2006, 6, 1175. (16) Zheng, B.; Tice, J. D.; Roach, L. S.; Ismagilov, R. F. Angew Chem Int Edit 2004, 43, 2508. (17) Li, L.; Mustafi, D.; Fu, Q.; Tereshko, V.; Chen, D. L. L.; Tice, J. D.; Ismagilov, R. F. P Natl Acad Sci USA 2006, 103, 19243. (18) Song, H.; Chen, D. L.; Ismagilov, R. F. Angew Chem Int Edit 2006, 45, 7336. (19) van der Woerd, M.; Ferree, D.; Pusey, M. Journal of Structural Biology 2003, 142, 180. (20) Ng, J. D.; Gavira, J. A.; Garcia-Ruiz, J. M. Journal of Structural Biology 2003, 142, 218. (21) Talreja, S.; Kenis, P. J. A.; Zukoski, C. F. Langmuir 2007, 23, 4516. (22) Hansen, C. L.; Quake, S. R.; Berger, J. M. US, 2007. (23) Newman, J.; Fazio, V. J.; Lawson, B.; Peat, T. S. Cryst Growth Des 2010, 10, 2785. (24) Newman, J.; Xu, J.; Willis, M. C. Acta Crystallographica Section D 2007, 63, 826. (25) Collingsworth, P. D.; Bray, T. L.; Christopher, G. K. J Cryst Growth 2000, 219, 283. (26) Durbin, S. D.; Feher, G. Annu Rev Phys Chem 1996, 47, 171. (27) Talreja, S.; Kim, D. Y.; Mirarefi, A. Y.; Zukoski, C. F.; Kenis, P. J. A. J Appl Crystallogr 2005, 38, 988. (28) Yoshizaki, I.; Nakamura, H.; Sato, T.; Igarashi, N.; Komatsu, H.; Yoda, S. J Cryst Growth 2002, 237, 295. (29) Anderson, M. J.; Hansen, C. L.; Quake, S. R. P Natl Acad Sci USA 2006, 103, 16746. (30) Hansen, C. L.; Sommer, M. O. A.; Quake, S. R. P Natl Acad Sci USA 2004, 101, 14431. (31) Lounaci, M.; Rigolet, P.; Abraham, C.; Le Berre, M.; Chen, Y. Microelectron Eng 2007, 84, 1758. (32) Zheng, B.; Roach, L. S.; Ismagilov, R. F. J Am Chem Soc 2003, 125, 11170. (33) Zhou, X.; Lau, L.; Lam, W. W. L.; Au, S. W. N.; Zheng, B. Anal. Chem. 2007. (34) Cherezov, V.; Caffrey, M. J Appl Crystallogr 2003, 36, 1372. (35) Qutub, Y.; Reviakine, I.; Maxwell, C.; Navarro, J.; Landau, E. M.; Vekilov, P. G. J Mol Biol 2004, 343, 1243. (36) Rummel, G.; Hardmeyer, A.; Widmer, C.; Chiu, M. L.; Nollert, P.; Locher, K. P.; Pedruzzi, I.; Landau, E. M.; Rosenbusch, J. P. Journal of Structural Biology 1998, 121, 82. (37) Gavira, J. A.; Toh, D.; Lopez-Jaramillo, J.; Garcia-Ruiz, J. M.; Ng, J. D. Acta Crystallogr D 2002, 58, 1147. (38) Stevens, R. C. Current Opinion in Structural Biology 2000, 10, 558. (39) Baker, M. Nat Methods 2010, 7, 429. (40) McPherson, A. In Current Topics in Membranes, Volume 63; Volume 63 ed.; DeLucas, L., Ed.; Academic Press: 2009, p 5. (41) Gabrielsen, M.; Gardiner, A. T.; Fromme, P.; Cogdell, R. J. In Current Topics in Membranes, Volume 63; Volume 63 ed.; DeLucas, L., Ed.; Academic Press: 2009, p 127. (42) Page, R. In Methods in Molecular Biology: Structural Proteomics - High Throughput Methods; Kobe, B., Guss, M., Huber, T., Eds.; Humana Press: Totowa, NJ, 2008; Vol. 426, p 345. (43) Caffrey, M. Ann Rev Biophys 2009, 38, 29. (44) Doerr, A. Nat Methods 2006, 3, 244. (45) Brostromer, E.; Nan, J.; Li, L.-F.; Su, X.-D. Biochemical and Biophysical Research Communications 2009, 386, 634. (46) Li, G.; Chen, Q.; Li, J.; Hu, X.; Zhao, J. Anal Chem 2010, 82, 4362. (47) Jia, Y.; Liu, X.-Y. The Journal of Physical Chemistry B 2006, 110, 6949. (48) RCSB Protein Data Bank. http://www.rcsb.org/ (July 11, 2010). (49) Membrane Proteins of Known 3D Structure. http://blanco.biomol.uci.edu/Membrane_Proteins_xtal.html (July 11, 2010). (50) Michel, H. Trends Biochem Sci 1983, 8, 56. (51) Rosenbusch, J. P. Journal of Structural Biology 1990, 104, 134. (52) Garavito, R. M.; Picot, D. Methods 1990, 1, 57. (53) Kulkarni, C. V. 2010; Vol. 12, p 237. (54) Landau, E. M.; Rosenbusch, J. P. P Natl Acad Sci USA 1996, 93, 14532. (55) Pebay-Peyroula, E.; Rummel, G.; Rosenbusch, J. P.; Landau, E. M. Science 1997, 277, 1676. (56) Cherezov, V.; Liu, W.; Derrick, J. P.; Luan, B.; Aksimentiev, A.; Katritch, V.; Caffrey, M. Proteins: Structure, Function, and Bioinformatics 2008, 71, 24. (57) Cherezov, V.; Rosenbaum, D. M.; Hanson, M. A.; Rasmussen, S. G. F.; Thian, F. S.; Kobilka, T. S.; Choi, H. J.; Kuhn, P.; Weis, W. I.; Kobilka, B. K.; Stevens, R. C. Science 2007, 318, 1258. (58) Cherezov, V.; Yamashita, E.; Liu, W.; Zhalnina, M.; Cramer, W. A.; Caffrey, M. J Mol Biol 2006, 364, 716. (59) Jaakola, V. P.; Griffith, M. T.; Hanson, M. A.; Cherezov, V.; Chien, E. Y. T.; Lane, J. R.; IJzerman, A. P.; Stevens, R. C. Science 2008, 322, 1211. (60) Rosenbaum, D. M.; Cherezov, V.; Hanson, M. A.; Rasmussen, S. G. F.; Thian, F. S.; Kobilka, T. S.; Choi, H. J.; Yao, X. J.; Weis, W. I.; Stevens, R. C.; Kobilka, B. K. Science 2007, 318, 1266. (61) Wacker, D.; Fenalti, G.; Brown, M. A.; Katritch, V.; Abagyan, R.; Cherezov, V.; Stevens, R. C. J Am Chem Soc 2010, 132, 11443. (62) Höfer, N.; Aragão, D.; Caffrey, M. Biophys J 2010, 99, L23. (63) Li, L.; Ismagilov, R. F. Ann Rev Biophys 2010. (64) Pal, R.; Yang, M.; Lin, R.; Johnson, B. N.; Srivastava, N.; Razzacki, S. Z.; Chomistek, K. J.; Heldsinger, D. C.; Haque, R. M.; Ugaz, V. M.; Thwar, P. K.; Chen, Z.; Alfano, K.; Yim, M. B.; Krishnan, M.; Fuller, A. O.; Larson, R. G.; Burke, D. T.; Burns, M. A. Lab Chip 2005, 5, 1024. (65) Jayashree, R. S.; Gancs, L.; Choban, E. R.; Primak, A.; Natarajan, D.; Markoski, L. J.; Kenis, P. J. A. J Am Chem Soc 2005, 127, 16758. (66) Wootton, R. C. R.; deMello, A. J. Chem Commun 2004, 266. (67) McPherson, A. J Appl Crystallogr 2000, 33, 397.