Dataset Information

Computational complexity of ecological and evolutionary spatial dynamics.

ABSTRACT: There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant) will take over a resident population? We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).

SUBMITTER: Ibsen-Jensen R

PROVIDER: S-EPMC4697423 | biostudies-literature | 2015 Dec

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Computational complexity of ecological and evolutionary spatial dynamics.

Ibsen-Jensen Rasmus R Chatterjee Krishnendu K Nowak Martin A MA

Proceedings of the National Academy of Sciences of the United States of America 20151207 51

There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for whic ...[more]

PMID: 26644569

Similar Datasets

Project description:BackgroundDiversity patterns result from ecological to evolutionary processes operating at different spatial and temporal scales. Species trait variation determine the spatial scales at which organisms perceive the environment. Despite this knowledge, the coupling of all these factors to understand how diversity is structured is still deficient. Here, we review the role of ecological and evolutionary processes operating across different hierarchically spatial scales to shape diversity patterns of bats-the second largest mammal order and the only mammals with real flight capability.Main bodyWe observed that flight development and its provision of increased dispersal ability influenced the diversification, life history, geographic distribution, and local interspecific interactions of bats, differently across multiple spatial scales. Niche packing combined with different flight, foraging and echolocation strategies and differential use of air space allowed the coexistence among bats as well as for an increased diversity supported by the environment. Considering distinct bat species distributions across space due to their functional characteristics, we assert that understanding such characteristics in Chiroptera improves the knowledge on ecological processes at different scales. We also point two main knowledge gaps that limit progress on the knowledge on scale-dependence of ecological and evolutionary processes in bats: a geographical bias, showing that research on bats is mainly done in the New World; and the lack of studies addressing the mesoscale (i.e. landscape and metacommunity scales).ConclusionsWe propose that it is essential to couple spatial scales and different zoogeographical regions along with their functional traits, to address bat diversity patterns and understand how they are distributed across the environment. Understanding how bats perceive space is a complex task: all bats can fly, but their perception of space varies with their biological traits.

Dataset Information

Computational complexity of ecological and evolutionary spatial dynamics.

Publications

Computational complexity of ecological and evolutionary spatial dynamics.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets