Ekologi dan evolusi melalui lensa algoritmik

Studi ekologi dan evolusi menjadi semakin matematis, tetapi sebagian besar alat teoretis tampaknya berasal dari fisika. Namun, dalam banyak kasus masalah memiliki sifat yang sangat berbeda (lihat misalnya SLBS00 ) dan dapat mengambil manfaat dari perspektif ilmu komputer . Namun, saya menyadari hanya beberapa hasil serius dari TCS yang mencoba menyentuh pertanyaan spesifik dalam ekologi dan evolusi. Dua arah yang muncul dalam pikiran adalah:

1. Livnat, A., Papadimitriou, C., Dusho, J., & Feldman, MW [2008] "Sebuah teori campuran untuk peran seks dalam evolusi" PNAS 105 (50): 19803-19808. [ pdf ]

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

Yang pertama menerapkan ide dari analisis algoritma genetika untuk menunjukkan perbedaan kualitatif antara cara organisme seksual dan aseksual berperilaku dalam lanskap kebugaran, dan telah mengarah pada tindak lanjut yang membantu membenarkan modularitas yang diamati. Yang terakhir menghubungkan teori evolusi dan pembelajaran komputasi, untuk mencoba membuktikan evolvabilitas dan hasil impositibilitas. Ini telah mempengaruhi sekumpulan kecil kertas, tetapi kebanyakan oleh ilmuwan komputer lainnya.

Apakah ada lebih banyak hasil di pembuluh darah ini? Apakah aplikasi ilmu komputer teoretis mereka yang dalam / non-sepele untuk memahami ekologi dan evolusi seperti yang dipelajari oleh para ahli biologi?

Catatan

• Saya tidak tertarik dengan hasil rekayasa genetika atau algoritma evolusioner umum. Meskipun ini adalah bagian yang sangat menarik dan mengasyikkan dari ilmu komputer, hubungannya dengan evolusi seperti yang dipelajari oleh para ahli biologi sering kali dangkal. Terkadang (seperti pada LPDF08) koneksi konkret dibuat, tetapi sebagian besar hasil standar tidak menarik secara biologis, dan karenanya saya tidak tertarik pada mereka dalam posting ini.

• Bioinformatika adalah bidang terdekat, tetapi juga bukan yang saya cari. Meskipun dapat digunakan untuk merekonstruksi hal-hal seperti pohon filogenetik dan dengan demikian membantu evolusi / ekologi, aspek CS teoritis tidak menjadi pusat perhatian. Di sini, hasil CS tampaknya sebagian besar untuk menyempurnakan alat yang dapat digunakan sebagian besar sebagai kotak hitam dari dalam teori yang sudah mapan, dan tidak untuk membangun atau memperluas teori biologis baru.

• Saya lebih suka hasil yang menggunakan aspek modern-ish dan non-sepele dari ilmu komputer untuk mempengaruhi biologi pada tingkat teori (tapi masih relevan dengan ahli biologi). Karena itu, saya tidak begitu tertarik pada hal-hal seperti metabiologi Chaitin .

Pertanyaan-pertanyaan Terkait

• Pernyataan yang dapat dibuktikan tentang algoritma genetika

• Lensa algoritmik dalam ilmu sosial

• Sumber untuk Teori Permainan Evolusi Algoritma

• Kompleksitas komputasi dalam keuangan kuantitatif

Hmmm. Sejauh teori evolusi / permainan evolusi berjalan, pendapat pribadi saya adalah bahwa makalah Livnat et al yang Anda sebutkan, sementara pekerjaan yang sangat bagus, tampaknya tidak jatuh "di luar" pendekatan matematika standar untuk teori permainan evolusi (lihat karya oleh misalnya Kelompok Martin Nowak , seperti makalah '05 "Evolutionary Dynamics on Graphs" ).

Jadi dua klaim yang akan saya buat adalah: Pertama, sementara ini adalah beberapa karya besar dalam Evolutionary Dynamics yang kebetulan dilakukan oleh para ilmuwan komputer, saya tidak akan secara pribadi menempatkannya di dalam Theoretical Computer Science atau sebagai semua yang terkait erat dengan TCS, kecuali untuk hubungan yang sudah ada sebelumnya antara teori permainan evolusioner dan algoritmik. Kedua, jika Anda cenderung tidak setuju, maka Anda mungkin akan terkejut betapa banyak bidang Evolusi Evolusi telah dibagikan / dibagikan dengan TCS secara filosofis (tapi saya masih tidak yakin tekniknya sama).

Secara umum, saya akan cenderung mengatakan bahwa tidak ada pekerjaan di sepanjang garis ini, termasuk referensi yang Anda sebutkan, yang sesuai dengan apa yang Anda cari, yang saya pikir merupakan hubungan yang mendalam antara beberapa konsep inti / teknik dalam TCS dan studi evolusi. (Tentu saja, jika ada yang memiliki pendapat berbeda, tolong katakan begitu!)

Saya memang berpikir bahwa teori permainan evolusioner atau dinamika evolusi dapat mengambil manfaat dari pendekatan yang lebih algoritmik, (seperti Livnat et al). Untuk contoh tertentu, saya melihat kemungkinan ekstensi yang bagus untuk mempertimbangkan agen yang dapat dikembangkan dengan kemampuan komparatif (terbatas), seperti yang dimodelkan oleh misalnya mesin negara hingga. Ini akan memungkinkan kita untuk mempelajari evolusi agen diskrit dengan strategi kondisional yang lebih kompleks seperti gayung bersambut. Saya telah melihat sedikit ini dan mendengar tentang beberapa pekerjaan awal sepanjang garis-garis ini tetapi tidak memiliki referensi untuk dikutip.

Tetapi bahkan contoh ini adalah aplikasi yang cukup mudah, jadi hasil semacam ini mungkin masih tidak akan menjawab pertanyaan Anda.

Saya memiliki harapan yang jauh lebih tinggi di sisi lain untuk belajar teori, yang suatu hari nanti dapat membuat koneksi yang bagus dengan dinamika evolusi juga. Tapi, saya tidak terlalu akrab dengan hasil itu jadi saya akan meninggalkan itu untuk orang lain untuk mengomentari.

(Sunting) Salah satu koneksi potensial yang harus disebutkan adalah hubungan pembelajaran yang diketahui (misalnya "masalah ahli") dan konvergensi dengan keseimbangan dalam permainan yang berulang. Khususnya, misalnya (lihat komentar Aaron Roth untuk perincian), dalam permainan yang diulangi, jika semua pemain memainkan strategi tanpa penyesalan, maka distribusi tindakan di masa lalu menyatu ke keseimbangan berkorelasi kasar dari permainan satu putaran. Mungkin ada sesuatu yang menarik dan baru untuk dikatakan tentang ini sebagaimana dilihat melalui lensa teori permainan evolusioner; Saya tidak yakin.

Satu jalur kerja (terkini) yang terkait dengan evolusi aseksual dengan aplikasi untuk merancang obat dan menggunakan teknik rantai Markov yang menarik: Evolusi Tanpa Seks

Inilah makalah baru yang menghubungkan evolusi / genetika dengan algoritma Multiplicative Weight Update, juga baru saja diprofilkan oleh yayasan Simons & termasuk rekan penulis yang dikutip dalam pertanyaan (Papadimitriou):

• Algoritma, permainan, dan evolusi Erick Chastain, Adi Livnat, Christos Papadimitriou, dan Umesh Vazirani

  Bahkan siswa evolusi yang paling berpengalaman, mulai dari Darwin sendiri, kadang-kadang mengungkapkan keheranan bahwa mekanisme seleksi alam telah menghasilkan seluruh Kehidupan seperti yang kita lihat di sekitar kita. Ada cara komputasi untuk mengartikulasikan keheranan yang sama: "Algoritma apa yang mungkin dapat mencapai semua ini hanya dalam tiga setengah miliar tahun?" Dalam makalah ini kami mengusulkan jawaban: Kami menunjukkan bahwa dalam rezim seleksi yang lemah, standar Persamaan genetika populasi yang menggambarkan seleksi alam di hadapan jenis kelamin menjadi identik dengan permainan berulang antara gen yang dimainkan sesuai dengan pembaruan bobot multiplikatif (MWUA), sebuah algoritma yang dikenal dalam ilmu komputer secara mengejutkan sangat kuat dan serbaguna. MWUA memaksimalkan tradeoff antara kinerja kumulatif dan entropi,

Survei luas baru-baru ini Misha Gromov Kristal, protein, stabilitas dan isoperimetri (Bull. Amer. Math. Soc. 48 (2011), 229-257) adalah uraian kaya topik matematika yang berhubungan dengan biologi (termasuk banyak topik yang terhubung ke TCS metode).

Pertanyaannya meminta daftar

Hasil yang menggunakan aspek-aspek modern-ish dan non-sepele dari ilmu komputer [...] yang sangat berbeda [...] melalui lensa algoritmik

Survei Gromov lebih berorientasi pada pertanyaan matematika umum daripada program penelitian tertentu. Dengan demikian survei dapat dibaca sebagai pilihan Gromov untuk

Pertanyaan yang (berpotensi) menggunakan aspek modern-ish dan non-sepele dari ilmu komputer [...] (banyak di antaranya) adalah sifat yang sangat terpisah [...] melalui (yang sering) lensa algoritmik.

Sebagai daftar pertanyaan yang tidak dijawab daripada daftar hasil yang diketahui, artikel Gromov menempatkan tuntutan kreatif yang signifikan pada pembaca.

Mungkin kebajikan utama artikel ini adalah penulisnya adalah ... Misha Gromov !

sayangnya tampaknya ada kesenjangan besar di sini dalam kepentingan / signifikansi ilmiah vs penelitian ilmiah aktual seperti juga dibuktikan dalam suara tinggi pada pertanyaan ini vs suara rendah pada jawaban (& tidak berharap untuk menentang pola itu di sini). tampaknya menjadi program studi / penelitian yang sangat penting di jantung teori ilmiah di awal masa pertumbuhannya. kita sekarang memiliki alat untuk melakukan eksperimen komputasi yang dapat menyebabkan teori evolusi menjadi kendala pemalsuan setidaknya dalam arti bahwa jika teori evolusi akurat, maka mestinya dimungkinkan untuk membuat model / mensimulasikannya setidaknya secara kasar di komputer; tetapi tampaknya ada sedikit upaya proyek (yang, tentu saja, sangat ambisius untuk sedikitnya).

misalnya, apakah ada beberapa simulasi yang cocok dengan perubahan evolusi yang diketahui dalam pohon filogenetik selama milyaran tahun? tantangannya adalah interdisipliner dan lintas bidang dan tampaknya tidak cocok dengan tepat / tepat ke bidang / batas ilmiah yang ada. bahkan tidak ada ilmuwan atau ahli biologi besar yang secara eksplisit mengusulkan program penelitian semacam itu.

berikut adalah beberapa ref lainnya muncul yang pasti tidak akan cocok ketat ke dalam kriteria sempit diuraikan dalam pertanyaan tapi mungkin kira-kira dekat:

• di bidang "kehidupan buatan" ada beberapa minat dalam mencoba mensimulasikan kondisi yang menyebabkan "sup kimia" mengorganisir diri menjadi semacam bentuk kehidupan semu yang menunjukkan aspek-aspek dasar replikasi dan sebagainya. misalnya: THE EVOGRID: Suatu Pendekatan terhadap Asal-usul Komputasi Kehidupan Endeavours Damer

  Upaya untuk memahami mekanisme asal usul kehidupan di Bumi dapat ditingkatkan dengan simulasi komputer tentang tahapan yang masuk akal dalam kemunculan kehidupan dari non-kehidupan di tingkat molekuler. Kelas simulasi ini kemudian dapat mendukung pengujian dan validasi melalui percobaan kimia laboratorium paralel. Kombinasi komponen komputasi, atau "cyber" ini dan investigasi usaha paralel dalam abiogenesis kimia dapat disebut pendekatan cyberbiogenesis. Tantangan utama teknologi untuk upaya cyberbiogenesis adalah merancang model simulasi komputer yang memungkinkan munculnya struktur dan proses virtual molekul prebiotik dan biologis melalui berbagai ambang batas kompleksitas. Tesis ini mengambil tantangan merancang, mengimplementasikan dan menganalisis satu model simulasi tersebut.

• MODEL SELEKSI KELOMPOK PERANG TERITORIAL, XENOPHOBIA DAN ALTRUISME DALAM MANUSIA DAN PRIMAT LAINNYA Agner Fog

  Abstrak: Model teoritis perang atas wilayah kelompok menunjukkan bahwa sifat-sifat perilaku seperti perang kooperatif, keadilan, altruisme, dan pengucilan orang luar mungkin telah terkoordinasi dengan primata yang lebih tinggi dan manusia prasejarah. Kondisi untuk perang teritorial untuk menjadi mekanisme pemilihan kelompok yang efektif dibahas. Kondisi-kondisi ini mungkin ada di masyarakat suku pada zaman prasejarah tetapi tidak di zaman modern. Evolusi geografis wilayah diilustrasikan dengan simulasi komputer.

• pertanyaannya tampaknya sangat mirip dengan: simulasi komputer dari proses evolusi di bumi yang berasal dari tahun 2008 pada stack overflow dengan beberapa ref misc.