# Evolution as a directed graph exploration?

First of all, I am not biologist, nor good in chemistry/physics.

Secondly, I am really eager to understand.

1. So I think of a "life" (of a certain whatever being) as a space of somewhat properties. Having a wings is a property. Being tall is a property. Ability to speak as humans do is a property as well.
2. Properties can be combined. Nearly like Lego blocks do combine: one can build both: a) quite elegant structures, b) total absurd of those blocks. Like with Lego, not necessarily each block can be composed with each block. There are some (probably extremely sophisticated!) rules, defining what can be combined with what; thus set of all properties you might get in future depends upon all the properties you already have. In other words, you present defines all the possibilities of your future.
3. There is at least one measuring system: it takes a set of properties as an input and maps it to a, let say, number (or something else, which obeys ordering; number feels like the most simple example) denoting how "good"/"bad" this particular combination is.
4. As a natural consequence of all above-mentioned, there is a directed graph, where: A) vertices represent all possible sets of all possible (respecting rules) combinations of all possible properties; B) directed edges represent the possibility to "evolve" from one concrete set of properties to another one concrete set of properties.

Based on those assumptions, I am going to define what "evolution" is:

Evolution becomes nothing but a finding a shortest path in that unbelievably huge directed graph. I assume most of the readers don't understand algorithms, so brief remark: "shortest-path" problem is one of the hardest even known; roughly saying, it takes "infinite" time and hence is impractical for humans; however, this perfectly explains why evolution takes billions of years - indeed, it's not that hard to define graph, which can't be solved faster than that.

But in order to find shortest path, which is known well from algorithmic theory, you have to be as broad as possible. You try to explore as many vertices, as possible, which means you're creating creatures with all those properties (see #2) and measure their "goodness" with help of your metrics (see #3). The problem here is that you have to track/memorize all the paths you have tried already; especially those, which are proved to be deadends: otherwise your graph exploration will never terminate: you will cycle over the routes you've seen already, but forgotten.

The other thing of great importance, is how expensive your computation is. It runs billions of years and thus you have to guarantee that it's defended properly, can't be lost because of stupid mistake or unexpected circumstances; and the best known way to do this is to copy information about entire process (since very beginning) to each and every Life-being you ever create. The more copies you got, the more reliable entire system: even if you loose all of them momentarily and exactly single creature will survive, it will be sufficient to continue your computation (to continue evolution) relying on the information it accumulates.

Taking into consideration the dimension of the graph we're talking about, that "backtracking" requires enormous amounts of memory. Hence, you need perfect compressing technique to pack your data in the most compact way. And it seems to me that DNA is exactly for this reason (probably not only for this, but this one is definitely important).

What I'd like to hear, is how logical entire thinking I've demonstrated, ignoring numerous details (which I even not aware of)? Could it work like a dramatically simplified representation of evolution? Did I define the DNA's role correctly then? Can you extend this "graph analogy" with fresh details? Am I missing something really big and fundamentally important?

# UPDATE:

1) @IMil:

Evolution becomes nothing but a finding a shortest path in that unbelievably huge directed graph.

What makes you think that evolution followed the shortest path?

Evolution does not. In order to find one, you have to try all of them (i.e. all possible paths starting from all existing vertices), measuring "shortness" according to a particular metric system you've accepted. Thus, "try them all" becomes an iteration over all possible properties in all possible ways (see #1 on the top of OP). Some of them clearly better than the other one (already known, seen in past and memorized somehow); but that does not discover the "best" path yet: there are, generally saying, unknown number of vertices you haven't visited yet, haven't measured yet, haven't tested out yet.. So, imagine you do not memorize what you have seen; what's than? What will happen if your metric system will get changed one day? - You'll have to start from the beginning rather than re-measure known subgraph (which is much more faster).

2) @Cort Ammon:

"There is at least one measuring system ... denoting how good/bad a combination is." This may be true telelogically, but we have no clear indication as to whether such a measure exists in a physical sense. Personally, I find it's more effective to think of there being at least trillions of measuring systems, each doing its own thing, which may or may not even be associated with evolution directly, such that the gestalt of all of those systems gives the behavior we see. While we can think of systems as "striving for good," we can also think of them as "just doing their own thing." Both approaches model nature quite well, with their own quirks.

I can't agree with you here. Having any positive number of metrics does not contradicts to the statement "there is at least one"; as well as having a "superposition" of any positive number of metrics does not.

So what we end up finding is that your definition is akin to saying "A written language is nothing more than a construct which admits finite sequences of letters".

Exactly. What I am saying, is that there exists an enormously huge graph of all possible combinations of all the letters. If you allow you letter sequences to be infinite, than graph itself becomes infinite as well; however, since it takes place in Nature those must be physically limited like everything else. Some of those letters indeed unite into words, which do make sense; the other sequences are just nonsense (with respect to the given metric system: hence, there might be cases, when one metric system disagrees with another one, it's OK). Then evolution becomes a process of searching for the greatest novel ever written (once again, according to the preferable metric system - even if it itself is some kind of "summary" of millions/billions/trillions of factors we're not aware of).

• As a programmer, you probably have already heard of evolutionary algorithms and esp. genetic algorithms used for optimization problems. Mar 14, 2018 at 21:07
• One thing you are leaving out is that evolution takes place in an environment, and the environment is always changing, sometimes drastically. Retaining information about previously helpful adaptations wouldn't necessarily be helpful in the long run, since changes in the environment may have negated their utility. Mar 15, 2018 at 0:25
• a) Finding the shortest path in a graph is not a particularly hard problem - Floyd-Warshall is O(V^3). b) Modelling evolution as a path in configuration space is theoretically neat, but leaves out almost all the details. Mar 15, 2018 at 14:00
• I am afraid this is not a question about biology is defined by SE Biology, which is a question and answer site, but an attempt to initiate a discusion. Any supposed "answers" will only be matters of opinion, which is why I am voting this off-topic. Mar 15, 2018 at 14:31
• You may want to look into something called fitness landscape which sounds like the basis of your model and one thing we know about it is evolution is crap at finding the shortest path, it often locks itself out of the best path even, it is all about finding the local high. en.wikipedia.org/wiki/Fitness_landscape
– John
Mar 15, 2018 at 20:20

But in order to find shortest path, which is known well from algorithmic theory, you have to be as broad as possible. You try to explore as many vertices, as possible, which means you're creating creatures with all those properties (see #2) and measure their "goodness" with help of your metrics (see #3). The problem here is that you have to track/memorize all the paths you have tried already; especially those, which are proved to be deadends: otherwise your graph exploration will never terminate: you will cycle over the routes you've seen already, but forgotten.

Evolution is an optimizing algorithm, but it isn't necessarily the best optimizing algorithm of its type. For example, genetic algorithms used by humans often have certain features that biological evolution doesn't, like carrying over the best solution from generation to generation. Biological evolution doesn't do that: if by chance you're fitter than any of your kids, tough you'll die anyway.

In that spirit, biological evolution doesn't go out of its way to explore as many vertices as possible, or to avoid "cycling over routes you've seen already" (impossible in practice because not many evolved traits can be reversed exactly. But when such reversals are possible we do see them happen. Many lineages have seen gains and losses of limbs, of flight, or moving in and out of aquatic life like ping-pong balls...). And in fact evolution has no memory of the past. We can make inferences about the past when looking at current organisms, but the only thing evolution acts on is the organism that currently exists.

It runs billions of years and thus you have to guarantee that it's defended properly, can't be lost because of stupid mistake or unexpected circumstances

You mean, like the Permian extinction? Those guys were pretty much lost I'm afraid. Same with all other extinctions.

Hence, you need perfect compressing technique to pack your data in the most compact way. And it seems to me that DNA is exactly for this reason (probably not only for this, but this one is definitely important).

What evidence do you have for DNA being the most compact form data could possibly take?

What I'd like to hear, is how logical entire thinking I've demonstrated, ignoring numerous details (which I even not aware of)? Could it work like a dramatically simplified representation of evolution?

Your basic idea, that mathematics, computer science and the field of optimization algorithms in particular can inform our understanding of evolution is sound. But finding the shortest path along a directed graph doesn't strike me as the best metaphor. Think more of finding the fitness peaks in a traits landscape, such that finding them is an NP-complete problem. Here are different algorithms that are used in this kind of problem:

https://optimization.mccormick.northwestern.edu/index.php/Heuristic_algorithms

Note that your requirement to remember past solutions is akin to the Tabu Search, but that's only one possible algorithm. Most heuristic algorithms don't do that.

Did I define the DNA's role correctly then?

No, you didn't. DNA enables the hereditary transfer of certain traits, which allows biological evolution to run as, um, well, an evolutionary algorithm. That is its role in the optimization process that is evolution. It does not copy the entire history of the evolutionary process; it just copies the molecule at hand, and the fact that it contains traces of what happened to previous copies is an epiphenomenon. And in fact it does not allow Evolution to re-create previous iterations of itself.

Can you extend this "graph analogy" with fresh details? Am I missing something really big and fundamentally important?

It seems to me you are treating evolution teleologically, imagining how you would design an ideal optimizing process to generate life and seeing if evolution matches. As this and other answers have found, it doesn't match (as an aside, I'm not sure the ideal optimizing process you envision would even be better than evolution. Tabu search isn't the best of all the heuristic algorithms). But more fundamentally, the assumption that evolution must be the best possible process for doing... what you think evolution is supposed to do, is unfounded. It might be true, it might not. It is generally more productive when looking at evolution to focus on what it does, and not on what we think it intends.

This is not to say teleological thinking has no place at all in evolution, insofar as one can argue that if something is optimized in some way, because it was created through an optimizing process that was optimizing for some specific characteristic(s), then it isn't absurd to use teleological language like "wings are for flying". They are, not in the sense that somebody wanted birds to fly and so made them wings, but in the sense that every characteristic of wings is what it is because it makes them good for flying. Because bird ancestors reproduced or not partly on the strength of their flying abilities.

In other words, if something was fine-tuned by evolution, then we can talk about it being "for" something. It's very possible that DNA is one such thing; maybe some traits of DNA are there to make evolution work better in some way or another(ETA: note even there the primary purpose wouldn't be "to make evolution work better", it would be to promote the reproduction of the organisms carrying that DNA. But if "evolution working better" in some way promoted that, then sure). But evolution itself isn't such a thing. At least I don't think there is evidence that it is.

Your theory is based on many false assumptions.

Evolution becomes nothing but a finding a shortest path in that unbelievably huge directed graph.

What makes you think that evolution followed the shortest path?

The best known way to do this is to copy information about entire process (since very beginning) to each and every Life-being you ever create

DNA doesn't intentionally store information about the evolutionary process. Some genes get lost completely, and mutations are, in general case, irreversible. That should be obvious in case of viral DNA/RNA, where there is simply no space for historical data. Many species, and groups of species, become extinct, and since the fitness of any species is determined by how well it fits in the ecosystem, extinction of dinosaurs makes "backtracking" of mammals impossible.

– AliceD
Mar 14, 2018 at 22:54
• you really should expand on the shortest path comment as well, as it stands it is not informative.
– John
Mar 15, 2018 at 20:17
• As for the shortest path: I'd say the burden of proof lies on the author. Evolution is driven by random mutations, and if you draw imaginary paths from, say, last common ancestor of chimps and humans to us (or chimps), there is no reason to believe that the actual path was the shortest one.
– IMil
Mar 15, 2018 at 20:30

You can prove your model trivially if you start from the assumption that all evolution consists of altering DNA. I think the general consensus is that that's a good place to start, but there may be more as we discover.

Now the issue is that, from this model, we can show that your graph approach is trivial.

• A node in the graph is associated with one sequence of DNA
• Edges between them represent changes that may occur in DNA.

Thus I simply redefined "Property" to be "the presence of a particular sequence of nucleotide."

Generally speaking, we recognize that there is some conversion function from this sequence of nucleotide into "properties" we care about. This means the graph I described above is isomorphic with the graph you were looking for. Of course, as you noted, that function is extraordinarily complicated.

"There is at least one measuring system ... denoting how good/bad a combination is." This may be true telelogically, but we have no clear indication as to whether such a measure exists in a physical sense. Personally, I find it's more effective to think of there being at least trillions of measuring systems, each doing its own thing, which may or may not even be associated with evolution directly, such that the gestalt of all of those systems gives the behavior we see. While we can think of systems as "striving for good," we can also think of them as "just doing their own thing." Both approaches model nature quite well, with their own quirks.

So what we end up finding is that your definition is akin to saying "A written language is nothing more than a construct which admits finite sequences of letters." (That's the definition of a "formal language," by the way). While technically true, it misses out on basically all of the nuance of language.

And there's also the concept of epigenetics which studies ways gene expression changes which don't involve changing DNA. This is an open field. We still do not fully understand what is going on there. But it certainly does appear to play an role, and it does not immediately fit into the simple mapping from DNA to properties.

• It is a great answer, many thanks! I update OP, please checkout the very bottom, there is your name. BTW, do you realize how close your statement to the Godel's theorems? I omitted this question in the OP, but still... question seems to be extremely important. If one show how this idea isomorphic to somewhat formal language... ;) Mar 16, 2018 at 6:45
• @SerejaBogolubov I love Godel's incompleteness theorems, and Tarski's undefinability theorem, but few people appreciate their implications. And, of course, when it comes to systems that are really operating in the world of real numbers rather than integers, they don't imply quite as much as we might like. Mar 16, 2018 at 14:51
• @SerejaBogolubov As for your edit, I agree that "trillions of metrics" is "1 or more." My point of that was to show just how inordinately difficult it is to use that "1 or more" phrasing, except in brutally abstract settings (such as with Godel's incompleteness theorems). Those metrics also most definitely do not superpose in a meaningful way. Biological systems are notoriously nonlinear. At some point, I think those issues start to add up, and the fact that modeling life as just an abstract representation of DNA starts to fall through long before you get the opportunity... Mar 16, 2018 at 14:54
• ... to raise enumeration issues. I could see drawing an analogy to coin flips. You might have some theory like Gambler's Ruin which says that after some countable number of coin flips, the gambler must lose, but failed to model the probability that the real coin lands on its edge instead of heads or tails (1:6000 for a US nickel), and how that influences the game. (I "won" a DnD game by rolling a die so that it landed on an edge instead of a face. The DM was a big fan of a comic in which the only way to win that game was to roll a die on edge) Mar 16, 2018 at 14:56