Ecologia e evolução através da lente algorítmica

27

O estudo da ecologia e da evolução está se tornando cada vez mais matemático, mas a maioria das ferramentas teóricas parece vir da física. No entanto, em muitos casos, os problemas têm uma natureza muito discreta (veja, por exemplo, SLBS00 ) e podem se beneficiar da perspectiva da ciência da computação . No entanto, estou ciente de apenas alguns resultados sérios do TCS que tentam abordar questões específicas em ecologia e evolução. As duas direções que vêm à mente são:

  1. Livnat, A., Papadimitriou, C., Dusho, J., & Feldman, MW [2008] "Uma teoria da mixabilidade para o papel do sexo na evolução" PNAS 105 (50): 19803-19808. [ pdf ]

  2. Valiant, LG [2009] "Evolvability" Journal of the ACM 56 (1): 3.

O primeiro aplica a idéia da análise de algoritmos genéticos para mostrar uma diferença qualitativa entre a maneira como os organismos sexuais e assexuais se comportam em ambientes de condicionamento físico e levou a acompanhamentos que ajudam a justificar a modularidade observada. O último conecta a teoria da evolução e da aprendizagem computacional, para tentar provar os resultados de evolutibilidade e impositibilidade. Ele influenciou uma pequena coleção de papéis, mas principalmente por outros cientistas da computação.

Existem mais resultados nessas veias? São suas outras aplicações profundas / não triviais da ciência da computação teórica para entender a ecologia e a evolução conforme estudada pelos biólogos?


Notas

  • Não estou interessado nos resultados de algoritmos genéticos ou evolutivos relacionados à engenharia geral. Embora essa seja uma parte muito interessante e empolgante da ciência da computação, sua conexão com a evolução estudada por biólogos é frequentemente superficial. Às vezes (como no LPDF08) são feitas conexões concretas, mas a maioria dos resultados padrão não tem interesse biológico e, portanto, não estou interessado neles neste post.

  • A bioinformática é um campo próximo, mas também não é o que estou procurando. Embora possa ser usado para reconstruir coisas como árvores filogenéticas e, assim, ajudar a evolução / ecologia, os aspectos teóricos do CS não tomam o centro do palco. Aqui, os resultados do CS parecem ser principalmente para aperfeiçoar uma ferramenta que pode ser usada amplamente como uma caixa-preta de dentro das teorias bem estabelecidas existentes, e não para construir ou estender novas teorias biológicas.

  • Prefiro resultados que usem aspectos modernos e não triviais da ciência da computação para influenciar a biologia no nível teórico (mas ainda relevante para os biólogos). Como tal, não estou tão interessado em coisas como a metabiologia de Chaitin .

Perguntas relacionadas

Artem Kaznatcheev
fonte
4
A pesquisa de Tanya Berger-Wolf sobre biologia computacional da população pode ser relevante aqui.
Jeffε
2
@vzn, como isso tem algo a ver com a ciência da computação teórica? Alguma dessas idéias usa o TCS de maneira não trivial? Não estou pedindo um curso introdutório de biologia, mas o impacto do pensamento histórico na ecologia e na evolução.
Artem Kaznatcheev
1
Possivelmente um pouco relevante: comunicação entre células em um organismo multicelular a partir da perspectiva da teoria da computação distribuída - veja, por exemplo, essa palestra de Yuval Emek .
Jukka Suomela

Respostas:

4

Hummm. Tanto quanto dinâmica evolutiva / teoria dos jogos vai, minha opinião pessoal é que o Livnat et al papel que você mencionou, enquanto o trabalho muito bom, não parece cair "fora" da abordagem matemática padrão para a teoria dos jogos evolucionária (ver o trabalho por exemplo Grupo de Martin Nowak , como o artigo '05 "Dynamics Evolutionary on Graphs" ).

Portanto, as duas alegações que eu faria são: Primeiro, embora este seja um ótimo trabalho em Dinâmica Evolucionária que é feito por cientistas da computação, eu não o colocaria pessoalmente na Teoria da Computação ou como estando intimamente relacionado ao TCS, exceto para a relação preexistente entre a teoria evolutiva e algorítmica dos jogos. Segundo, se você está discordando, pode se surpreender com o quanto o campo da Dinâmica Evolucionária já compartilha / compartilha com o TCS filosoficamente (mas ainda não tenho certeza de que as técnicas sejam semelhantes).

Em geral, eu gostaria de dizer que não há nenhum trabalho nesse sentido, incluindo a referência que você mencionou, que se encaixa no que você parece estar procurando, o que eu acho que é uma conexão profunda entre algum conceito / técnica central no TCS e o estudo da evolução. (Obviamente, se alguém tiver uma opinião diferente, diga-o!)

Eu acho que a teoria dos jogos evolucionários ou a dinâmica evolutiva poderiam se beneficiar de abordagens mais algorítmicas (como Livnat et al). Para um exemplo em particular, vejo possíveis extensões agradáveis ​​para considerar agentes evolutivos com habilidades computacionais (limitadas), conforme modelado por, por exemplo, máquinas de estados finitos. Isso nos permitiria estudar a evolução de agentes discretos com estratégias condicionais mais complexas, como tit-for-tat. Analisei um pouco isso e ouvi falar de alguns trabalhos preliminares nesse sentido, mas não tenho nenhuma referência a citar.

Mas mesmo este exemplo é uma aplicação bastante direta, portanto, resultados desse tipo provavelmente ainda não responderiam à sua pergunta.

Por outro lado, tenho grandes esperanças de aprender a teoria, que um dia poderia fazer boas conexões com a dinâmica evolutiva também. Mas eu não estou muito familiarizado com esses resultados, então deixarei isso para que outros comentem.

(Editar) Uma conexão potencial que deve ser mencionada é a relação conhecida de aprendizado (por exemplo, o "problema do especialista") e a convergência para o equilíbrio em jogos repetidos. Especificamente, por exemplo (veja o comentário de Aaron Roth para obter detalhes), em um jogo repetido, se todos os jogadores estiverem jogando estratégias sem arrependimentos, a distribuição de ações passadas converge para um equilíbrio correlato grosseiro do jogo de rodada única. Pode haver algo interessante e novo a dizer sobre isso, visto através das lentes da teoria dos jogos evolucionários; Não tenho certeza.

usul
fonte
2
Obrigado por seus pensamentos, mas esta não é uma resposta. Tenho plena consciência (como mencionei na segunda frase) de grupos como o de Nowak, que se baseiam principalmente em ferramentas inspiradas na física. A questão não é se poderia haver conexões (como eu já sei que existem) ou se a maioria do campo as persegue (como eu já sei que elas não o fazem), mas por exemplos de etapas iniciais que as pessoas deram do ângulo do TCS .
Artem Kaznatcheev
Certo, bem, eu estava tentando responder de forma negativa (no que diz respeito à dinâmica evolutiva) da maneira mais útil possível.
usul 27/10/12
Também agora estou um pouco confuso sobre se você acha que Livnat et al é uma resposta positiva à sua própria pergunta ou não? (Além disso, esta é uma questão incrível / interessante e espero que obter muito mais / melhores respostas!)
usul
1
O LPDF08 e o trabalho de acompanhamento mais recente são exemplos positivos, assim como o trabalho e os acompanhamentos da Valiant. No entanto, eu as excluo das respostas simplesmente porque já as conheço.
Artem Kaznatcheev
3
Escolha rápida de nit: sob a noção padrão de arrependimento, a história empírica do jogo sem arrependimentos converge apenas para o conjunto de equilíbrios correlatos "grosseiros" em jogos gerais. A noção mais forte de arrependimento "interno" ou "de troca" é necessária para convergir para o conjunto de equilíbrios correlatos. O jogo regular sem arrependimento converge para o equilíbrio de Nash em jogos de soma zero. Isso pode ser mais relevante para noções evolutivas - os equilíbrios correlatos precisam de um dispositivo correlacionado para implementar, e não está claro o que isso seria no contexto da evolução.
Aaron Roth
3

Uma (recente) linha de trabalho relacionada à evolução assexuada com aplicações ao design de drogas e utiliza técnicas interessantes da cadeia de Markov: Evolution Without Sex

anônimo
fonte
2

aqui está um novo artigo notável ligando evolução / genética ao algoritmo Multiplicative Weight Update, também elaborado pela fundação Simons e inclui um co-autor citado na pergunta (Papadimitriou):

  • Algoritmos, jogos e evolução Erick Chastain, Adi Livnat, Christos Papadimitriou e Umesh Vazirani

    Mesmo os estudantes mais experientes da evolução, começando com o próprio Darwin, ocasionalmente expressaram espanto por o mecanismo da seleção natural ter produzido toda a Vida como a vemos ao nosso redor. Existe uma maneira computacional de articular o mesmo espanto: “Que algoritmo poderia conseguir tudo isso em meros três bilhões e meio de anos?” Neste artigo, propomos uma resposta: Demonstramos que, no regime de seleção fraca, o padrão As equações da genética populacional que descrevem a seleção natural na presença do sexo tornam-se idênticas às de um jogo repetido entre genes reproduzidos de acordo com atualizações de peso multiplicativas (MWUA), um algoritmo conhecido na ciência da computação por ser surpreendentemente poderoso e versátil. O MWUA maximiza uma troca entre desempenho cumulativo e entropia,

vzn
fonte
0

A recente pesquisa abrangente de Misha Gromov Cristais, proteínas, estabilidade e isoperimetria (Bull. Amer. Math. Soc. 48 (2011), 229-257) é uma rica veia de tópicos matemáticos relacionados à biologia (incluindo muitos tópicos que se conectam ao TCS métodos).

A pergunta solicitou uma lista de

Resultados que usam aspectos modernos e não triviais da ciência da computação […] de natureza muito discreta […] através de uma lente algorítmica

A pesquisa de Gromov é mais orientada para questões matemáticas gerais do que para programas de pesquisa específicos. Assim, a pesquisa pode ser lida como uma seleção de Gromov

Perguntas que (potencialmente) usam aspectos modernos e não triviais da ciência da computação [...] (muitos dos quais) são de natureza muito discreta [...] através (muitas vezes) de uma lente algorítmica.

Como uma lista de perguntas não respondidas, em vez de uma lista de resultados conhecidos, o artigo de Gromov impõe exigências criativas significativas ao leitor.

Talvez a principal virtude do artigo seja que o autor seja… Misha Gromov !

John Sidles
fonte
1
Este é um artigo interessante, mas não vejo como isso se relaciona com a evolução e a ecologia. Existem algumas referências passageiras à evolução (mais proeminentemente nas seções 4 e 6, onde se argumenta que a evolução deve promover simetria). Não há absolutamente nenhuma menção à ecologia. Além disso, embora este seja um bom tratamento matemático, não vejo um foco algorítmico ou computacional. Você pode expandir sua resposta para explicar a relevância deste artigo para visualizar a evolução e a ecologia através das lentes algorítmicas? Caso contrário, isso parece mais adequado como um comentário, não como uma resposta.
Artem Kaznatcheev
@Artem, a resposta foi expandida conforme solicitado. Obrigado Artem.
John sidles
-2

infelizmente, parece haver uma lacuna enorme aqui em interesse / significado científico versus pesquisa científica real, como também evidenciado em votos altos sobre esta questão e votos baixos em respostas (e não esperando desafiar esse padrão aqui). parece ser um programa de estudo / pesquisa muito importante no coração da teoria científica em sua primeira infância. agora temos as ferramentas para realizar experimentos computacionais que podem sujeitar a teoria da evolução a restrições de falsificabilidade , pelo menos no sentido de que, se a teoria evolucionária for precisa, será possível modelá-la / simulá-la pelo menos aproximadamente em um computador; mas parece haver muito poucas tentativas do projeto (o que é, certamente, extremamente ambicioso para dizer o mínimo).

por exemplo, existe alguma simulação que corresponda a mudanças evolutivas conhecidas na árvore filogenética ao longo de bilhões de anos? o desafio é interdisciplinar e transversal e não parece se encaixar perfeitamente / exatamente nos campos / limites científicos existentes. notavelmente, nem parece haver grandes cientistas ou biólogos propondo explicitamente esse programa de pesquisa.

aqui estão alguns outros árbitros que certamente não se encaixam estritamente nos critérios restritos descritos na pergunta, mas podem estar mais ou menos próximos:

  • no campo da "vida artificial", existe algum interesse em tentar simular as condições que levaram à "sopa química" se auto-organizar em algum tipo de quase-vida que mostra aspectos básicos da replicação, etc. Ex .: THE EVOGRID: Uma Abordagem às Origens Computacionais da Vida Empreendimentos Damer

    A busca para entender os mecanismos da origem da vida na Terra poderia ser aprimorada por simulações por computador de estágios plausíveis no surgimento da vida da não-vida no nível molecular. Essa classe de simulação poderia então suportar testes e validação por meio de experimentos químicos de laboratório paralelos. Essa combinação de um componente computacional ou “cibernético” e uma investigação de esforço paralelo na abiogênese química pode ser denominada uma abordagem de cibbiobiogênese. O desafio tecnológico central para os esforços de cibobiogênese é projetar modelos de simulação em computador que permitam o surgimento de novo de estruturas e processos moleculares virtuais prebióticos e biológicos através de múltiplos limites de complexidade. Esta tese assume o desafio de projetar, implementar e analisar um desses modelos de simulação.

  • UM MODELO DE SELEÇÃO DE GRUPO DE GUERRA TERRITORIAL, XENOFOBIA E ALTRUISMO EM HUMANOS E OUTROS PRIMATOS Agner Fog

    Resumo: Um modelo teórico de guerras por territórios de grupo mostra que traços comportamentais como guerra cooperativa, justiça, altruísmo e exclusão externa podem ter co-evoluído em primatas superiores e no homem pré-histórico. As condições para que a guerra territorial seja um mecanismo eficaz de seleção de grupos são discutidas. Essas condições podem estar presentes nas sociedades tribais nos tempos pré-históricos, mas não nos tempos modernos. A evolução geográfica dos territórios é ilustrada com simulações em computador.

  • notavelmente, a questão parece ser muito semelhante a: simulação em computador do processo de evolução na Terra que data de 2008 no estouro de pilha com algumas referências diversas.

vzn
fonte
note que o projeto "origens da vida" está realmente tentando simular "evolução" em origens muito primordiais, isto é, o estágio pré-DNA , portanto, de certa forma, pode-se argumentar que seja realmente "pré-biologia" ...
vzn