What computers won't tell you about ecological and evolutionary dynamics

December 09, 2015

The authors specifically took a look at complexity theory which is part of theoretical computer science as well as mathematics. It classifies algorithms that can solve certain categories of computational problems according to their inherent difficulty.

They applied these well-defined classes of complexity to some fundamental questions in biology, namely to the ecological and evolutionary dynamics within structured populations. These research questions investigate how population structures affect the outcome of the evolutionary process.

Consider for example the problem of finding the probability that a genetic mutation establishes itself in a resident population, or an invasive species occupies an ecological niche. Though these problems are well studied, an understanding of the computational complexity of even such simple problems was missing.

The investigators found the rather unexpected proof that these fundamental questions in ecology and evolution can be precisely characterized by specific classes of complexity theory, as though these evolutionary processes would mimic aspects of computation. By defining the exact complexity class, they formally proved that these questions cannot be solved with a simple formula.

However, the authors also demonstrated that two classic problems are indeed efficiently solvable: One is the molecular clock--the rate at which neutral mutations accumulate over time--and the other is the exact fixation probability for a genetic variation to take over in the case of a well-mixed population structure.

So how could the researchers tell for certain that some questions are solvable and that an algorithm must exist? And how is it possible to claim that for other specific questions a computational solution is not possible?

The authors used the established methods of computational complexity theory and applied them to the defined evolutionary scenarios in evolutionary game theory and evolutionary graph theory. As a result, they were able to derive the exact complexity class for each of these research questions. The specific complexity class in turn can tell us if an efficient algorithm exists. How so?

For instance, given a gigantic jigsaw puzzle and a guidance telling us where each piece should go, it is easy to assemble the puzzle and check that it indeed gives the picture on the box. Complexity theory calls this type of problems P as the problem can be solved in polynomial time. Among other things, P contains all problems that can be solved with a simple formula. However, many problems cannot be solved in polynomial time as the necessary computational resource would increase exponentially with the growing size of the input. Thus, for such problems, no simple formula exists.

Another important complexity class in the context of this study is nondeterministic polynomial time (NP) which categorizes the problems to which solutions can be verified in polynomial time: If we imagine the giant jigsaw puzzle without the guidance, then it might be hard to decide where some of the pieces should go. However, as mentioned above, once a solution (=guidance) is found it is easy to check that it is indeed a solution.

Incidentally, the question whether all problems in NP belong to P or not is one of the famous six yet unsolved problems of mathematics, for which a Millenium Prize of 1 million dollars was awarded in 2000 by the Clay Mathematics Institute. It is the widely believed albeit yet unproven that P does not equal NP, and hence, the hardest problems in NP cannot be solved with a simple formula.

The findings of the investigators are a first step to establish a connection between the two disciplines of computer science and biology, and they also suggest that research on certain questions in ecological and evolutionary dynamics need to focus on special aspects that can be solved with a simple formula.

Institute of Science and Technology Austria

Related Mathematics Articles from Brightsurf:

A new method for boosting the learning of mathematics
How can mathematics learning in primary school be facilitated? UNIGE has developed an intervention to promote the learning of math in school.

Could mathematics help to better treat cancer?
Impaired information processing may prevent cells from perceiving their environment correctly; they then start acting in an uncontrolled way and this can lead to the development of cancer.

People can see beauty in complex mathematics, study shows
Ordinary people see beauty in complex mathematical arguments in the same way they can appreciate a beautiful landscape painting or a piano sonata.

Improving geothermal HVAC systems with mathematics
Sustainable heating, ventilation, and air conditioning systems, such as those that harness low-enthalpy geothermal energy, are needed to reduce collective energy use and mitigate the continued effects of a warming climate.

How the power of mathematics can help assess lung function
Researchers at the University of Southampton have developed a new computational way of analyzing X-ray images of lungs, which could herald a breakthrough in the diagnosis and assessment of chronic obstructive pulmonary disease (COPD) and other lung diseases.

Mathematics pushes innovation in 4-D printing
New mathematical results will provide a potential breakthrough in the design and the fabrication of the next generation of morphable materials.

More democracy through mathematics
For democratic elections to be fair, voting districts must have similar sizes.

How to color a lizard: From biology to mathematics
Skin color patterns in animals arise from microscopic interactions among colored cells that obey equations discovered by Alan Turing.

US educators awarded for exemplary teaching in mathematics
Janet Heine Barnett, Caren Diefenderfer, and Tevian Dray were named the 2017 Deborah and Franklin Tepper Haimo Award winners by the Mathematical Association of America (MAA) for their teaching effectiveness and influence beyond their institutions.

Authors of year's best books in mathematics honored
Prizes for the year's best books in mathematics were awarded to Ian Stewart and Tim Chartier by the Mathematical Association of America (MAA) on Jan.

Read More: Mathematics News and Mathematics Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.