L'étude de l'écologie et de l'évolution devient de plus en plus mathématique, mais la plupart des outils théoriques semblent provenir de la physique. Cependant, dans de nombreux cas, les problèmes ont un caractère très discret (voir par exemple SLBS00 ) et pourraient bénéficier d'une perspective informatique . Pourtant, je ne connais que quelques résultats sérieux de TCS qui tentent de toucher à des questions spécifiques en écologie et évolution. Les deux directions qui me viennent à l'esprit sont:
Livnat, A., Papadimitriou, C., Dusho, J., et Feldman, MW [2008] "Une théorie de la mixabilité pour le rôle du sexe dans l'évolution" PNAS 105 (50): 19803-19808. [ pdf ]
Valiant, LG [2009] "Evolvability" Journal of the ACM 56 (1): 3.
Le premier applique l'idée de l'analyse des algorithmes génétiques pour montrer une différence qualitative entre la façon dont les organismes sexuels et asexuels se comportent dans les paysages de fitness, et a conduit à des suivis qui aident à justifier la modularité observée. Ce dernier relie l'évolution et la théorie de l'apprentissage informatique, pour essayer de prouver les résultats de l'évolutivité et de l'impossibilité. Il a influencé une petite collection d'articles, mais principalement par d'autres informaticiens.
Y a-t-il plus de résultats dans ces veines? Leurs autres applications profondes / non triviales de l'informatique théorique permettent-elles de comprendre l'écologie et l'évolution telles qu'elles sont étudiées par les biologistes?
Remarques
Je ne suis pas intéressé par les résultats des algorithmes génétiques ou évolutionnaires liés à l'ingénierie générale. Bien que ce soit une partie très intéressante et passionnante de l'informatique, sa connexion à l'évolution telle qu'étudiée par les biologistes est souvent superficielle. Parfois (comme dans LPDF08) des connexions concrètes sont faites, mais la plupart des résultats standard ne sont pas d'intérêt biologique, et donc je ne m'intéresse pas à eux dans ce post.
La bioinformatique est un domaine proche, mais ce n'est pas non plus ce que je recherche. Bien qu'il puisse être utilisé pour reconstruire des choses comme les arbres phylogénétiques et ainsi aider à l'évolution / l'écologie, les aspects théoriques du CS ne prennent pas le devant de la scène. Ici, les résultats CS semblent être principalement destinés à perfectionner un outil qui peut être largement utilisé comme boîte noire à partir de théories bien établies existantes, et non à construire ou à étendre de nouvelles théories biologiques.
Je préfère les résultats qui utilisent des aspects modernes et non triviaux de l'informatique pour influencer la biologie au niveau théorique (mais toujours pertinent pour les biologistes). En tant que tel, je ne suis pas très intéressé par des choses comme la métabiologie de Chaitin .
Questions connexes
la source
Réponses:
Hmmm. En ce qui concerne la dynamique évolutive / théorie des jeux, mon opinion personnelle est que le document de Livnat et al que vous avez mentionné, bien que très beau travail, ne semble pas tomber "en dehors" de l'approche mathématique standard de la théorie des jeux évolutionnistes (voir le travail par ex. Le groupe de Martin Nowak , tel que l'article de 2005 "Evolutionary Dynamics on Graphs" ).
Donc, les deux affirmations que je ferais sont les suivantes: Premièrement, bien que ce soit un excellent travail dans Dynamique évolutionnaire qui se trouve être effectué par des informaticiens, je ne le placerais pas personnellement dans l'Informatique théorique ou comme étant tout ce qui est étroitement lié au TCS, sauf pour la relation préexistante entre la théorie des jeux évolutionnaire et algorithmique. Deuxièmement, si vous êtes enclin à être en désaccord, alors vous serez peut-être surpris de voir combien le domaine de la dynamique évolutionnaire partage / partage déjà avec TCS philosophiquement (mais je ne suis toujours pas sûr que les techniques soient si similaires).
En général, je serais enclin à dire qu'il n'y a aucun travail dans ce sens, y compris la référence que vous avez mentionnée, qui correspond à ce que vous semblez rechercher, ce qui, je pense, est un lien profond entre un concept / technique de base dans TCS et l'étude de l'évolution. (Bien sûr, si quelqu'un a une opinion différente, dites-le!)
Je pense que la théorie des jeux évolutionnaires ou la dynamique évolutionnaire pourraient bénéficier d'approches plus algorithmiques (comme Livnat et al). Pour un exemple particulier, je vois de belles extensions possibles pour considérer des agents évolutifs avec des capacités de calcul (limitées), comme modélisé par exemple par des machines à états finis. Cela nous permettrait d'étudier l'évolution d'agents discrets avec des stratégies conditionnelles plus complexes comme le tit-for-tat. J'ai examiné un peu cela et entendu parler de travaux préliminaires dans ce sens, mais je n'ai aucune référence à citer.
Mais même cet exemple est une application assez simple, donc les résultats de ce type ne répondront probablement toujours pas à votre question.
J'ai par contre beaucoup plus d'espoirs pour l'apprentissage de la théorie, qui pourrait un jour faire de belles connexions avec la dynamique évolutionnaire. Mais, je ne connais pas très bien ces résultats, je vais donc laisser cela aux autres pour commenter.
(Edit) Une connexion potentielle qui devrait être mentionnée est la relation connue de l'apprentissage (par exemple le "problème de l'expert") et la convergence vers les équilibres dans les jeux répétés. Plus précisément, par exemple (voir le commentaire d'Aaron Roth pour plus de détails), dans un jeu répété, si tous les joueurs jouent des stratégies sans regret, alors la distribution passée des actions converge vers un équilibre corrélé grossier du jeu à un tour. Il peut y avoir quelque chose d'intéressant et de nouveau à dire à ce sujet, vu à travers la lentille de la théorie du jeu évolutif; Je ne suis pas sûr.
la source
Un (récent) domaine de travail lié à l'évolution asexuée avec des applications à la conception de médicaments et utilisant des techniques de chaîne de Markov intéressantes: Evolution Without Sex
la source
Voici un nouvel article notable reliant évolution / génétique à l'algorithme de mise à jour du poids multiplicatif, également présenté par la fondation Simons et inclut un co-auteur cité dans la question (Papadimitriou):
Algorithmes, jeux et évolution Erick Chastain, Adi Livnat, Christos Papadimitriou et Umesh Vazirani
la source
La récente enquête de Misha Gromov sur les cristaux, les protéines, la stabilité et l'isopérimétrie (Bull. Amer. Math. Soc. 48 (2011), 229-257) est une riche veine de sujets mathématiques liés à la biologie (y compris de nombreux sujets liés au TCS méthodes).
La question demandait une liste des
L'enquête de Gromov est davantage orientée vers les questions mathématiques générales que vers des programmes de recherche spécifiques. Ainsi, l'enquête peut être lue comme une sélection de Gromov de
En tant que liste de questions sans réponse plutôt que liste de résultats connus, l'article de Gromov impose des exigences créatives importantes au lecteur.
Peut-être que la principale vertu de l'article est que l'auteur est… Misha Gromov !
la source
hélas, il semble y avoir une énorme lacune dans l'intérêt / la signification scientifique par rapport à la recherche scientifique réelle, comme en témoignent également les votes élevés sur cette question vs les votes faibles sur les réponses (et ne pas s'attendre à défier ce modèle ici). il semble que ce soit un programme d'étude / de recherche très important au cœur de la théorie scientifique à ses débuts. nous avons maintenant les outils pour faire des expériences de calcul qui peuvent soumettre la théorie de l'évolution à des contraintes de falsifiabilité au moins en ce sens que si la théorie de l'évolution est exacte, alors il devrait être possible de la modéliser / simuler au moins grossièrement sur un ordinateur; mais il semble qu'il y ait très peu d'essayer le projet (qui est, à coup sûr, extrêmement ambitieux pour le moins).
par exemple, existe-t-il une simulation qui correspond aux changements évolutifs connus de l'arbre phylogénétique sur des milliards d'années? le défi est interdisciplinaire et transversal et ne semble pas correspondre parfaitement / exactement aux domaines / frontières scientifiques existants. remarquablement, il ne semble même pas y avoir de grands scientifiques ou biologistes proposant explicitement un tel programme de recherche.
voici quelques autres références qui ne correspondent certainement pas strictement aux critères étroits décrits dans la question, mais peuvent être à peu près proches:
dans le domaine de la "vie artificielle", il y a un certain intérêt à tenter de simuler les conditions qui ont conduit à l'auto-organisation de la "soupe chimique" en une sorte de formes de quasi-vie qui montrent les aspects fondamentaux de la réplication, etc. Ex: L'EVOGRID: Une approche des origines computationnelles des efforts de vie Damer
UN MODÈLE DE SÉLECTION DE GROUPE DE GUERRE TERRITORIALE, DE XÉNOPHOBIE ET D'ALTRUISME CHEZ LES HUMAINS ET AUTRES PRIMATS Agner Fog
remarquablement, la question semble être très similaire à: simulation informatique du processus d'évolution sur terre datant de 2008 sur débordement de pile avec quelques références diverses.
la source