Search

The spanning tree packing number of a graph G, denoted by STP(G), is the maximum number of edge-disjoint spanning trees contained in G. Let denotes the set of all spanning trees of G. We say that a spanning tree T of G is of type ( ) if the maximum number of edge-disjoint spanning trees contained in (subgraph obtained by deleting all edges of T) is , in other words . The set of all ’s types of spanning trees gives a partition of . We introduce st-robustness of a graph as a new connectivity measure that evaluates the connectivity of a graph in case of deleting some of its spanning trees. st-robustness of a graph G, denoted by STR(G), is defined as the expected value of , when T ranges over all spanning trees of G. In this paper we study this parameter and evaluate it in the case of complete graphs. [ABSTRACT FROM AUTHOR]

The emergence of phenotypic diversity in a population of cells and their arrangement in space and time is one of the most fascinating features of living systems. In fact, understanding multicellularity is unthinkable without explaining the proximate and the ultimate causes of cell differentiation in time and space. Simpler forms of cell differentiation can be found in unicellular organisms, such as bacterial biofilm, where reversible cell differentiation results in phenotypically diverse populations. In this manuscript, we attempt to start with the simple case of reversible nongenetic phenotypic to construct a model of differentiation and pattern formation. Our model, which we refer to as noise-driven differentiation (NDD) model, is an attempt to consider the prevalence of noise in biological systems, alongside what is known about genetic switches and signaling, to create a simple model which generates spatiotemporal patterns from bottom-up. Our simulations indicate that the presence of noise in cells can lead to reversible differentiation and the addition of signaling can create spatiotemporal pattern., Competing Interests: The authors have declared that no competing interests exist.

Based on previous studies, empirical distribution of the bacterial burst size varies even in a population of isogenic bacteria. Since bacteriophage progenies increase linearly with time, it is the lysis time variation that results in the bacterial burst size variations. Here, the burst size variation is computationally modeled by considering the lysis time decisions as a game. Each player in the game is a bacteriophage that has initially infected and lysed its host bacterium. Also, the payoff of each burst size strategy is the average number of bacteria that are solely infected by the bacteriophage progenies after lysis. For calculating the payoffs, a new version of ball and bin model with time dependent occupation probabilities (TDOP) is proposed. We show that Nash equilibrium occurs for a range of mixed burst size strategies that are chosen and played by bacteriophages, stochastically. Moreover, it is concluded that the burst size variations arise from choosing mixed lysis strategies by each player. By choosing the lysis time and also the burst size stochastically, the released bacteriophage progenies infect a portion of host bacteria in environment and avoid extinction. The probability distribution of the mixed burst size strategies is also identified.

Background: Understanding the mechanisms by which hundreds of diverse cell types develop from a single mammalian zygote has been a central challenge of developmental biology. Conrad H. Waddington, in his metaphoric "epigenetic landscape" visualized the early embryogenesis as a hierarchy of lineage bifurcations. In each bifurcation, a single progenitor cell type produces two different cell lineages. The tristable dynamical systems are used to model the lineage bifurcations. It is also shown that a genetic circuit consisting of two auto-activating transcription factors (TFs) with cross inhibitions can form a tristable dynamical system., Results: We used gene expression profiles of pre-implantation mouse embryos at the single cell resolution to visualize the Waddington landscape of the early embryogenesis. For each lineage bifurcation we identified two clusters of TFs - rather than two single TFs as previously proposed - that had opposite expression patterns between the pair of bifurcated cell types. The regulatory circuitry among each pair of TF clusters resembled a genetic circuit of a pair of single TFs; it consisted of positive feedbacks among the TFs of the same cluster, and negative interactions among the members of the opposite clusters. Our analyses indicated that the tristable dynamical system of the two-cluster regulatory circuitry is more robust than the genetic circuit of two single TFs., Conclusions: We propose that a modular hierarchy of regulatory circuits, each consisting of two mutually inhibiting and auto-activating TF clusters, can form hierarchical lineage bifurcations with improved safeguarding of critical early embryogenesis against biological perturbations. Furthermore, our computationally fast framework for modeling and visualizing the epigenetic landscape can be used to obtain insights from experimental data of development at the single cell resolution.

One of the fundamental problems in bioinformatics is phylogenetic tree reconstruction, which can be used for classifying living organisms into different taxonomic clades. The classical approach to this problem is based on a marker such as 16S ribosomal RNA. Since evolutionary events like genomic rearrangements are not included in reconstructions of phylogenetic trees based on single genes, much effort has been made to find other characteristics for phylogenetic reconstruction in recent years. With the increasing availability of completely sequenced genomes, gene order can be considered as a new solution for this problem. In the present work, we applied maximal common intervals (MCIs) in two or more genomes to infer their distance and to reconstruct their evolutionary relationship. Additionally, measures based on uncommon segments (UCS's), i.e., those genomic segments which are not detected as part of any of the MCIs, are also used for phylogenetic tree reconstruction. We applied these two types of measures for reconstructing the phylogenetic tree of 63 prokaryotes with known COG (clusters of orthologous groups) families. Similarity between the MCI-based (resp. UCS-based) reconstructed phylogenetic trees and the phylogenetic tree obtained from NCBI taxonomy browser is as high as 93.1% (resp. 94.9%). We show that in the case of this diverse dataset of prokaryotes, tree reconstruction based on MCI and UCS outperforms most of the currently available methods based on gene orders, including breakpoint distance and DCJ. We additionally tested our new measures on a dataset of 13 closely-related bacteria from the genus Prochlorococcus. In this case, distances like rearrangement distance, breakpoint distance and DCJ proved to be useful, while our new measures are still appropriate for phylogenetic reconstruction., (Copyright © 2014 Elsevier Ireland Ltd. All rights reserved.)

The problem of constructing an optimal rooted phylogenetic network from an arbitrary set of rooted triplets is an NP-hard problem. In this paper, we present a heuristic algorithm called TripNet, which tries to construct a rooted phylogenetic network with the minimum number of reticulation nodes from an arbitrary set of rooted triplets. Despite of current methods that work for dense set of rooted triplets, a key innovation is the applicability of TripNet to non-dense set of rooted triplets. We prove some theorems to clarify the performance of the algorithm. To demonstrate the efficiency of TripNet, we compared TripNet with SIMPLISTIC. It is the only available software which has the ability to return some rooted phylogenetic network consistent with a given dense set of rooted triplets. But the results show that for complex networks with high levels, the SIMPLISTIC running time increased abruptly. However in all cases TripNet outputs an appropriate rooted phylogenetic network in an acceptable time. Also we tetsed TripNet on the Yeast data. The results show that Both TripNet and optimal networks have the same clustering and TripNet produced a level-3 network which contains only one more reticulation node than the optimal network.

Decision making at a cellular level determines different fates for isogenic cells. However, it is not yet clear how rational decisions are encoded in the genome, how they are transmitted to their offspring, and whether they evolve and become optimized throughout generations. In this paper, we use a game theoretic approach to explain how rational decisions are made in the presence of cooperators and competitors. Our results suggest the existence of an internal switch that operates as a biased coin. The biased coin is, in fact, a biochemical bistable network of interacting genes that can flip to one of its stable states in response to different environmental stimuli. We present a framework to describe how the positions of attractors in such a gene regulatory network correspond to the behavior of a rational player in a competing environment. We evaluate our model by considering lysis/lysogeny decision making of bacteriophage lambda in E. coli.