Candidate gene studies on cardiovascular traits

Cardiovascular diseases (CVD) are a major cause of death and disability in Western countries and a growing health problem in the developing world. The genetic component of both coronary heart disease (CHD) and ischemic stroke events has been established in twin studies, and the traits predisposing to CVD, such as hypertension, dyslipidemias, obesity, diabetes, and smoking behavior, are all partly hereditary. Better understanding of the pathophysiology of CVD-related traits could help to target disease prevention and clinical treatment to individuals at an especially high disease risk and provide novel pharmaceutical interventions. This thesis aimed to clarify the genetic background of CVD at a population level using large Nordic population cohorts and a candidate gene approach. The first study concentrated on the allelic diversity of the thrombomodulin (THBD) gene in two Finnish cohorts, FINRISK-92 and FINRISK-97. The results from this study implied that THBD variants do not substantially contribute to CVD risk. In the second study, three other candidate genes were added to the analyses. The study investigated the epistatic effects of coagulation factor V (F5), intercellular adhesion molecule -1 (ICAM1), protein C (PROC), and THBD in the same FINRISK cohorts. The results were encouraging; we were able to identify several single SNPs and SNP combinations associating with CVD and mortality. Interestingly, THBD variants appeared in the associating SNP combinations despite the negative results from Study I, suggesting that THBD contributes to CVD through gene-gene interactions. In the third study, upstream transcription factor -1 (USF1) was analyzed in a cohort of Swedish men. USF1 was associated with metabolic syndrome, characterized by accumulation of different CVD risk factors. A putative protective and a putative risk variant were identified. A direct association with CVD was not observed. The longitudinal nature of the study also clarified the effect of USF1 variants on CVD risk factors followed in four examinations throughout adulthood. The three studies provided valuable information on the study of complex traits, highlighting the use of large study samples, the importance of replication, and the full coverage of the major allelic variants of the target genes to assure reliable findings. Although the genetic basis of coronary heart disease and ischemic stroke remains unknown, single genetic findings may facilitate the recognition of high-risk subgroups.

Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).