| 1. |
- Björklund, Andreas, et al.
(författare)
-
Fast Witness Extraction using a Decision Oracle
- 2014
-
Ingår i: Algorithms - ESA 2014/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662447772 ; 8737, s. 149-160
-
Konferensbidrag (refereegranskat)abstract
- The gist of many (NP-)hard combinatorial problems is to decide whether a universe of n elements contains a witness consisting of k elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for large values of n. By relying on techniques from combinatorial group testing, we demonstrate that a witness may be extracted with O(klogn) queries to either a deterministic or a randomized set inclusion oracle with one-sided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebra-based FPT algorithms are practical, in particular in the setting of the k-path problem. Also discussed are engineering issues such as optimizing finite field arithmetic.
|
|
| 2. |
- Björklund, Erik, et al.
(författare)
-
Secondary prevention medications after coronary artery bypass grafting and long-term survival : a population-based longitudinal study from the SWEDEHEART registry.
- 2019
-
Ingår i: European Heart Journal. - : Oxford University Press. - 0195-668X .- 1522-9645. ; 41:17, s. 1653-1661
-
Tidskriftsartikel (refereegranskat)abstract
- AIMS: To evaluate the long-term use of secondary prevention medications [statins, β-blockers, renin-angiotensin-aldosterone system (RAAS) inhibitors, and platelet inhibitors] after coronary artery bypass grafting (CABG) and the association between medication use and mortality.METHODS AND RESULTS: All patients who underwent isolated CABG in Sweden from 2006 to 2015 and survived at least 6 months after discharge were included (n = 28 812). Individual patient data from SWEDEHEART and other mandatory nationwide registries were merged. Multivariable Cox regression models using time-updated data on dispensed prescriptions were used to assess associations between medication use and long-term mortality. Statins were dispensed to 93.9% of the patients 6 months after discharge and to 77.3% 8 years later. Corresponding figures for β-blockers were 91.0% and 76.4%, for RAAS inhibitors 72.9% and 65.9%, and for platelet inhibitors 93.0% and 79.8%. All medications were dispensed less often to patients ≥75 years. Treatment with statins [hazard ratio (HR) 0.56, 95% confidence interval (95% CI) 0.52-0.60], RAAS inhibitors (HR 0.78, 95% CI 0.73-0.84), and platelet inhibitors (HR 0.74, 95% CI 0.69-0.81) were individually associated with lower mortality risk after adjustment for age, gender, comorbidities, and use of other secondary preventive drugs (all P < 0.001). There was no association between β-blockers and mortality risk (HR 0.97, 95% CI 0.90-1.06; P = 0.54).CONCLUSION: The use of secondary prevention medications after CABG was high early after surgery but decreased significantly over time. The results of this observational study, with inherent risk of selection bias, suggest that treatment with statins, RAAS inhibitors, and platelet inhibitors is essential after CABG whereas the routine use of β-blockers may be questioned.
|
|
| 3. |
- Aldrin-Kirk, Patrick, et al.
(författare)
-
A novel two-factor monosynaptic TRIO tracing method for assessment of circuit integration of hESC-derived dopamine transplants
- 2022
-
Ingår i: Stem Cell Reports. - : Elsevier BV. - 2213-6711. ; 17:1, s. 159-172
-
Tidskriftsartikel (refereegranskat)abstract
- Transplantation in Parkinson's disease using human embryonic stem cell (hESC)-derived dopaminergic (DA) neurons is a promising future treatment option. However, many of the mechanisms that govern their differentiation, maturation, and integration into the host circuitry remain elusive. Here, we engrafted hESCs differentiated toward a ventral midbrain DA phenotype into the midbrain of a preclinical rodent model of Parkinson's disease. We then injected a novel DA-neurotropic retrograde MNM008 adeno-associated virus vector capsid, into specific DA target regions to generate starter cells based on their axonal projections. Using monosynaptic rabies-based tracing, we demonstrated for the first time that grafted hESC-derived DA neurons receive distinctly different afferent inputs depending on their projections. The similarities to the host DA system suggest a previously unknown directed circuit integration. By evaluating the differential host-to-graft connectivity based on projection patterns, this novel approach offers a tool to answer outstanding questions regarding the integration of grafted hESC-derived DA neurons.
|
|
| 4. |
- Aldrin-Kirk, Patrick, et al.
(författare)
-
Chemogenetic modulation of cholinergic interneurons reveals their regulating role on the direct and indirect output pathways from the striatum
- 2018
-
Ingår i: Neurobiology of Disease. - : Elsevier BV. - 0969-9961. ; 109, s. 148-162
-
Tidskriftsartikel (refereegranskat)abstract
- The intricate balance between dopaminergic and cholinergic neurotransmission in the striatum has been thoroughly difficult to characterize. It was initially described as a seesaw with a competing function of dopamine versus acetylcholine. Recent technical advances however, have brought this view into question suggesting that the two systems work rather in concert with the cholinergic interneurons (ChIs) driving dopamine release. In this study, we have utilized two transgenic Cre-driver rat lines, a choline acetyl transferase ChAT-Cre transgenic rat and a novel double-transgenic tyrosine hydroxylase TH-Cre/ChAT-Cre rat to further elucidate the role of striatal ChIs in normal motor function and in Parkinson's disease. Here we show that selective and reversible activation of ChIs using chemogenetic (DREADD) receptors increases locomotor function in intact rats and potentiate the therapeutic effect of L-DOPA in the rats with lesions of the nigral dopamine system. However, the potentiation of the L-DOPA effect is accompanied by an aggravation of L-DOPA induced dyskinesias (LIDs). These LIDs appear to be driven primarily through the indirect striato-pallidal pathway since the same effect can be induced by the D2 agonist Quinpirole. Taken together, the results highlight the intricate regulation of balance between the two output pathways from the striatum orchestrated by the ChIs.
|
|
| 5. |
- Aldrin-Kirk, Patrick, et al.
(författare)
-
DREADD Modulation of Transplanted DA Neurons Reveals a Novel Parkinsonian Dyskinesia Mechanism Mediated by the Serotonin 5-HT6 Receptor
- 2016
-
Ingår i: Neuron. - : Elsevier BV. - 0896-6273. ; 90:5, s. 955-968
-
Tidskriftsartikel (refereegranskat)abstract
- Transplantation of DA neurons is actively pursued as a restorative therapy in Parkinson's disease (PD). Pioneering clinical trials using transplants of fetal DA neuroblasts have given promising results, although a number of patients have developed graft-induced dyskinesias (GIDs), and the mechanism underlying this troublesome side effect is still unknown. Here we have used a new model where the activity of the transplanted DA neurons can be selectively modulated using a bimodal chemogenetic (DREADD) approach, allowing either enhancement or reduction of the therapeutic effect. We show that exclusive activation of a cAMP-linked (Gs-coupled) DREADD or serotonin 5-HT6 receptor, located on the grafted DA neurons, is sufficient to induce GIDs. These findings establish a mechanistic link between the 5-HT6 receptor, intracellular cAMP, and GIDs in transplanted PD patients. This effect is thought to be mediated through counteraction of the D2 autoreceptor feedback inhibition, resulting in a dysplastic DA release from the transplant.
|
|
| 6. |
- Baranowska, Julia, et al.
(författare)
-
Associations between medical therapy after surgical aortic valve replacement for aortic stenosis and long-term mortality: a report from the SWEDEHEART registry.
- 2022
-
Ingår i: European heart journal. Cardiovascular pharmacotherapy. - : Oxford University Press (OUP). - 2055-6837 .- 2055-6845. ; 8:8, s. 837-846
-
Tidskriftsartikel (refereegranskat)abstract
- The association between use of statins, renin-angiotensin system (RAS) inhibitors and/or β-blockers and long-term mortality in patients with aortic stenosis who underwent surgical aortic valve replacement (SAVR) is unknown.All patients with aortic stenosis who underwent isolated first time SAVR in Sweden from 2006 to 2017 and survived six months after discharge were included. Individual patient data from four mandatory nationwide registries were merged. Cox proportional hazards models, with time-updated data on medication status and adjusted for age, sex, comorbidities, type of prosthesis, and year of surgery, were used to investigate associations between dispensed statins, RAS inhibitors, and β-blockers, and all-cause mortality. In total, 9553 patients were included, and median follow-up time was 4.9 years (range 0-11); 1738 patients (18.2%) died during follow-up. Statins were dispensed to 49.1% and 49.0% of the patients within six months of discharge from hospital and after ten years, respectively. Corresponding figures were 51.4% and 53.9% for RAS inhibitors, and 79.3% and 60.7% for β-blockers. Ongoing treatment was associated with lower mortality risk for statins [adjusted hazard ratio (aHR) 0.67 (95% confidence interval 0.60-0.74), p<0.001] and RAS inhibitors [aHR 0.84 (0.76-0.93), p<0.001] but not for β-blockers [aHR 1.17 (1.05-1.30), p=0.004]. The associations were robust in subgroups based on age, sex, and comorbidities (p for interactions>0.05).The results of this large population-based real-world study support the use of statins and RAS inhibitors for patients who underwent SAVR due to aortic stenosis.
|
|
| 7. |
- Beziat, Vivien, et al.
(författare)
-
NK cell responses to cytomegalovirus infection lead to stable imprints in the human KIR repertoire and involve activating KIRs
- 2013
-
Ingår i: Blood. - : American Society of Hematology. - 0006-4971 .- 1528-0020. ; 121:14, s. 2678-2688
-
Tidskriftsartikel (refereegranskat)abstract
- Human natural killer (NK) cells are functionally regulated by killer cell immunoglobulin-like receptors (KIRs) and their interactions with HLA class I molecules. As KIR expression in a given NK cell is genetically hard-wired, we hypothesized that KIR repertoire perturbations reflect expansions of unique NK-cell subsets and may be used to trace adaptation of the NK-cell compartment to virus infections. By determining the human KIR-ome at a single-cell level in more than 200 donors, we were able to analyze the magnitude of NK cell adaptation to virus infections in healthy individuals. Strikingly, infection with human cytomegalovirus (CMV), but not with other common herpesviruses, induced expansion and differentiation of KIR-expressing NK cells, visible as stable imprints in the repertoire. Education by inhibitory KIRs promoted the clonal-like expansion of NK cells, causing a bias for self-specific inhibitory KIRs. Furthermore, our data revealed a unique contribution of activating KIRs (KIR2DS4, KIR2DS2, or KIR3DS1), in addition to NKG2C, in the expansion of human NK cells. These results provide new insight into the diversity of KIR repertoire and its adaptation to virus infection, suggesting a role for both activating and inhibitory KIRs in immunity to CMV infection.
|
|
| 8. |
- Björklund, Andreas, et al.
(författare)
-
A faster hafnian formula for complex matrices and its benchmarking on a supercomputer
- 2019
-
Ingår i: ACM Journal of Experimental Algorithmics. - : Association for Computing Machinery (ACM). - 1084-6654. ; 24:1
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of n × n complex matrices run in O(n32n/2) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 × 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 × 100 matrix.
|
|
| 9. |
- Björklund, Andreas
(författare)
-
Algorithmic Bounds for Presumably Hard Combinatorial Problems
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. Our results include I a) There is a polynomial--time algorithm always finding a path of length Omega((log n/ log log n)^2) in directed Hamiltonian graphs of constant bounded degree on n vertices. In undirected graphs on $n$ vertices with a long path of length L we give a polynomial--time algorithm finding Omega((log L/ log log L)^2) long paths. The technique used is a novel graph decomposition which inspired Hal Gabow to find the strongest approximation algorithm for Longest Path in undirected graphs known to date. I b) You cannot always in polynomial time find simple paths of length f(n) log^2 n or cycles of length f(n)log n for any non-decreasing function f(n) which is omega(1) and computable in subexponential time in directed Hamiltonian graphs of constant bounded degree on n vertices, unless there are 2^{o(n)} time deterministic algorithms for n-variable 3SAT. II a) There is a PTAS for MAXCUT on d-regular unweighted graphs on n vertices, containing O(d^4 log n) simple 4-cycles, for $d$ of omega(sqrt{n log n}). In particular, there is always a PTAS for d of Omega(n/log n) regardless of the number of 4-cycles. Moreover, MAXkSAT on n variables for constant k can be approximated in polynomial time with an absolute error of (epsilon+o(1))n^ksqrt{log log n/log n} for any fixed epsilon>0. The techniques used are low rank approximations, exhaustive search in few dimensions, and linear programming. II b) There is no PTAS for MAXCUT on unweighted graphs on n vertices of average degree delta for any delta less than n/(log n(log log n)^{omega(1)}), unless there are 2^{o(n)} time randomized algorithms for n-variable 3SAT. III) For any family S of subsets S_1,...,S_m of a ground set U of size n it is possible to count the number of covers of U in k pieces from S in time 2^nn^{O(1)} for any k as long as S is enumerable in that time bound. In particular the chromatic polynomial of a graph can be computed in time O(2^nn^3). The Chromatic Number in an n-vertex graph can be computed in time O(2.2461^n) using only polynomial space. The technique used is counting over an inclusion--exclusion formula.
|
|
| 10. |
- Björklund, Andreas, et al.
(författare)
-
Approximate counting of K-paths : Deterministic and in polynomial space
- 2019
-
Ingår i: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. - 9783959771092 ; 132
-
Konferensbidrag (refereegranskat)abstract
- A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊−2)-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊−1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊−2)-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4k+O(√k(log2 k+log2 ∊−1))m log n-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. Additionally, we present a randomized 4k+O(log k(log k+log ∊−1))m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4k+o(k)m whenever ∊−1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊−1 = 2o(k 4 ) and 1 ∊−1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(1)-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.
|
|
