74 research outputs found
Analytical calculations on content-based networks
No full textBu makalede içerik-temelli ağlar üzerinde, ağın topolojik özelliklerini belirlemek için, ortalama-alan yaklaşımlarıyla yapılan analitik hesapların güvenilirliği tartışılacaktır. İçerik-temelli ağları, “tanıma ve bağlanma” mekanizmalarının belirleyici olduğu kontrol çizgelerinin topolojik özelliklerini tasvir etmek için önermiştik. Birçok karmaşık ağ yapısının bu tür enformasyon paylaşımına dayalı bir prensibe göre inşa edildiğini söyleyebiliriz. Örneğin gen ifadesinin düzenlemesinde, anahtar/kilit olarak niteleyebileceğimiz elemanların özelleşmiş etkileşimleri söz konusudur. Bu sebeple modelimizin biyolojik çizgeler de dahil olmak üzere, birçok gerçek ağ yapısının tasviri için uygun olduğunu düşünüyoruz. İçerik-temelli ağımızda, ağın düğümlerini bir ya da birden fazla rastgele dizi ile eşleştirip, düğümler arasındaki etkileşimleri onlara atanan dizilerin birbirleri içinde tekrarlanma koşulu altında inşa ediyoruz. Böylece, bu dizilerin uzunlukları ve içerikleri, ortaya çıkacak olan çizgenin tüm topolojik özelliklerini belirlemektedir. Düğüm çiftleri arasındaki bağlanma olasılıklarının hesabında yapılan ortalama-alan yaklaşımlarının ise, dizilerin uzunluk dağılımlarına bağlı olarak, varılan sonuçlarda ağın gerçek özelliklerinden önemli farklılaşmalara yol açabileceği görülüyor. Bu yaklaşımlarda, dizilerin farklı enformasyon içerikleri ihmal edilmekte ve olasılıklar sadece dizilerin uzunlukları cinsinden elde edilmektedir. Halbuki her sonlu dizi için, dizinin içerdiği farklı sembol sayısı ek bir enformasyon içermektedir. Burada sergilemeye çalışacağımız, kabalaştırılmış ortalama-alan türünden yaklaşımların, belli ekstrem durumlarda, tasvir etmeyi amaçladıkları ağın özelliklerinden uzak sonuçlar verebileceğidir. Ancak gerçek biyolojik ağ yapılarının modellenmesinde karşımıza çıkan uzunluk dağılımlarında ortaya çıkan hatalar hiçbir zaman burada sergileyeceğimiz örneklerde olduğu kadar büyük olmamış, bilakis ortalama-alan yaklaşımı simülasyon sonuçlarına oldukça yakın sonuçlar vermiştir. Anahtar Kelimeler: Karmaşık ağ yapıları, içerik-temelli ağlar, ortalama-alan yaklaşımı.Content-based networks have been proposed (Balcan and Erzan, 2004; Mungan et al., 2005) to model the topological properties of complex networks built on the principle of information sharing, where the interactions between system components assume the simultaneous fulfillment of a series of constraints (Mezard et al., 2002). In content-based networks, the constraint-satisfaction problem is realized by means of a sequence-matching rule between sequences associated with the nodes of a network. In the case of transcriptional gene regulation, the transcription factors recognize special subsequences of DNA and bind them. This is one instance of constraint-satisfaction, which can be realized with a sequence-matching rule between two different classes of sequences (Balcan et al., 2006). Another example is the so called the RNA interference (Balcan and Erzan, 2004), where sequence-specific gene silencing occurs at the level of post-transcriptional gene regulation. In our content-based networks, n linear codes are associated with each node of the network. For n=2, one of the sequences associated with the node represents the key-sequence through which the node recognizes other nodes, whereas the second sequence represents the lock-sequence through which the same node is recognized. An interaction between a pair of nodes is established if the key-sequence associated with the first node is repeated as an uninterrupted subsequence in the lock-sequence associated with the second node. Thus, the length distributions of these sequences are the most important parameters determining the topological properties of the content-based networks. In this article we will discuss the validity of analytical calculations performed on the topological properties of content-based networks in the mean-field approximation (Balcan and Erzan, 2007), by means of two examples. In this mean field approach (Mungan et al., 2005) the pair-wise connectivity probabilities are only functions of the respective lengths of the sequences which must satisfy an inclusion requirement, and of the size r of the alphabet from which the symbols are drawn. This approximation ignores the correlations between the overlapping subsequences within a sequence. Moreover the fluctuations in the information content of finite sequences are neglected. In Balcan and Erzan (2007), the correlations between the edges co-incident on the same node were also ignored. In the first example, the key- sequences of unit length (thus, they consist of single letters) are searched in lock-sequences of an arbitrary fixed length. Via this simple example it is possible to show that the probability that lock-sequences will be recognized by a key-sequence depends not only on the length of the lock-sequence but also on the number of distinct subsequences embedded in it. At this point the coarse grained approximation neglecting the fluctuations in the information content of the finite lock sequences about their mean information content, misses the behavior of the in-degree distribution. This error is in fact identical to neglecting the correlations between edges incident upon a given node. In the second example, the lengths of the key sequences are fixed at an arbitrary value l, and the lock-sequences are chosen to be of length k=l+1, one character longer than the key-sequences. In this example, it is clear that the correlations between the two subsequences of length l cannot be neglected. It has already been shown (Guibas and Odlyzko, 1981; Mungan et al., 2005; Mungan, 2007; Bilge et al., 2004) that the connection probability of a key-sequence depends on the ?shift-match number? which measures the auto-correlations within a sequence, in other words, the degree to which successive subsequences are correlated with each other. We show here by an explicit and rather transparent calculation that, neglecting this correlation yields out- and in-degree distributions that are totally in error. The mean-field approximations used in the calculation of the topological properties of the double-string model (Balcan and Erzan, 2007) yield results that are in good agreement with the simulations, since i) the lengths k of the lock sequences far exceed r, ii) the number of distinct substrings contained in any given lock string is large ( k-l >> rl ) and iii) the fine structure of the topological properties are determined by the fact that there is a disribution of lock- and key-string lengths. Keywords: Complex networks, content-based networks, mean-field approach
Ukrainian "malancars" — the Eastern part of Carpathian-Balcan carnival tradition
No full textAuthor proves the fruitfulness of comparative Carpathian-Balcan Studies on the problem of reconstruction of Slavic and other Southeastern people's cultural heritage. From this very point of view the Ukrainian new-year custom "Malanka" is analyzed, as well as and its invariant structure and archaic scenario.Автор обстоює перспективність порівняльних карпато-балканських студій у розв'язанні проблем реконструкції духовної культури слов'ян та інших народів Південно-Східної Європи. Під цим кутом зору розглядається український новорічний обряд "Маланка ", аналізується його інваріантна структура й архаїчний сценарій
Efficient semi-supervised and active learning of disjunctions
No full textWe provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting. Copyright 2013 by the author(s).link_to_subscribed_fulltex
Information content based model for the topological properties of the gene regulatory network of Escherichia coli
No full textGene regulatory networks (GRN) are being studied with increasingly precise quantitative tools and can provide a testing ground for ideas regarding the emergence and evolution of complex biological networks. We analyze the global statistical properties of the transcriptional regulatory network of the prokaryote Escherichia coli, identifying each operon with a node of the network. We propose a null model for this network using the content-based approach applied earlier to the eukaryote Saccharomyces cerevisiae (Balcan et al., 2007). Random sequences that represent promoter regions and binding sequences are associated with the nodes. The length distributions of these sequences are extracted from the relevant databases. The network is constructed by testing for the occurrence of binding sequences within the promoter regions. The ensemble of emergent networks yields an exponentially decaying in-degree distribution and a putative power law dependence for the out-degree distribution with a flat tail, in agreement with the data. The clustering coefficient, degree-degree correlation, rich club coefficient and k-core visualization all agree qualitatively with the empirical network to an extent not yet achieved by any other computational model, to our knowledge. The significant statistical differences can point the way to further research into non-adaptive and adaptive processes in the evolution of the E. coli GRN. (C) 2009 Elsevier Ltd. All rights reserved
Network Of Gene Expressıon
No full textTez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2003Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2003Biyolojik sistemlerde protein üretimi, yani gen ifadesi, birebir olmamakta ve genlerin birbirleriyle olan etkileşimleri sonucu ortaya çıkmaktadır. Bu etkileşimler için, seçilim baskısı olmaksızın mutasyon geçiren basit bir modelde, Monte Carlo simülasyonlarıyla, gen etkileşimlerinin ölçekten bağımsız bir şebeke oluşturduğu ve bir gen tarafından baskılanan gen sayısı ( O z ) dağılımının ( ) O O z τ − ( O τ =0.47±0.01) gibi bir kuvvet yasasına tabi olduğu ve bu şebekenin bir küçük dünya modeline uygun olarak kümelenme katsayısının C ≈ 0.5 olduğu bulundu. Gen etkileşimi şebekesinin bir kinetik Ising modeli biçiminde betimlenmesi durumunda, sistemin tepkimelerinin zaman içinde ölçekten bağımsız bir sönümlenme zamanı dağılımına sahip olabileceği görüldü. Bu kendiliğinden kritik sistemin dinamik davranışını inceleyebilmek için, dinamik renormalizasyon grubu dönüşümleri rastgele Γ - komşuluklu spin sistemlerine genelleştirildi.We have studied the regulatory network of gene expression during protein synthesis in biological systems. We have intoduced a simple random bit-string model to represent a chromosome sequence and have only considered the inhibition interactions between the genes. As the result of our Monte Carlo simulations, we have found that this simple model gives rise to a network of gene expression which is of the small-world type, with a clustering coefficient C ≈ 0.5, and is scale-invariant with the distribution of out-going connectivities obeying n(zout) ∼ (zout)-τ . The exponent τ is found to be τ=0.47±0.01. This result shows that the system is complex and can respond on any scale to the sitimuli coming from the environment. This also shows that the system has a selforganized critical behavior. In order to test ideas regarding the distribution of relaxation times on such a network, we have generalized the dynamical renormalization-group calculations to networks with an arbitrary number of nearest neighbors. This will enable us to compute the dynamical exponent on networks with random connections.Yüksek LisansM.Sc
Properties Of Content-based Networks
No full textTez (Doktora) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2007Thesis (PhD) -- İstanbul Technical University, Institute of Science and Technology, 2007Burada sunulan tez calışmasının ana teması transkripsiyon gen regülasyonu (düzenleme) çizgelerinin oluşumuna katkıda bulunan unsurların ve bu çizgelerin yapısal (topolojik) özelliklerinin enformasyon teorisi yaklaşımı ile modellenmesidir. Transkripsiyonel gen kontrolünde, transkripsiyon faktörleri olarak isimlendirilen proteinler DNA üzerinde özel alt dizilere bağlanarak, gen ifadesinin düzenlenmesine katkıda bulunmaktadırlar. Böyle bir proteinin tanıyıp bağlanabildiği DNA motiflerinin bilgi içeriğini başka bir alfabede ifade etmek mümkün olabilir. Bu yaklaşımla mayanın transkripsiyonel gen düzenleme ağını, içerik temelli ağın herbir düğümü bir gene karşılık gelmek üzere, herbir düğümüne gelişi güzel ikilik sistemde içerikleri olan diziler atayarak ve düğümler arasına, onlara atanan dizilerin birbirleri içerisinde tekrarlanma durumlarına göre, belli koşulları sağlamaları sonunda kenarlar yerleştirerek modelledik. Paylaşılan bilgi miktarının dağılımı modelimizin en önemli girdisi olup, ortaya çıkacak olan çizgenin özelliklerini tamamen belirlemektedir. Mayanının etkileşim ağını ayrıntılı biçimde inceleyerek, çizgenin yapısal özelliklerini içerik temelli modelimizin istatistiksel topluluğunun üyeleriyle karşılaştırdık. Gördük ki, içerik temelli modelimiz maya çizgesinin bütün özelliklerini barındırmakta ve bu tür ağların yapısal özelliklerinin anlaşılmasına imkan sağlamaktadır. Tamamen gelişi güzel dizilerden oluşturduğumuz içerik temelli çizgenin mayanın kontrol ağına yakınlığı, bu tür karmaşık ağ yapılarının evrim altında ereksel biçimde yoktan var edilmeleri gerekmedikleri sonucuna varmamıza neden olmaktadır. İçerik temelli modelimizin kabalaştırılması sonunda elde ettiğimiz ve (sadece dizi uzunluklarına bağlı) gizli-değişkenli olarak isimlendirilen modelin bizim içerik temelli modelimizi ve gerçek maya çizgesini yakından izleyen yapısal özellikleri nedeniyle, bu kaba model üzerinde yapılacak analitik hesapların düzenleme ağlarının yapılarıyla ilgili öngörülerde bulunabileceğini göstermektedir. İcerik temelli çizgelerin gen kontrol ağlarına yakınlıkları, gelişi güzel Boolean dinamiğini içerik temelli ağlara uyarlamamızı özendirmiştir. Bu yolla gen ifadesinin kontrol çizgelerinin topolojilerinin gen ifadesi dinamiği üzerindeki etkilerini anlamak mükün olabilir. Sonuçlarımız içerik temelli ağların bağışıklık sistemi yada protein etkileşimleri gibi çok sayıda koşulun yerine gelmesi sayesinde oluşan etkileşim ağlarının modellenmesi için elverişli olanaklar sunduğunu göstermektedir.The research we present in this thesis has been devoted to the modelling and understanding of transcriptional gene regulatory networks, on the basis of an information theoretical approach. Transcriptional gene regulation involve special proteins, namely the transcription factors, which bind to the DNA by recognizing specific subsequences, namely the transcription factor binding sites, embedded in them. We have modelled the transcriptional regulation network of yeast within this approach by associating random linear codes with the genes of the organism represented by nodes in our content-based network, and establishing edges between the nodes if and only if they share a certain amount of information, which has been realized via a sequence-matching rule. The distribution of the amount of shared information, which has been represented by the bitwise Shannon information of the random linear codes associated with the binding sequences and the promoter regions, are the most important biological inputs to our content-based model. We have made a very careful analysis of the transcriptional regulation networks of yeast, and compared their topological features with those of the ensemble of our content-based networks. We have observed that our content-based model is able to reproduce all the global topological features of these networks, which provides us with an understanding of their emergent nature. We conclude that the complex networks of gene regulation can arise spontaneously even with the random codes, so they do not need to be constructed from scratch by evolutionary mechanisms. We have also introduced the hidden-variable version of our content-based model involving only the pairwise connection probabilities as a function of the string lengths and observed that this model is able capture the main properties of our double-string model. So the analytical calculation on the hidden-variable model can provide us with making some predictions on the further properties of real networks. Very close topological similarities between the content-based models and genetic regulatory networks have led us to consider a modified random Boolean dynamics on our content-based networks, which we believe will help us with the understanding of the relationship between the architecture of the underlying network and the function of these systems. Our results point to further promising research problems in biological systems, where interactions between different components require the fulfillment of a series of constraints, which means the exchange of a certain amount of information. Examples are immune systems and protein interactions.DoktoraPh
Comparing large-scale computational approaches to epidemic modeling: Agent-based versus structured metapopulation models
No full textAbstract Background In recent years large-scale computational models for the realistic simulation of epidemic outbreaks have been used with increased frequency. Methodologies adapt to the scale of interest and range from very detailed agent-based models to spatially-structured metapopulation models. One major issue thus concerns to what extent the geotemporal spreading pattern found by different modeling approaches may differ and depend on the different approximations and assumptions used. Methods We provide for the first time a side-by-side comparison of the results obtained with a stochastic agent-based model and a structured metapopulation stochastic model for the progression of a baseline pandemic event in Italy, a large and geographically heterogeneous European country. The agent-based model is based on the explicit representation of the Italian population through highly detailed data on the socio-demographic structure. The metapopulation simulations use the GLobal Epidemic and Mobility (GLEaM) model, based on high-resolution census data worldwide, and integrating airline travel flow data with short-range human mobility patterns at the global scale. The model also considers age structure data for Italy. GLEaM and the agent-based models are synchronized in their initial conditions by using the same disease parameterization, and by defining the same importation of infected cases from international travels. Results The results obtained show that both models provide epidemic patterns that are in very good agreement at the granularity levels accessible by both approaches, with differences in peak timing on the order of a few days. The relative difference of the epidemic size depends on the basic reproductive ratio, R0, and on the fact that the metapopulation model consistently yields a larger incidence than the agent-based model, as expected due to the differences in the structure in the intra-population contact pattern of the approaches. The age breakdown analysis shows that similar attack rates are obtained for the younger age classes. Conclusions The good agreement between the two modeling approaches is very important for defining the tradeoff between data availability and the information provided by the models. The results we present define the possibility of hybrid models combining the agent-based and the metapopulation approaches according to the available data and computational resources.</p
- …
