Mechanism of gallic acid biosynthesis in bacteria (Escherichia coli) and walnut (Juglans regia)

Gallic acid (GA), a key intermediate in the synthesis of plant hydrolysable tannins, is also a primary anti-inflammatory, cardio-protective agent found in wine, tea, and cocoa. In this publication, we reveal the identity of a gene and encoded protein essential for GA synthesis. Although it has long been recognized that plants, bacteria, and fungi synthesize and accumulate GA, the pathway leading to its synthesis was largely unknown. Here we provide evidence that shikimate dehydrogenase (SDH), a shikimate pathway enzyme essential for aromatic amino acid synthesis, is also required for GA production. Escherichia coli (E. coli) aroE mutants lacking a functional SDH can be complemented with the plant enzyme such that they grew on media lacking aromatic amino acids and produced GA in vitro. Transgenic Nicotiana tabacum lines expressing a Juglans regia SDH exhibited a 500% increase in GA accumulation. The J. regia and E. coli SDH was purified via overexpression in E. coli and used to measure substrate and cofactor kinetics, following reduction of NADP(+) to NADPH. Reversed-phase liquid chromatography coupled to electrospray mass spectrometry (RP-LC/ESI-MS) was used to quantify and validate GA production through dehydrogenation of 3-dehydroshikimate (3-DHS) by purified E. coli and J. regia SDH when shikimic acid (SA) or 3-DHS were used as substrates and NADP(+) as cofactor. Finally, we show that purified E. coli and J. regia SDH produced GA in vitro.

Forming Networks of Strategic Agents with Desired Topologies

Many networks such as social networks and organizational networks in global companies consist of self-interested agents. The topology of these networks often plays a crucial role in important tasks such as information diffusion and information extraction. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a stable network having that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation and a utility model that captures many key features. Based on this model, we analyze relevant network topologies and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks, wherein no node wants to delete any of its links and no two nodes would want to create a link between them.

Mechanism design for time critical and cost critical task execution via crowdsourcing

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an atomic task as well as in recruiting other agents to execute the task. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, sybil-proofness and collapse-proofness are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.

Sufficient conditions for formation of a network topology by self-interested agents

Networks such as organizational network of a global company play an important role in a variety of knowledge management and information diffusion tasks. The nodes in these networks correspond to individuals who are self-interested. The topology of these networks often plays a crucial role in deciding the ease and speed with which certain tasks can be accomplished using these networks. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a pairwise stable network with only that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation. In this model, nodes enter the network sequentially and the utility of a node captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze relevant network topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers, and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks. We also study the social welfare properties of the above topologies.