Ecology and evolution through the algorithmic lens
Hmmm. As far as evolutionary dynamics/game theory goes, my personal opinion is that the Livnat et al paper you mentioned, while very nice work, doesn't seem to fall "outside" the standard mathematical approach to evolutionary game theory (see work by e.g. Martin Nowak's group, such as the '05 paper "Evolutionary Dynamics on Graphs").

So the two claims I would make are: First, while this is some great work in Evolutionary Dynamics that happens to be done by computer scientists, I would not personally place it inside Theoretical Computer Science or as being all that closely related to TCS, except for the preexisting relationship between evolutionary and algorithmic game theory. Second, if you're inclined to disagree, then you may be surprised how much the field of Evolutionary Dynamics already shares/shared with TCS philosophically (but I'm still not sure the techniques are that similar).

In general, I would be inclined to say that there is not any work along these lines, including the reference you mentioned, that fit what you seem to be looking for, which I think is a deep connection between some core concept/technique in TCS and the study of evolution. (Of course, if anyone has a differing opinion, please say so!)

I do think that evolutionary game theory or evolutionary dynamics could benefit from more algorithic approaches, (such as Livnat et al). For a particular example, I see possible nice extensions for considering evolvable agents with (limited) computional abilities, as modeled by e.g. finite state machines. This would allow us to study the evolution of discrete agents with more complex conditional strategies such as tit-for-tat. I've looked into this a bit and heard of some preliminary work along these lines but don't have any references to cite.

But even this example is a rather straightforward application, so results of this sort probably still wouldn't answer your question.

I have much higher hopes on the other hand for learning theory, which could someday make nice connections to evolutionary dynamics as well. But, I'm not very familiar with those results so I will leave that for others to comment on.

(Edit) One potential connection that should be mentioned is the known relationship of learning (e.g. the "expert's problem") and convergence to equilibria in repeated games. Specifically, for example (see Aaron Roth's comment for details), in a repeated game, if all players are playing no-regret strategies, then the past distribution of actions converges to a coarse correlated equilibrium of the single-round game. There may be something interesting and novel to say about this as viewed through the evolutionary game theory lens; I'm not sure.