Ekologia i ewolucja poprzez soczewkę algorytmiczną

27

Badanie ekologii i ewolucji staje się coraz bardziej matematyczne, ale wydaje się, że większość narzędzi teoretycznych pochodzi z fizyki. Jednak w wielu przypadkach problemy mają bardzo dyskretny charakter (patrz na przykład SLBS00 ) i mogą skorzystać z perspektywy informatyki . Jednak wiem tylko o kilku poważnych wynikach TCS, które próbują poruszać konkretne pytania z ekologii i ewolucji. Dwa kierunki, które przychodzą na myśl, to:

  1. Livnat, A., Papadimitriou, C., Dusho, J., i Feldman, MW [2008] „Teoria mieszalności dla roli seksu w ewolucji” PNAS 105 (50): 19803-19808. [ pdf ]

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

Ten pierwszy stosuje pomysł z analizy algorytmów genetycznych, aby pokazać różnicę jakościową między zachowaniami organizmów płciowych i bezpłciowych w krajobrazach fitness, i doprowadził do dalszych obserwacji, które uzasadniają zaobserwowaną modułowość. Ten ostatni łączy ewolucję i obliczeniową teorię uczenia się, aby spróbować udowodnić wyniki ewolucji i niemożliwości. Wpłynął na niewielką kolekcję artykułów, ale głównie przez innych informatyków.

Czy w tych żyłach jest więcej wyników? Czy ich inne głębokie / nietrywialne zastosowania informatyki teoretycznej do rozumienia ekologii i ewolucji są badane przez biologów?


Uwagi

  • Nie interesują mnie wyniki algorytmów genetycznych lub ewolucyjnych związanych z inżynierią ogólną. Chociaż jest to bardzo interesująca i ekscytująca część informatyki, jej związek z ewolucją badany przez biologów jest często powierzchowny. Czasami (jak w LPDF08) tworzone są konkretne połączenia, ale większość standardowych wyników nie ma znaczenia biologicznego i dlatego nie jestem nimi zainteresowany w tym poście.

  • Bioinformatyka to pobliska dziedzina, ale też nie tego szukam. Chociaż można go wykorzystać do rekonstrukcji rzeczy, takich jak drzewa filogenetyczne, a tym samym pomóc w ewolucji / ekologii, teoretyczne aspekty CS nie zajmują centralnego miejsca. Tutaj wyniki CS wydają się głównie doskonalić narzędzie, które można wykorzystać głównie jako czarną skrzynkę w ramach istniejących dobrze ugruntowanych teorii, a nie budować ani rozszerzać nowych teorii biologicznych.

  • Wolę wyniki, które wykorzystują nowoczesne i nietrywialne aspekty informatyki, aby wpływać na biologię na poziomie teoretycznym (ale wciąż istotnym dla biologów). Jako takie, nie interesują mnie takie rzeczy jak metabiologia Chaitina .

Powiązane pytania

Artem Kaznatcheev
źródło
4
Istotne mogą być tutaj badania Tanyi Berger-Wolf dotyczące biologii populacji obliczeniowej .
Jeffε
2
@vzn jak to ma coś wspólnego z teoretyczną informatyką? Czy któryś z tych pomysłów używa TCS w trywialny sposób? Nie proszę o wprowadzenie do biologii, ale o wpływ myślenia cstheory na ekologię i ewolucję.
Artem Kaznatcheev
1
Być może dość istotne: komunikacja między komórkami w organizmie wielokomórkowym z perspektywy teorii przetwarzania rozproszonego - patrz np. Wykład Yuvala Emka .
Jukka Suomela

Odpowiedzi:

4

Hmmm. Jeśli chodzi o ewolucyjną dynamikę / teorię gier, moja osobista opinia jest taka, że ​​wspomniany przez ciebie papier Livnat i wsp., Choć bardzo fajna praca, nie wydaje się „wykraczać poza” standardowe matematyczne podejście do ewolucyjnej teorii gier (patrz praca np. Grupa Martina Nowaka , taka jak artykuł z 05 „Evolutionary Dynamics on Graphs” ).

Więc dwa twierdzenia, które chciałbym przedstawić, to: po pierwsze, chociaż jest to świetna praca w Dynamice Ewolucji, którą akurat wykonują informatycy, nie umieściłbym jej osobiście wewnątrz Teoretycznej Informatyki lub jako ściśle związanej z TCS, z wyjątkiem dla istniejącego związku między ewolucyjną a algorytmiczną teorią gier. Po drugie, jeśli nie masz ochoty się z tym nie zgadzać, możesz być zaskoczony, jak bardzo pole Dynamiki Ewolucyjnej już dzieli się / współdzieli z TCS filozoficznie (ale nadal nie jestem pewien, czy techniki są podobne).

Ogólnie rzecz biorąc, chciałbym powiedzieć, że nie ma żadnej pracy w tym zakresie, w tym wspomnianego przez ciebie odniesienia, która pasowałaby do tego, czego wydajesz się poszukiwać, co moim zdaniem jest głębokim związkiem między pewną podstawową koncepcją / techniką w TCS i badanie ewolucji. (Oczywiście, jeśli ktoś ma odmienne zdanie, powiedz to!)

Myślę, że ewolucyjna teoria gier lub ewolucyjna dynamika mogłyby skorzystać z większej liczby podejść algorytmicznych (takich jak Livnat i in.). Na konkretny przykład widzę możliwe miłe rozszerzenia do rozważania ewoluowalnych agentów o (ograniczonych) zdolnościach konstytucyjnych, modelowanych np. Przez skończone maszyny stanów. Pozwoliłoby nam to zbadać ewolucję dyskretnych czynników za pomocą bardziej złożonych strategii warunkowych, takich jak tit-for-tat. Przyglądałem się temu trochę i słyszałem o wstępnych pracach w tym zakresie, ale nie mam żadnych cytatów.

Ale nawet ten przykład jest dość prostą aplikacją, więc wyniki tego rodzaju prawdopodobnie nadal nie odpowiedziałyby na twoje pytanie.

Z drugiej strony mam znacznie większe nadzieje na naukę teorii, która może pewnego dnia mieć dobre powiązania z dynamiką ewolucyjną. Ale nie znam się zbyt dobrze na tych wynikach, więc zostawię to do komentowania przez innych.

(Edytuj) Jednym z potencjalnych powiązań, o którym należy wspomnieć, jest znany związek uczenia się (np. „Problem eksperta”) i konwergencji do równowagi w powtarzanych grach. W szczególności, na przykład (w szczegółach komentarz Aarona Rotha), w powtarzanej grze, jeśli wszyscy gracze grają w strategie nie żałowania, wówczas poprzedni rozkład akcji zbiega się z grubą, skorelowaną równowagą pojedynczej rundy. Może być coś ciekawego i nowego do powiedzenia na ten temat, patrząc z perspektywy ewolucyjnej teorii gier; Nie jestem pewny.

usul
źródło
2
Dziękuję za twoje przemyślenia, ale to nie jest odpowiedź. Jestem w pełni świadomy (jak wspominam w drugim zdaniu) grup takich jak Nowak, które opierają się głównie na narzędziach inspirowanych fizyką. Pytanie nie dotyczy tego, czy mogą istnieć połączenia (jak już wiem, że istnieją), czy też większość pola je realizuje (jak już wiem, że nie), ale przykłady wczesnych kroków, które ludzie podjęli z punktu widzenia TCS .
Artem Kaznatcheev
Zgadza się, próbowałem odpowiedzieć przecząco (o ile chodzi o dynamikę ewolucji) tak pomocnie, jak to możliwe.
usul
Teraz jestem trochę zdezorientowany, czy uważasz, że Livnat i in. Są pozytywną odpowiedzią na twoje pytanie, czy nie? (Poza tym jest to niesamowite / ciekawe pytanie i mam nadzieję, że otrzymacie o wiele więcej / lepsze odpowiedzi!)
usul
1
LPDF08 i nowsze prace uzupełniające są pozytywnymi przykładami, podobnie jak praca i kontynuacja Valiant. Wykluczam je jednak z odpowiedzi tylko dlatego, że już je znam.
Artem Kaznatcheev
3
Szybki wybór: zgodnie ze standardowym pojęciem żalu historia empiryczna gry bez żalu zbiega się jedynie z zestawem „zgrubnych” skorelowanych równowag w grach ogólnych. Potrzebne jest silniejsze pojęcie żalu „wewnętrznego” lub „zamiany”, aby zbliżyć się do zestawu skorelowanych równowag. Zwykła gra bez żalu zbiega się z równowagą Nasha w grach o sumie zerowej. Może to być bardziej odpowiednie dla pojęć ewolucyjnych - skorelowane równowagi potrzebują urządzenia korelującego do wdrożenia i nie jest jasne, co by to było w kontekście ewolucji.
Aaron Roth
3

Jedna (ostatnia) linia pracy związana z ewolucją bezpłciową z zastosowaniami do projektowania narkotyków i wykorzystaniem interesujących technik łańcucha Markowa: ewolucja bez seksu

anonimowy
źródło
2

Oto nowy znaczący artykuł łączący ewolucję / genetykę z algorytmem Multiplicative Weight Update, również profilowany przez fundację Simonsa i zawiera współautora cytowanego w pytaniu (Papadimitriou):

  • Algorytmy, gry i ewolucja Erick Chastain, Adi Livnat, Christos Papadimitriou i Umesh Vazirani

    Nawet najbardziej doświadczeni studenci ewolucji, poczynając od samego Darwina, od czasu do czasu wyrażali zdumienie, że mechanizm doboru naturalnego wytworzył całe Życie, jakie widzimy wokół nas. Istnieje obliczeniowy sposób wyrażenia tego samego zdumienia: „Jaki algorytm mógłby to wszystko osiągnąć w ciągu zaledwie trzech i pół miliarda lat?” W tym artykule proponujemy odpowiedź: Wykazujemy, że w reżimie słabej selekcji standard równania genetyki populacyjnej opisujące naturalną selekcję w obecności płci stają się identyczne z tymi z powtarzanej gry między genami granymi zgodnie z multiplikatywnymi aktualizacjami wagi (MWUA), algorytmem znanym w informatyce jako zaskakująco potężnym i wszechstronnym. MWUA maksymalizuje kompromis między skumulowaną wydajnością a entropią,

vzn
źródło
0

Ostatnie szeroko zakrojone badanie Mishy Gromov Kryształy, białka, stabilność i izoperymetria (Bull. Amer. Math. Soc. 48 (2011), 229-257) jest bogatą tematyką matematyczną związaną z biologią (w tym wiele tematów związanych z TCS metody).

Pytanie zadało listę

Wyniki wykorzystujące nowoczesne i nietrywialne aspekty informatyki […] o bardzo dyskretnej naturze […] za pomocą soczewki algorytmicznej

Ankieta Gromova jest bardziej zorientowana na ogólne pytania matematyczne niż na określone programy badawcze. Tak więc ankietę można odczytać jako wybór Gromowa

Pytania, które (potencjalnie) wykorzystują nowoczesne i nietrywialne aspekty informatyki […] (z których wiele) mają bardzo dyskretny charakter […] poprzez (co często jest) soczewkę algorytmiczną.

Jako lista pytań bez odpowiedzi, a nie lista znanych wyników, artykuł Gromova stawia czytelnikowi znaczące wymagania twórcze.

Być może główną zaletą tego artykułu jest to, że autorem jest… Misha Gromov !

John Sidles
źródło
1
To fajny artykuł, ale nie rozumiem, jak odnosi się on do ewolucji i ekologii. Istnieje kilka przemijających odniesień do ewolucji (najwyraźniej w rozdziałach 4 i 6, gdzie argumentuje się, że ewolucja powinna promować symetrię). Absolutnie nie ma wzmianki o ekologii. Co więcej, chociaż jest to dobre podejście matematyczne, nie widzę skupienia algorytmicznego ani obliczeniowego. Czy potrafisz rozszerzyć swoją odpowiedź, aby wyjaśnić znaczenie tego artykułu dla patrzenia na ewolucję i ekologię za pomocą soczewki algorytmicznej? W przeciwnym razie wydaje się to bardziej odpowiednie jako komentarz, a nie odpowiedź.
Artem Kaznatcheev
@Artem, odpowiedź została rozszerzona zgodnie z żądaniem. Dziękuję Artem.
John Sidles,
-2

niestety wydaje się, że istnieje tu ogromna luka w zainteresowaniach naukowych / znaczeniu naukowym w porównaniu z faktycznymi badaniami naukowymi, o czym świadczą również wysokie głosy w tym pytaniu w porównaniu z niską liczbą głosów w odpowiedziach (i nie spodziewając się tutaj przeciwstawić temu wzorowi). wydaje się, że jest to bardzo ważny program studiów / badań w centrum teorii naukowej we wczesnym okresie niemowlęcym. mamy teraz narzędzia do przeprowadzania eksperymentów obliczeniowych, które mogą poddać teorię ewolucji ograniczeniom falsyfikowalności przynajmniej w tym sensie, że jeśli teoria ewolucji jest dokładna, powinna istnieć możliwość jej modelowania / symulacji przynajmniej z grubsza na komputerze; ale wydaje się, że bardzo mało próbuje tego projektu (co z pewnością jest niezwykle ambitne co najmniej).

na przykład, czy istnieje jakaś symulacja, która pasuje do znanych zmian ewolucyjnych w drzewie filogenetycznym na przestrzeni miliardów lat? wyzwanie jest interdyscyplinarne i przekrojowe i wydaje się, że nie pasuje dokładnie / dokładnie do istniejących dziedzin / granic naukowych. Co ciekawe, nawet nie wydaje się, aby istniał żaden poważny naukowiec lub biolog, który wyraźnie proponowałby taki program badawczy.

oto kilka innych referencji, które z pewnością nie pasują ściśle do wąskich kryteriów przedstawionych w pytaniu, ale mogą być z grubsza zbliżone:

  • w dziedzinie „sztucznego życia” istnieje zainteresowanie próbą symulacji warunków, które doprowadziły do ​​samoorganizacji „zupy chemicznej” w jakieś formy quasi-życia, które wykazują podstawowe aspekty replikacji itp. np .: EVOGRID: Podejście do obliczeniowych początków życia Ender Damer Damer

    Dążenie do zrozumienia mechanizmów powstawania życia na Ziemi może zostać wzmocnione przez symulacje komputerowe prawdopodobnych stadiów powstawania życia z nie-życia na poziomie molekularnym. Ta klasa symulacji mogłaby następnie wspierać testy i walidację poprzez równoległe laboratoryjne eksperymenty chemiczne. To połączenie komponentu obliczeniowego lub „cyber” z równoległym badaniem wysiłkowym w abiogenezie chemicznej można nazwać podejściem cyberbiogenezy. Głównym wyzwaniem technologicznym w dążeniach do cyberbiogenezy jest zaprojektowanie komputerowych modeli symulacyjnych umożliwiających de novo pojawienie się prebiotycznych i biologicznych wirtualnych struktur molekularnych i procesów poprzez wiele progów złożoności. Teza ta podejmuje wyzwanie polegające na zaprojektowaniu, wdrożeniu i analizie jednego takiego modelu symulacyjnego.

  • GRUPOWY MODEL WYBORU WOJNY TERYTORIALNEJ, XENOFOBII I ALTRUIZMU U LUDZI I INNYCH PRIMATÓW Agner Fog

    Streszczenie: Teoretyczny model wojen o terytoria grupowe pokazuje, że cechy behawioralne, takie jak wojna kooperacyjna, sprawiedliwość, altruizm i wykluczenie z zewnątrz mogły współwystępować u wyższych naczelnych i prehistorycznych ludzi. Omówiono warunki wojny terytorialnej jako skutecznego mechanizmu selekcji grup. Warunki te mogły występować w społeczeństwach plemiennych w czasach prehistorycznych, ale nie w czasach współczesnych. Geograficzną ewolucję terytoriów ilustrują symulacje komputerowe.

  • co ciekawe, wydaje się, że pytanie jest bardzo podobne do: komputerowej symulacji procesu ewolucji na Ziemi datowanej na 2008 r. przy przepełnieniu stosu z kilkoma różnymi referencjami.

vzn
źródło
zwróć uwagę, że projekt „początki życia” faktycznie próbuje symulować „ewolucję” w bardzo pierwotnych początkach, tj. na etapie sprzed DNA , więc pod pewnymi względami można uznać, że jest to „pre-biologia” ...
vzn