Browsing by Subject "COMPLEXITY"

Sort by: Order: Results:

Now showing items 1-20 of 37
  • Kangas, Kustaa; Koivisto, Mikko; Salonen, Sami (2020)
    We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time $${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constant t; the notation $${\tilde{O}}$$O~hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.
  • MacGregor-Fors, Ian; Falfan, Ina; Garcia-Arroyo, Michelle; Lemoine-Rodriguez, Richard; Gomez-Martinez, Miguel A.; Marin-Gomez, Oscar H.; Perez-Maqueo, Octavio; Equihua, Miguel (2022)
    To tackle urban heterogeneity and complexity, several indices have been proposed, commonly aiming to provide information for decision-makers. In this study, we propose a novel and customizable procedure for quantifying urban ecosystem integrity. Based on a citywide approach, we developed an easy-to-use index that contrasts physical and biological variables of urban ecosystems with a given reference system. The Urban Ecosystem Integrity Index (UEII) is the sum of the averages from the variables that make up its intensity of urbanization and biological components. We applied the UEII in a Mexican tropical city using land surface temperature, built cover, and the richness of native plants and birds. The overall ecosystem integrity of the city, having montane cloud, tropical dry, and temperate forests as reference systems, was low (-0.34 +/- SD 0.32), showing that, beyond its biodiverse greenspace network, the built-up structure highly differs from the ecosystems of reference. The UEII showed to be a flexible and easy-to-calculate tool to evaluate ecosystem integrity for cities, allowing for comparisons between or among cities, as well as the sectors/regions within cities. If used properly, the index could become a useful tool for decision making and resource allocation at a city level.
  • Silva, M; Pratas, D; Pinho, AJ (2021)
    Recently, the scientific community has witnessed a substantial increase in the generation of protein sequence data, triggering emergent challenges of increasing importance, namely efficient storage and improved data analysis. For both applications, data compression is a straightforward solution. However, in the literature, the number of specific protein sequence compressors is relatively low. Moreover, these specialized compressors marginally improve the compression ratio over the best general-purpose compressors. In this paper, we present AC2, a new lossless data compressor for protein (or amino acid) sequences. AC2 uses a neural network to mix experts with a stacked generalization approach and individual cache-hash memory models to the highest-context orders. Compared to the previous compressor (AC), we show gains of 2-9% and 6-7% in reference-free and reference-based modes, respectively. These gains come at the cost of three times slower computations. AC2 also improves memory usage against AC, with requirements about seven times lower, without being affected by the sequences' input size. As an analysis application, we use AC2 to measure the similarity between each SARS-CoV-2 protein sequence with each viral protein sequence from the whole UniProt database. The results consistently show higher similarity to the pangolin coronavirus, followed by the bat and human coronaviruses, contributing with critical results to a current controversial subject. AC2 is available for free download under GPLv3 license.
  • Baumeister, Dorothea; Järvisalo, Matti; Neugebauer, Daniel; Niskanen, Andreas; Rothe, Jörg (2021)
    A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.
  • Morris, Rebecca J.; Gripenberg, Sofia; Lewis, Owen T.; Roslin, Tomas (2014)
  • Durand, Arnaud; Hannula, Miika; Kontinen, Juha; Meier, Arne; Virtema, Jonni (2018)
    We define a variant of team semantics called multiteam semantics based on multisets and study the properties of various logics in this framework. In particular, we define natural probabilistic versions of inclusion and independence atoms and certain approximation operators motivated by approximate dependence atoms of Vaananen.
  • Wirz, Lukas; Schwerdtfeger, Peter; Avery, James (2021)
    We describe a method for computing the number of Hamilton cycles in cubic polyhedral graphs. The Hamilton cycle counts are expressed in terms of a finite-state machine, and can be written as a matrix expression. In the special case of polyhedral graphs with repeating layers, the state machines become cyclic, greatly simplifying the expression for the exact Hamilton cycle counts, and let us calculate the exact Hamilton cycle counts for infinite series of graphs that are generated by repeating the layers. For some series, these reduce to closed form expressions, valid for the entire infinite series. When this is not possible, evaluating the number of Hamiltonian cycles admitted by the series' k-layer member is found by computing a (k - 1)th matrix power, requiring O(log(2)(k)) matrix-matrix multiplications. We demonstrate our technique for the two infinite series of fullerene nanotubes with the smallest caps. In addition to exact closed form and matrix expressions, we provide approximate exponential formulas for the number of Hamilton cycles.
  • Hagolani, Pascal F.; Zimm, Roland; Marin-Riera, Miquel; Salazar-Ciudad, Isaac (2019)
    Embryonic development involves gene networks, extracellular signaling, cell behaviors (cell division, adhesion, etc.) and mechanical interactions. How should these be coordinated to lead to complex and robust morphologies? To explore this question, we randomly wired genes and cell behaviors into a huge number of networks in EmbryoMaker. EmbryoMaker is a computational model of animal development that simulates how the 3D positions of cells, i.e. morphology, change over time due to such networks. We found that any gene network can lead to complex morphologies if this activates cell behaviors over large regions of the embryo. Importantly, however, for such complex morphologies to be robust to noise, gene networks should include cell signaling that compartmentalizes the embryo into small regions where cell behaviors are regulated differently. If, instead, cell behaviors are equally regulated over large regions, complex but non-robust morphologies arise. We explain how compartmentalization enhances robustness and why it is a general feature of animal development. Our results are consistent with theories proposing that robustness evolved by the co-option of gene networks and extracellular cell signaling in early animal evolution.
  • Sinnemäki, Kaius (2014)
    Linguistic typological preferences have often been linked to cognitive processing preferences but often without recourse to typologically relevant experiments on cognitive processing. This article reviews experimental work on the possible parallels between preferences in cognitive processing and language typology. I summarize the main theoretical accounts of the processing‐typology connection and show that typological distributions arise diachronically from preferred paths of language change, which may be affected by the degree to which alternative structures are preferred (e.g., easier) in acquisition or usage. The surveyed experimental evidence shows that considerable support exists for many linguistic universals to reflect preferences in cognitive processing. Artificial language learning experiments emerge as a promising method for researching the processing‐typology connection, as long as its limitations are taken into account. I further show that social and cultural differences in cognition may have an effect on typological distributions and that to account for this variation a multidisciplinary approach to the processing‐typology connection has to be developed. Lastly, since the body of experimental research does not adequately represent the linguistic diversity of the world's languages, it remains as an urgent task for the field to better account for this diversity in future work.
  • Kivimäki, Mika; Walker, Keenan A.; Pentti, Jaana; Nyberg, Solja; Mars, Nina; Vahtera, Jussi; Suominen, Sakari B.; Lallukka, Tea; Rahkonen, Ossi; Pietiläinen, Olli; Koskinen, Aki; Vaananen, Ari; Kalsi, Jatinderpal K.; Goldberg, Marcel; Zins, Marie; Alfredsson, Lars; Westerholm, Peter J. M.; Knutsson, Anders; Theorell, Tores; Ervasti, Jenni; Oksanen, Tuula; Sipilä, Pyry N.; Tabak, Adam G.; Ferrie, Jane E.; Williams, Stephen A.; Livingston, Gill; Gottesman, Rebecca F.; Singh-Manoux, Archana; Zetterberg, Henrik; Lindbohm, Joni (2021)
    OBJECTIVES To examine the association between cognitively stimulating work and subsequent risk of dementia and to identify protein pathways for this association. DESIGN Multicohort study with three sets of analyses. SETTING United Kingdom, Europe, and the United States. PARTICIPANTS Three associations were examined: cognitive stimulation and dementia risk in 107 896 participants from seven population based prospective cohort studies from the IPD-Work consortium (individual participant data meta-analysis in working populations); cognitive stimulation and proteins in a random sample of 2261 participants from one cohort study; and proteins and dementia risk in 13 656 participants from two cohort studies. MAIN OUTCOME MEASURES Cognitive stimulation was measured at baseline using standard questionnaire instruments on active versus passive jobs and at baseline and over time using a job exposure matrix indicator. 4953 proteins in plasma samples were scanned. Follow-up of incident dementia varied between 13.7 to 30.1 years depending on the cohort. People with dementia were identified through linked electronic health records and repeated clinical examinations. RESULTS During 1.8 million person years at risk, 1143 people with dementia were recorded. The risk of dementia was found to be lower for participants with high compared with low cognitive stimulation at work (crude incidence of dementia per 10 000 person years 4.8 in the high stimulation group and 7.3 in the low stimulation group, age and sex adjusted hazard ratio 0.77, 95% confidence interval 0.65 to 0.92, heterogeneity in cohort specific estimates I2=0%, P=0.99). This association was robust to additional adjustment for education, risk factors for dementia in adulthood (smoking, heavy alcohol consumption, physical inactivity, job strain, obesity, hypertension, and prevalent diabetes at baseline), and cardiometabolic diseases (diabetes, coronary heart disease, stroke) before dementia diagnosis (fully adjusted hazard ratio 0.82, 95% confidence interval 0.68 to 0.98). The risk of dementia was also observed during the first 10 years of follow-up (hazard ratio 0.60, 95% confidence interval 0.37 to 0.95) and from year 10 onwards (0.79, 0.66 to 0.95) and replicated using a repeated job exposure matrix indicator of cognitive stimulation (hazard ratio per 1 standard deviation increase 0.77, 95% confidence interval 0.69 to 0.86). In analysis controlling for multiple testing, higher cognitive stimulation at work was associated with lower levels of proteins that inhibit central nervous system axonogenesis and synaptogenesis: slit homologue 2 (SLIT2, fully adjusted r3 -0.34, P(0.001), carbohydrate sulfotransferase 12 (CHSTC, fully adjusted r3 -0.33, P(0.001), and peptidyl-glycine alpha-amidating monooxygenase (AMD, fully adjusted r3 -0.32, P(0.001). These proteins were associated with increased dementia risk, with the fully adjusted hazard ratio per 1 SD being 1.16 (95% confidence interval 1.05 to 1.28) for SLIT2, 1.13 (1.00 to 1.27) for CHSTC, and 1.04 (0.97 to 1.13) for AMD. CONCLUSIONS The risk of dementia in old age was found to be lower in people with cognitively stimulating jobs than in those with non-stimulating jobs. The findings that
  • Räsänen, Aleksi (2021)
    Cross-scale interactions affect resilience in a wide array of social systems such as flood risk management, but it has been argued that studies of such interactions remain limited. Based on qualitative interviews, quantitative surveys, and policy document analysis, I employed the panarchy framework in an analysis of temporal changes and cross-scale interactions in flood risk management at the local and regional scale in Rovaniemi, in Finnish Lapland. The results revealed that administrative co-operation in flood preparedness has functioned well in Rovaniemi in recent decades and few changes have been made to it. Nevertheless, flood defense measures have been the subject of a persistent and dynamic conflict, which has been locked in a polarized phase. Among local residents? approaches to flood risk management, there have been few changes in preparedness, although administrative actors have emphasized communication and self-preparedness in recent years. I discuss how the cross-scale mismatches have contributed to hinder the flood risk management, sharpen the conflict over flood defense measures, and keep the local residents? level of preparedness low.
  • Scott, Ashley; Reinhold, Sabine; Hermes, Taylor; Kalmykov, Alexey A.; Belinskiy, Andrey; Buzhilova, Alexandra; Berezina, Natalia; Kantorovich, Anatoliy R.; Maslov, Vladimir E.; Guliyev, Farhad; Lyonnet, Bertille; Gasimov, Parviz; Jalilov, Bakhtiyar; Eminli, Jeyhun; Iskandarov, Emil; Hammer, Emily; Nugent, Selin E.; Hagan, Richard; Majander, Kerttu; Onkamo, Päivi; Nordqvist, Kerkko; Shishlina, Natalia; Kaverzneva, Elena; Korolev, Arkadiy I.; Khokhlov, Aleksandr A.; Smolyaninov, Roman V.; Sharapova, Svetlana V.; Krause, Rudiger; Karapetian, Marina; Stolarczyk, Eliza; Krause, Johannes; Hansen, Svend; Haak, Wolfgang; Warinner, Christina (2022)
    Archaeological and archaeogenetic evidence points to the Pontic-Caspian steppe zone between the Caucasus and the Black Sea as the crucible from which the earliest steppe pastoralist societies arose and spread, ultimately influencing populations from Europe to Inner Asia. However, little is known about their economic foundations and the factors that may have contributed to their extensive mobility. Here, we investigate dietary proteins within the dental calculus proteomes of 45 individuals spanning the Neolithic to Greco-Roman periods in the Pontic-Caspian Steppe and neighbouring South Caucasus, Oka-Volga-Don and East Urals regions. We find that sheep dairying accompanies the earliest forms of Eneolithic pastoralism in the North Caucasus. During the fourth millennium Bc, Maykop and early Yamnaya populations also focused dairying exclusively on sheep while reserving cattle for traction and other purposes. We observe a breakdown in livestock specialization and an economic diversification of dairy herds coinciding with aridification during the subsequent late Yamnaya and North Caucasus Culture phases, followed by severe climate deterioration during the Catacomb and Lola periods. The need for additional pastures to support these herds may have driven the heightened mobility of the Middle and Late Bronze Age periods. Following a hiatus of more than 500 years, the North Caucasian steppe was repopulated by Early Iron Age societies with a broad mobile dairy economy, including a new focus on horse milking.
  • Korhonen, Tuukka; Järvisalo, Matti (AAAI Press, 2020)
    AAAI Conference on Artificial Intelligence
  • Erjansola, Ari-Matti; Lipponen, Jukka; Vehkalahti, Kimmo; Aula, Hanna-Mari; Pirttila-Backman, Anna-Maija (2021)
    Brand logos are a fundamental part of the corporate visual identity, and their reception has been vigorously researched. The focus has been on the visual traits of the logo and their effect on the reception process, whereas little attention has been paid to how the logo becomes part of the brand. This article narrows this research gap in investigating how a new logo is evaluated, how the perception evolves, and what underlying dimensions emerge from the reception process. We adopted a longitudinal free-association approach and followed the qualitative and quantitative changes in logo associations among first-year students at Aalto University as it was going through a merger accompanied with a radical visual-identity redesign. We show how the new logo faced initial resistance before it became a source of positive brand associations, and how it became anchored in the university ' s corporate identity. We argue that logo evaluations span three dimensions: they may be congruent or incongruent with the disposition of the individual toward the change: they may be congruent or incongruent with the visual preferences of the individual; and they may be based on the visuals of the logo or on its identity-expressing capabilities.
  • Nyqvist, Eeva-Liisa; Lahtinen, Sinikka (2021)
    Swedish grammatical gender is challenging for Finnish-speaking learners of Swedish due to its abstract meaning, the complex nature of Swedish NPs and the low salience of the morphology used to mark gender. Our study compares the expression of gender in texts written in Swedish by Finnish-speaking 12- and 15-year-old immersion students with that of 16-year-old non-immersion students. The results show that NPs with gender agreement, i.e. those with several morphemes marking gender, are more difficult than NPs with only one marker. In all informant groups, uter is significantly easier than neuter, but uter is also overused, as approximately 75% of all Swedish nouns are uter in modern Swedish. Comparisons between different informant groups show that non-immersion students often reach a significantly higher level of accuracy than immersion students, which indicates that formal teaching has a positive effect.
  • Rizzi, Romeo; Cairo, Massimo; Mäkinen, Veli; Tomescu, Alexandru I.; Valenzuela, Daniel (2019)
    Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content of diploid genomes to be used as basis of sequence analysis. In this paper, we show that the computational complexity will change for natural extensions of alignments to pan-genome representations and to diploid genomes. More broadly, our approach can also be seen as a minimal extension of sequence alignment to labelled directed acyclic graphs (labeled DAGs). Namely, we show that finding a covering alignment of two labeled DAGs is NP-hard even on binary alphabets. A covering alignment asks for two paths R-1 (red) and G(1) (green) in DAG D-1 and two paths R-2 (red) and G(2) (green) in DAG D-2 that cover the nodes of the graphs and maximize the sum of the global alignment scores: asosp(R-1), sp(R-2)) + asosp(G(1)), sp(G(2))), where sp(P) is the concatenation of labels on the path P. Pair-wise alignment of haplotype sequences forming a diploid chromosome can be converted to a two-path coverable labelled DAG, and then the covering alignment models the similarity of two diploids over arbitrary recombinations. We also give a reduction to the other direction, to show that such a recombination-oblivious diploid alignment is NP-hard on alphabets of size 3.
  • Kulmuni, J.; Westram, A. M. (2017)
    The possibility of intrinsic barriers to gene flow is often neglected in empirical research on local adaptation and speciation with gene flow, for example when interpreting patterns observed in genome scans. However, we draw attention to the fact that, even with gene flow, divergent ecological selection may generate intrinsic barriers involving both ecologically selected and other interacting loci. Mechanistically, the link between the two types of barriers may be generated by genes that have multiple functions (i.e., pleiotropy), and/or by gene interaction networks. Because most genes function in complex networks, and their evolution is not independent of other genes, changes evolving in response to ecological selection can generate intrinsic barriers as a by-product. A crucial question is to what extent such by-product barriers contribute to divergence and speciation-that is whether they stably reduce gene flow. We discuss under which conditions by-product barriers may increase isolation. However, we also highlight that, depending on the conditions (e.g., the amount of gene flow and the strength of selection acting on the intrinsic vs. the ecological barrier component), the intrinsic incompatibility may actually destabilize barriers to gene flow. In practice, intrinsic barriers generated as a by-product of divergent ecological selection may generate peaks in genome scans that cannot easily be interpreted. We argue that empirical studies on divergence with gene flow should consider the possibility of both ecological and intrinsic barriers. Future progress will likely come from work combining population genomic studies, experiments quantifying fitness and molecular studies on protein function and interactions.
  • Duplouy, Anne; Nair, Abhilash; Nyman, Toshka; van Nouhuys, Saskya (2021)
    Population bottlenecks associated with founder events strongly impact the establishment and genetic makeup of populations. In addition to their genotype, founding individuals also bring along symbionts that can manipulate the phenotype of their host, affecting the host population establishment, dynamics and evolution. Thus, to understand introduction, invasion, and spread, we should identify the roles played by accompanying symbionts. In 1991, the parasitoid wasp, Hyposoter horticola, and its associated hyperparasitoid were accidentally introduced from the main Åland islands, Finland, to an isolated island in the archipelago, along with their host, the Glanville fritillary butterfly. Though the receiving island was unoccupied, the butterfly was present on some of the small islands in the vicinity. The three species have persisted as small populations ever since. A strain of the endosymbiotic bacterium Wolbachia has an intermediate prevalence in the H. horticola across the main Åland population. The infection increases susceptibility of the parasitoid to hyperparasitism. We investigated the establishment and spread of the parasitoid, along with patterns of prevalence of its symbiont using 323 specimens collected between 1992 and 2013, from five localities across Åland, including the source and introduced populations. Using 14 microsatellites and one mitochondrial marker, we suggest that the relatively diverse founding population and occasional migration between islands might have facilitated the persistence of all isolated populations, despite multiple local population crashes. We also show local near-fixation of Wolbachia, where the hyperparasitoid is absent, and selection against infected wasp genotypes is relaxed.
  • LaMere, Kelsey; Mäntyniemi, Samu; Vanhatalo, Jarno; Haapasaari, Päivi (2020)
    Eliciting stakeholders’ mental models is an important participatory modeling (PM) tool for building systems knowledge, a frequent challenge in natural resource management. Therefore, mental models constitute a valu-able source of information, making it imperative to document them in detail, while preserving the integrity of stakeholders’ beliefs. We propose a methodology, the Rich Elicitation Approach (REA), which combines direct and indirect elicitation techniques to meet these goals. We describe the approach in the context of the effects of climate change on Baltic salmon. The REA produced holistic depictions of mental models, with more variables and causal relationships per diagram than direct elicitation alone, thus providing a solid knowledge base on which to begin PM studies. The REA was well received by stakeholders and fulfilled the substantive, normative, instrumental, and educational functions of PM. However, motivating stakeholders to confirm the accuracy of their models during the verification stage of the REA was challenging.
  • Alexandridis, Nikolaos; Marion, Glenn; Chaplin-Kramer, Rebecca; Dainese, Matteo; Ekroos, Johan; Grab, Heather; Jonsson, Mattias; Karp, Daniel S.; Meyer, Carsten; O'Rourke, Megan E.; Pontarp, Mikael; Poveda, Katja; Seppelt, Ralf; Smith, Henrik G.; Martin, Emily A.; Clough, Yann (2021)
    Natural control of invertebrate crop pests has the potential to complement or replace conventional insecticide based practices, but its mainstream application is hampered by predictive unreliability across agroecosystems. Inconsistent responses of natural pest control to changes in landscape characteristics have been attributed to ecological complexity and system-specific conditions. Here, we review agroecological models and their potential to provide predictions of natural pest control across agricultural landscapes. Existing models have used a multitude of techniques to represent specific crop-pest-enemy systems at various spatiotemporal scales, but less wealthy regions of the world are underrepresented. A realistic representation of natural pest control across systems appears to be hindered by a practical trade-off between generality and realism. Nonetheless, observations of context-sensitive, trait-mediated responses of natural pest control to land-use gradients indicate the potential of ecological models that explicitly represent the underlying mechanisms. We conclude that modelling natural pest control across agroecosystems should exploit existing mechanistic techniques towards a framework of contextually bound generalizations. Observed similarities in causal relationships can inform the functional grouping of diverse agroecosystems worldwide and the development of the respective models based on general, but context-sensitive, ecological mechanisms. The combined use of qualitative and quantitative techniques should allow the flexible integration of empirical evidence and ecological theory for robust predictions of natural pest control across a wide range of agroecological contexts and levels of knowledge availability. We highlight challenges and promising directions towards developing such a general modelling framework.