Computational problems in perfect phylogeny haplotyping: Typing without calling the allele

A haplotype is an m-long binary vector. The XOR-genotype of two haplotypes is the m-vector of their coordinate-wise XOR. We study the following problem: Given a set of XOR-genotypes, reconstruct their haplotypes so that the set of resulting haplotypes can be mapped onto a perfect phylogeny (PP) tree. The question is motivated by studying population evolution in human genetics and is a variant of the PP haplotyping problem that has received intensive attention recently. Unlike the latter problem, in which the input is '' full '' genotypes, here, we assume less informative input and so may be more economical to obtain experimentally. Building on ideas of Gusfield, we show how to solve the problem in polynomial time by a reduction to the graph realization problem. The actual haplotypes are not uniquely determined by the tree they map onto and the tree itself may or may not be unique. We show that tree uniqueness implies uniquely determined haplotypes, up to inherent degrees of freedom, and give a sufficient condition for the uniqueness. To actually determine the haplotypes given the tree, additional information is necessary. We show that two or three full genotypes suffice to reconstruct all the haplotypes and present a linear algorithm for identifying those genotypes.

Chemical and isotopic equilibrium between CO2 and CH4 in fumarolic gas discharges: Generation of CH4 in arc magmatic-hydrothermal systems

The chemical and isotopic composition of fumarolic gases emitted from Nisyros Volcano, Greece, and of a single gas sample from Vesuvio, Italy, was investigated in order to determine the origin of methane (CH,) within two subduction-related magmatic-hydrothermal environments. Apparent temperatures derived from carbon isotope partitioning between CH4 and CO2 of around 340degreesC for Nisyros and 470degreesC for Vesuvio correlate well with aquifer temperatures as measured directly and/or inferred from compositional data using the H2O-H-2-CO2-CO-CH4 geothermometer. Thermodynamic modeling reveals chemical equilibrium between CH4, CO2 and H2O implying that carbon isotope partitioning between CO2 and CH, in both systems is controlled by aquifer temperature. N-2/(3) He and CH4/(3) He ratios of Nisyros fumarolic gases are unusually low for subduction zone gases and correspond to those of midoceanic ridge environments. Accordingly, CH4 may have been primarily generated through the reduction of CO, by H, in the absence of any organic matter following a Fischer-Tropsch-type reaction. However, primary occurrence of minor amounts of thermogenic CH4 and subsequent re-equilibration with co-existing CO2 cannot be ruled out entirely- CO2/He-3 ratios and delta(13)C(CO2) values imply that the evolved CO2 either derives from a metasomatized mantle or is a mixture between two components, one outgassing from an unaltered mantle and the other released by thermal breakdown of marine carbonates. The latter may contain traces of organic matter possibly decomposing to CH4 during thermometamorphism. Copyright (C) 2004 Elsevier Ltd.

Three essays in incomplete contracts

General Introduction These three chapters, while fairly independent from each other, study economic situations in incomplete contract settings. They are the product of both the academic freedom my advisors granted me, and in this sense reflect my personal interests, and of their interested feedback. The content of each chapter can be summarized as follows: Chapter 1: Inefficient durable-goods monopolies In this chapter we study the efficiency of an infinite-horizon durable-goods monopoly model with a fmite number of buyers. We find that, while all pure-strategy Markov Perfect Equilibria (MPE) are efficient, there also exist previously unstudied inefficient MPE where high valuation buyers randomize their purchase decision while trying to benefit from low prices which are offered once a critical mass has purchased. Real time delay, an unusual monopoly distortion, is the result of this attrition behavior. We conclude that neither technological constraints nor concern for reputation are necessary to explain inefficiency in monopolized durable-goods markets. Chapter 2: Downstream mergers and producer's capacity choice: why bake a larger pie when getting a smaller slice? In this chapter we study the effect of downstream horizontal mergers on the upstream producer's capacity choice. Contrary to conventional wisdom, we find anon-monotonic relationship: horizontal mergers induce a higher upstream capacity if the cost of capacity is low, and a lower upstream capacity if this cost is high. We explain this result by decomposing the total effect into two competing effects: a change in hold-up and a change in bargaining erosion. Chapter 3: Contract bargaining with multiple agents In this chapter we study a bargaining game between a principal and N agents when the utility of each agent depends on all agents' trades with the principal. We show, using the Potential, that equilibria payoffs coincide with the Shapley value of the underlying coalitional game with an appropriately defined characteristic function, which under common assumptions coincides with the principal's equilibrium profit in the offer game. Since the problem accounts for differences in information and agents' conjectures, the outcome can be either efficient (e.g. public contracting) or inefficient (e.g. passive beliefs).

General Equilibrium Analysis. A Century after Walras

2010 marks the hundredth anniversary of the death of Léon Walras, the brilliant originator and first formaliser of general equilibrium theory - one of the pillars of modern economic theory. In advancing much derided practical solutions Walras also displayed more concern for the problems of living in a second best world than is common in modern pure theories of the invisible hand, efficient market hypothesis, DSGE macroeconomics or the thinking of some contemporary free market admirers all based on general equilibrium theory. This book brings contributions from the likes of Kenneth Arrow, Alan Kirman, Richard Posner, Amartya Sen and Robert Solow to share their thoughts and reflections on the theoretical heritage of Léon Walras. Some authors reminisce on the part they played in the development of modern general economics theory; others reflect on the crucial part played by general equilibrium in the development of macroeconomics, microeconomics, growth theory, welfare economics and the theory of justice; others still complain about the wrong path economic theory took under the influence of post 1945 developments in general equilibrium theory.