Boole ağı - Boolean network

Ağ bilimi
Internet_map_1024.jpg
Ağ türleri
Grafikler
Özellikleri
Türler
Modeller
Topoloji
Dinamikler
  • Listeler
  • Kategoriler
  • Kategori: Ağ teorisi
  • Kategori: Grafik teorisi
Boolean Ağının durum uzayı N = 4 düğümler ve K = 1 bağlantılar düğüm başına. Düğümler açılabilir (kırmızı) veya kapatılabilir (mavi). İnce (siyah) oklar, ekranın girişlerini sembolize eder. Boole işlevi bu, her düğüm için basit bir "kopyalama" işlevidir. Kalın (gri) oklar, eşzamanlı güncellemenin ne yaptığını gösterir. Toplamda 6 (turuncu) var çekiciler 4 tanesi sabit noktalar.

Bir Boole ağı ayrık bir kümeden oluşur boole değişkenleri her biri bir Boole işlevi (muhtemelen her değişken için farklıdır), bu değişkenlerin bir alt kümesinden girdiler alan ve atandığı değişkenin durumunu belirleyen çıktı. Bu işlevler kümesi, değişkenler kümesi üzerinde bir topoloji (bağlanabilirlik) belirler ve bunlar daha sonra bir ağ. Genellikle sistemin dinamikleri ayrı olarak alınır. Zaman serisi zaman zaman tüm ağın durumu t+1, her bir değişkenin fonksiyonunun ağın durumu üzerinde o anda değerlendirilmesiyle belirlenir t. Bu yapılabilir eşzamanlı olarak veya asenkron.[1]

Boole ağları, düzenleyici ağları modellemek için biyolojide kullanılmıştır. Boole ağları, genlerin basit ikili anahtarlar olmadığı durumlarda genetik gerçekliğin kaba bir basitleştirmesi olsa da, ifade edilen ve bastırılan genlerin doğru modelini doğru bir şekilde yakaladıkları birkaç durum vardır.[2][3] Görünüşte matematiksel kolay (eşzamanlı) model ancak 2000'lerin ortasında tam olarak anlaşıldı.[4]

Klasik model

Boole ağı, belirli bir tür sıralı dinamik sistem, burada zaman ve durumlar ayrıktır, yani hem değişkenler kümesi hem de zaman serisindeki durumlar kümesi her birinin bir birebir örten bir tamsayı dizisine. Bu tür sistemler hücresel otomata ağlarda, kurulduklarında her bir düğümün hepsinden rastgele seçilen bir kurala sahip olması dışında 22K ile olası olanlar K girdiler. İle K = 2 2. sınıf davranışı hakim olma eğilimindedir. Ama için K> 2, görülebilen davranış, rastgele bir haritalama için tipik olana hızlı bir şekilde yaklaşır. 2N devletleri N temel düğümlerin kendisi esasen rastgele bağlanmıştır.[5]

Bir rastgele Boole ağı (RBN), belirli bir boyuttaki tüm olası boole ağları kümesinden rastgele seçilen bir tanesidir, N. O halde, bu tür ağların beklenen özelliklerinin, tüm olası ağlar topluluğunun çeşitli istatistiksel özelliklerine nasıl bağlı olduğu, istatistiksel olarak incelenebilir. Örneğin, ortalama bağlantı değiştikçe RBN davranışının nasıl değiştiği incelenebilir.

İlk Boole ağları tarafından önerildi Stuart A. Kauffman 1969'da rastgele modelleri genetik düzenleme ağları[6] ancak matematiksel anlayışları ancak 2000'lerde başladı.[7][8]

Çekiciler

Bir Boole ağında yalnızca 2N olası durumlar, bir yörünge er ya da geç daha önce ziyaret edilen bir duruma ulaşacaktır ve bu nedenle, dinamikler deterministik olduğundan, yörünge sabit bir duruma veya bir döngünün içine düşecektir. cazibe merkezi (dinamik sistemlerin daha geniş alanında, bir döngü yalnızca, eğer ondan kaynaklanan tedirginlikler ona geri dönerse bir çekicidir). Çekicinin yalnızca tek bir durumu varsa, buna nokta çekicive çeken birden fazla durumdan oluşuyorsa, buna döngü çekicisi. Bir çekiciye götüren durumlara, havza çekicinin. Yalnızca yörüngelerin başlangıcında meydana gelen durumlar (hiçbir yörünge yol açmaz. -e onlara) denir cennet Bahçesi eyaletler[9] ve ağın dinamikleri bu durumlardan çekicilere doğru akmaktadır. Bir çekiciye ulaşmak için geçen süre denir geçici zaman.[4]

Büyüyen bilgisayar gücü ve görünüşte basit olan modelin artan anlayışıyla, farklı yazarlar çekicilerin ortalama sayısı ve uzunluğu için farklı tahminler verdiler, burada temel yayınların kısa bir özeti.[10]

YazarYılOrtalama çekici uzunluğuOrtalama çekici sayısıyorum Yap
Kauffmann [6]1969
Bastolla / Parisi[11]1998güç yasasından daha hızlı, güç yasasından daha hızlı, ilk sayısal kanıtlar
Bilke / Sjunnesson[12]2002sistem boyutu ile doğrusal,
Socolar / Kauffman[13]2003doğrusaldan daha hızlı, ile
Samuelsson / Troein[14]2003süper polinom büyüme, matematiksel kanıt
Mihaljev / Drossel[15]2005güç yasasından daha hızlı, güç yasasından daha hızlı,

istikrar

Dinamik sistemler teorisinde, bir ağın çekicilerinin yapısı ve uzunluğu, ağın dinamik aşamasına karşılık gelir. Boole ağlarının kararlılığı bağlantılarına bağlıdır düğümler. Bir Boole ağı, kararlı, kritik veya kaotik davranış. Bu fenomen, ortalama düğüm bağlantı sayısının kritik bir değeri tarafından yönetilir () ve ile karakterize edilebilir Hamming mesafesi mesafe ölçüsü olarak. İstikrarsız rejimde, başlangıçta birbirine yakın olan iki devlet arasındaki mesafe ortalama olarak zaman içinde katlanarak büyürken, istikrarlı rejimde katlanarak azalır. Bunda, "başlangıçta yakın durumlar" ile, Hamming mesafesinin düğüm sayısına kıyasla küçük olduğu anlamına gelir () ağda.

İçin N-K-modeli[16] ağ kararlı ise kritik eğer ve eğer kararsızsa .

Belirli bir düğümün durumu göre güncellenir doğruluk şeması, çıktıları rastgele doldurulan. belirli bir dizi giriş sinyaline bir kapama çıkışı atama olasılığını belirtir.

Eğer her düğüm için, kararlı ve kaotik aralık arasındaki geçiş şunlara bağlıdır: . Göre Bernard Derrida ve Yves Pomeau[17]ortalama bağlantı sayısının kritik değeri .

Eğer sabit değildir ve dereceler ile dış dereceler arasında bir korelasyon yoktur, kararlılık koşulları tarafından belirlenir [18][19][20] Ağ kararlıdır, eğer kritik eğer ve eğer kararsızsa .

Kararlılık koşulları, ağlar için aynıdır. ölçeksiz topoloji derece içi ve dışı dağıtımın bir güç yasası dağılımı olduğu yerlerde: , ve , çünkü bir düğümden gelen her dış bağlantı, diğerine bir iç bağlantıdır.[21]

Duyarlılık, belirli bir düğümün Boole işlevinin çıktısının, girdisi değişirse değişme olasılığını gösterir. Rastgele Boole ağları için,. Genel durumda, ağın istikrarı en büyük özdeğer matrisin , nerede , ve ... bitişik matris ağın.[22] Ağ kararlıdır, eğer kritik eğer , eğer kararsız .

Modelin varyasyonları

Diğer topolojiler

Bir tema çalışmaktır farklı temel grafik topolojileri.

  • Homojen durum, basitçe ünlü olana indirgeme olan bir ızgarayı ifade eder. Ising modeli.
  • Ölçeksiz Boole ağları için topolojiler seçilebilir.[23] Güç kanununda yalnızca derece dağılımının dağıtıldığı durum ayırt edilebilir,[24] ya da sadece dış derece dağılımı ya da her ikisi.

Diğer güncelleme şemaları

Klasik Boole ağları (bazen CRBN, yani Klasik Rasgele Boolean Ağı) eşzamanlı olarak güncellenir. Genlerin genellikle durumlarını aynı anda değiştirmemesi gerçeğinden motive olan,[25] farklı alternatifler tanıtıldı. Ortak bir sınıflandırma[26] takip ediliyor:

  • Deterministik eşzamansız güncellenmiş Boole ağları (DRBNs) eşzamanlı olarak güncellenmez, ancak belirleyici bir çözüm hala mevcuttur. Bir düğüm ben ne zaman güncellenecek t ≡ Qben (mod Pben) nerede t zaman adımıdır.[27]
  • En genel durum, tam stokastik güncellemedir (GARBN, genel eşzamansız rastgele boole ağları). Burada, güncellenecek her hesaplama adımında bir (veya daha fazla) düğüm seçilir.
  • Kısmen Gözlemlenen Boolean Dinamik Sistem (POBDS)[28][29][30][31] sinyal modeli, Boolean durum vektörünün doğrudan gözlemlenebilirlik varsayımını ortadan kaldırarak ve gözlem sürecinde belirsizliğe izin vererek, pratikte karşılaşılan senaryoyu ele alarak önceki tüm deterministik ve stokastik Boolean ağ modellerinden farklıdır.

Boolean Ağlarının Uygulanması

Sınıflandırma

  • Ölçeklenebilir Optimal Bayes Sınıflandırması[32] potansiyel model belirsizliğini hesaba katan optimum bir yörünge sınıflandırması geliştirdi ve ayrıca, optimal çözümden çok daha düşük karmaşıklığa sahip büyük ağlar için oldukça ölçeklenebilir olan parçacık tabanlı bir yörünge sınıflandırması önerdi.

Ayrıca bakınız

Referanslar

  1. ^ Naldi, A .; Monteiro, P. T .; Midye, C .; Kestler, H. A .; Thieffry, D .; Xenarios, I .; Saez-Rodriguez, J .; Helikar, T .; Chaouiya, C. (25 Ocak 2015). "CoLoMoTo ile mantıksal modelleme standartlarının ve araçlarının ortaklaşa geliştirilmesi". Biyoinformatik. 31 (7): 1154–1159. doi:10.1093 / biyoinformatik / btv013. PMID  25619997.
  2. ^ Albert, Réka; Othmer, Hans G (Temmuz 2003). "Düzenleyici etkileşimlerin topolojisi, Drosophila melanogaster'daki segment polarite genlerinin ekspresyon modelini tahmin eder". Teorik Biyoloji Dergisi. 223 (1): 1–18. CiteSeerX  10.1.1.13.3370. doi:10.1016 / S0022-5193 (03) 00035-3. PMC  6388622. PMID  12782112.
  3. ^ Li, J .; Bench, A. J .; Vassiliou, G. S .; Fourouclas, N .; Ferguson-Smith, A. C .; Green, A.R. (30 Nisan 2004). "İnsan miyeloid malignitelerinde silinmiş kromozom 20 bölgesinde bulunan bir polikomb aile üyesi olan insan L3MBTL geninin baskısı". Ulusal Bilimler Akademisi Bildiriler Kitabı. 101 (19): 7341–7346. Bibcode:2004PNAS..101.7341L. doi:10.1073 / pnas.0308195101. PMC  409920. PMID  15123827.
  4. ^ a b Drossel, Barbara (Aralık 2009). "Rastgele Boole Ağları". Schuster, Heinz Georg (ed.). Bölüm 3. Rastgele Boole Ağları. Doğrusal Olmayan Dinamikler ve Karmaşıklık İncelemeleri. Wiley. s. 69–110. arXiv:0706.3351. doi:10.1002 / 9783527626359.ch3. ISBN  9783527626359. S2CID  119300231.
  5. ^ Wolfram Stephen (2002). Yeni Bir Bilim Türü. Champaign, Illinois: Wolfram Media, Inc. s.936. ISBN  978-1579550080. Alındı 15 Mart 2018.
  6. ^ a b Kauffman, Stuart (11 Ekim 1969). Rastgele Genetik Kontrol Ağlarında "Homeostaz ve Farklılaşma". Doğa. 224 (5215): 177–178. Bibcode:1969Natur.224..177K. doi:10.1038 / 224177a0. PMID  5343519. S2CID  4179318.
  7. ^ Aldana, Maximo; Bakırcı, Susan; Kadanoff, Leo P. (2003). Rastgele Bağlaşımlı Boole Dinamikleri. Doğrusal Olmayan Bilimlerde Perspektifler ve Sorunlar. sayfa 23–89. arXiv:nlin / 0204062. doi:10.1007/978-0-387-21789-5_2. ISBN  978-1-4684-9566-9. S2CID  15024306.
  8. ^ Gershenson Carlos (2004). "Rastgele Boolean Ağlarına Giriş". Bedau, M., P. Husbands, T. Hutton, S. Kumar ve H. Suzuki (Eds.) Workshop and Tutorial Proceedings, Dokuzuncu Uluslararası Canlı Sistemlerin Simülasyonu ve Sentezi Konferansı (ALife IX). Pp. 2004: 160–173. arXiv:nlin.AO/0408006. Bibcode:2004nlin ...... 8006G.
  9. ^ Wuensche, Andrew (2011). Ayrık dinamikleri keşfetmek: [DDLab kılavuzu: hücresel otomata, rasgele Boole ve çok değerli yeni çalışmaları [sic] ve ötesini araştırmak için araçlar]. Frome, İngiltere: Luniver Press. s. 16. ISBN  9781905986316. Alındı 12 Ocak 2016.
  10. ^ Greil Florian (2012). "Modelleme Çerçevesi Olarak Boole Ağları". Bitki Biliminde Sınırlar. 3: 178. doi:10.3389 / fpls.2012.00178. PMC  3419389. PMID  22912642.
  11. ^ Bastolla, U .; Parisi, G. (Mayıs 1998). "Kauffman ağlarının modüler yapısı". Physica D: Doğrusal Olmayan Olaylar. 115 (3–4): 219–233. arXiv:cond-mat / 9708214. Bibcode:1998PhyD..115..219B. doi:10.1016 / S0167-2789 (97) 00242-X. S2CID  1585753.
  12. ^ Bilke, Sven; Sjunnesson, Fredrik (Aralık 2001). "Kauffman modelinin kararlılığı". Fiziksel İnceleme E. 65 (1): 016129. arXiv:cond-mat / 0107035. Bibcode:2002PhRvE..65a6129B. doi:10.1103 / PhysRevE.65.016129. PMID  11800758. S2CID  2470586.
  13. ^ Socolar, J .; Kauffman, S. (Şubat 2003). "Sıralı ve Kritik Rastgele Boolean Ağlarında Ölçeklendirme". Fiziksel İnceleme Mektupları. 90 (6): 068702. arXiv:cond-mat / 0212306. Bibcode:2003PhRvL..90f8702S. doi:10.1103 / PhysRevLett.90.068702. PMID  12633339. S2CID  14392074.
  14. ^ Samuelsson, Björn; Troein, Carl (Mart 2003). "Kauffman Ağlarında Çekiciler Sayısında Süper Polinom Büyüme". Fiziksel İnceleme Mektupları. 90 (9): 098701. Bibcode:2003PhRvL..90i8701S. doi:10.1103 / PhysRevLett.90.098701. PMID  12689263.
  15. ^ Mihaljev, Tamara; Drossel, Barbara (Ekim 2006). "Kritik rasgele Boole ağlarının genel bir sınıfında ölçeklendirme". Fiziksel İnceleme E. 74 (4): 046101. arXiv:cond-mat / 0606612. Bibcode:2006PhRvE..74d6101M. doi:10.1103 / PhysRevE.74.046101. PMID  17155127. S2CID  17739744.
  16. ^ Kauffman, S.A. (1969). "Rastgele oluşturulmuş genetik ağlarda metabolik stabilite ve epigenez". Teorik Biyoloji Dergisi. 22 (3): 437–467. doi:10.1016/0022-5193(69)90015-0. PMID  5803332.
  17. ^ Derrida, B; Pomeau, Y (1986-01-15). "Rastgele Otomata Ağları: Basit Tavlı Bir Yaklaşım". Europhysics Letters (EPL). 1 (2): 45–49. Bibcode:1986EL ...... 1 ... 45D. doi:10.1209/0295-5075/1/2/001.
  18. ^ Solé, Ricard V .; Luque, Bartolo (1995-01-02). "Genelleştirilmiş Kauffman ağlarında faz geçişleri ve antichaos". Fizik Harfleri A. 196 (5–6): 331–334. Bibcode:1995PhLA..196..331S. doi:10.1016 / 0375-9601 (94) 00876-Q.
  19. ^ Luque, Bartolo; Solé, Ricard V. (1997-01-01). "Rasgele ağlarda faz geçişleri: Kritik noktaların basit analitik belirlenmesi". Fiziksel İnceleme E. 55 (1): 257–260. Bibcode:1997PhRvE..55..257L. doi:10.1103 / PhysRevE.55.257.
  20. ^ Fox, Jeffrey J .; Hill, Colin C. (2001-12-01). "Topolojiden biyokimyasal ağlarda dinamiğe". Kaos: Disiplinlerarası Doğrusal Olmayan Bilim Dergisi. 11 (4): 809–815. Bibcode:2001Chaos..11..809F. doi:10.1063/1.1414882. ISSN  1054-1500. PMID  12779520.
  21. ^ Aldana, Maximino; Cluzel, Philippe (2003-07-22). "Doğal bir sağlam ağ sınıfı". Ulusal Bilimler Akademisi Bildiriler Kitabı. 100 (15): 8710–8714. Bibcode:2003PNAS..100.8710A. doi:10.1073 / pnas.1536783100. ISSN  0027-8424. PMC  166377. PMID  12853565.
  22. ^ Pomerance, Andrew; Ott, Edward; Girvan, Michelle; Losert, Wolfgang (2009-05-19). "Ağ topolojisinin, genetik kontrolün ayrık durum modellerinin kararlılığı üzerindeki etkisi". Ulusal Bilimler Akademisi Bildiriler Kitabı. 106 (20): 8209–8214. arXiv:0901.4362. Bibcode:2009PNAS..106.8209P. doi:10.1073 / pnas.0900142106. ISSN  0027-8424. PMC  2688895. PMID  19416903.
  23. ^ Aldana, Maximino (Ekim 2003). "Ölçeksiz topolojiye sahip ağların Boole dinamikleri". Physica D: Doğrusal Olmayan Olaylar. 185 (1): 45–66. arXiv:cond-mat / 0209571. Bibcode:2003PhyD. 185 ... 45A. doi:10.1016 / s0167-2789 (03) 00174-x.
  24. ^ Drossel, Barbara; Greil, Florian (4 Ağustos 2009). "Ölçeksiz derece dağıtımlı kritik Boole ağları". Fiziksel İnceleme E. 80 (2): 026102. arXiv:0901.0387. Bibcode:2009PhRvE..80b6102D. doi:10.1103 / PhysRevE.80.026102. PMID  19792195. S2CID  2487442.
  25. ^ Harvey, Imman; Bossomaier, Terry (1997). Kocalar, Phil; Harvey, Imman (editörler). Eklem dışı zaman: Eşzamansız rastgele Boole ağlarında çekiciler. Dördüncü Avrupa Yapay Yaşam Konferansı Bildirileri (ECAL97). MIT Basın. sayfa 67–75. ISBN  9780262581578.
  26. ^ Gershenson Carlos (2002). Standish, Russell K; Bedau, Mark A (editörler). Rastgele Boolean Ağların Sınıflandırılması. Sekizinci Uluslararası Yapay Yaşam Konferansı Bildirileri. Yapay yaşam. 8. Cambridge, Massachusetts, ABD. s. 1–8. arXiv:cs / 0208001. Bibcode:2002cs ........ 8001G. ISBN  9780262692816. Alındı 12 Ocak 2016.
  27. ^ Gershenson, Carlos; Broekaert, Ocak; Aerts, Diederik (14 Eylül 2003). Bağlamsal Rastgele Boole Ağları [7. Avrupa Konferansı, ECAL 2003]. Yapay Yaşamdaki Gelişmeler. Bilgisayar Bilimlerinde Ders Notları. 2801. Dortmund, Almanya. sayfa 615–624. arXiv:nlin / 0303021. doi:10.1007/978-3-540-39432-7_66. ISBN  978-3-540-39432-7. S2CID  4309400.
  28. ^ Imani, M .; Braga-Neto, U.M. (2017/01/01). "Kısmen Gözlemlenen Boolean Dinamik Sistemler için Maksimum Olabilirlik Uyarlamalı Filtre". Sinyal İşlemede IEEE İşlemleri. 65 (2): 359–371. arXiv:1702.07269. Bibcode:2017 ITSP ... 65..359I. doi:10.1109 / TSP.2016.2614798. ISSN  1053-587X. S2CID  178376.
  29. ^ Imani, M .; Braga-Neto, U.M. (2015). "Bir Boole Kalman yumuşak kullanarak mantıksal dinamik sistemler için optimum durum tahmini". 2015 IEEE Küresel Sinyal ve Bilgi İşleme Konferansı (GlobalSIP). s. 972–976. doi:10.1109 / GlobalSIP.2015.7418342. ISBN  978-1-4799-7591-4. S2CID  8672734.
  30. ^ Imani, M .; Braga-Neto, U.M. (2016). 2016 Amerikan Kontrol Konferansı (ACC). s. 227–232. doi:10.1109 / ACC.2016.7524920. ISBN  978-1-4673-8682-1. S2CID  7210088.
  31. ^ Imani, M .; Braga-Neto, U. (2016-12-01). Sonlu gözlem uzayına sahip kısmen gözlemlenen Boole dinamik sistemleri için noktaya dayalı değer yinelemesi. 2016 IEEE 55. Karar ve Kontrol Konferansı (CDC). s. 4208–4213. doi:10.1109 / CDC.2016.7798908. ISBN  978-1-5090-1837-6. S2CID  11341805.
  32. ^ Hajiramezanali, E. & Imani, M. & Braga-Neto, U. & Qian, X. & Dougherty, E .. Düzenleyici Model Belirsizliği Altında Tek Hücreli Yörüngelerin Ölçeklendirilebilir Optimal Bayes Sınıflandırması. ACMBCB'18. https://dl.acm.org/citation.cfm?id=3233689

Dış bağlantılar