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.

Project description:BackgroundWhole genome duplication (WGD) and tandem duplication (TD) provide two critical sources of raw genetic material for genome complexity and evolutionary novelty. Little is known about the complexity of the Sesamum indicum genome after it diverged from a common ancestor with the paleodiploid Vitis vinifera and further experienced WGD and TD events.ResultsHere, we analyzed the functional divergence of different classes of inter- and intra-genome gene pairs from ancestral events to uncover multiple-layers of evolutionary dynamics acting during the process of forming the modern S. indicum genome. Comprehensive inter-genome analyses revealed that 60% and 70% of syntenic orthologous gene pairs were retained among the two subgenomes in S. indicum compared to V. vinifera, although there was no evidence of significant differences under selection pressure. For the intra-genomic analyses, 5,932 duplicated gene pairs experienced fractionation, with the remaining 1,236 duplicated gene pairs having undergone functional divergence under diversifying selection. Analysis of the TD events indicated that 2,945 paralogous gene pairs, from 1,089 tandem arrays of 2-16 genes, experienced functional divergence under diversifying selection. Sequence diversification of different classes of gene pairs revealed that most of TD events occurred after the WGD event, with others following the ancestral gene order indicating ancient TD events at some time prior to the WGD event. Our comparison-of-function analyses for different classes of gene pairs indicated that the WGD and TD evolutionary events were both responsible for introducing genes that enabled exploration of novel and complementary functionalities, whilst maintaining individual plant ruggedness.ConclusionsIn this study, we first investigated functional divergence of different classes of gene pairs to characterize the dynamic processes associated with each evolutionary event in S. indicum. The data demonstrated massive and distinct functional divergence among different classes of gene pairs, and provided a genome-scale view of gene function diversification explaining the complexity of the S. indicum genome. We hope this provides a biological model to study the mechanism of plant species formation, particularly in the context of the evolutionary history of flowering plants, and offers novel insights for the study of angiosperm genomes.

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