Abstract: ABSTRACT: Bacterial strains that were genetically blocked in important metabolic pathways and grown under selectiveconditions underwent a process of adaptive evolution: certain pathways may have been deregulated andtherefore allowed for the circumvention of the given block. A block of endogenous pyruvate synthesis fromglycerol was realized by a knockout of pyruvate kinase and phosphoenolpyruvate carboxylase in E. coli. Theresulting mutant strain was able to grow on a medium containing glycerol and lactate, which served as anexogenous pyruvate source. Heterologous expression of a pyruvate carboxylase gene from Corynebacteriumglutamicum was used for anaplerosis of the TCA cycle. Selective conditions were controlled in a continuousculture with limited lactate feed and an excess of glycerol feed. After 200-300 generationspyruvate-prototrophic mutants were isolated. The genomic analysis of an evolved strain revealed that thegenotypic basis for the regained pyruvate-prototrophy was not obvious. A constraint-based model of themetabolism was employed to compute all possible detours around the given metabolic block by solving ahierarchy of linear programming problems. The regulatory network was expected to be responsible for theadaptation process. Hence, a Boolean model of the transcription factor network was connected to themetabolic model. Our model analysis only showed a marginal impact of transcriptional control on the biomassyield on substrate which is a key variable in the selection process. In our experiment, microarray analysisconfirmed that transcriptional control probably played a minor role in the deregulation of the alternativepathways for the circumvention of the block.
Abstract: An analytical model based on the statistical properties of Open Reading Frames (ORFs) of eubacterial genomes such as codon composition and sequence length of all reading frames was developed. This new model predicts the average length, maximum length as well as the length distribution of the ORFs of 70 species with GC contents varying between 21% and 74%. Furthermore, the number of annotated genes is predicted with high accordance. However, the ORF length distribution in the five alternative reading frames shows interesting deviations from the predicted distribution. In particular, long ORFs appear more often than expected statistically. The unexpected depletion of stop codons in these alternative open reading frames cannot completely be explained by a biased codon usage in the +1 frame. While it is unknown if the stop codon depletion has a biological function, it could be due to a protein coding capacity of alternative ORFs exerting a selection pressure which prevents the fixation of stop codon mutations. The comparison of the analytical model with bacterial genomes, therefore, leads to a hypothesis suggesting novel gene candidates which can now be investigated in subsequent wet lab experiments.
Abstract: Boolean models of regulatory networks are assumed to be tolerant to perturbations. That qualitatively implies that each function can only depend on a few nodes. Biologically motivated constraints further show that functions found in Boolean regulatory networks belong to certain classes of functions, for example, the unate functions. It turns out that these classes have specific properties in the Fourier domain. That motivates us to study the problem of detecting controlling nodes in classes of Boolean networks using spectral techniques. We consider networks with unbalanced functions and functions of an average sensitivity less than 23k, where k is the number of controlling variables for a function. Further, we consider the class of 1-low networks which include unate networks, linear threshold networks, and networks with nested canalyzing functions. We show that the application of spectral learning algorithms leads to both better time and sample complexity for the detection of controlling nodes compared with algorithms based on exhaustive search. For a particular algorithm, we state analytical upper bounds on the number of samples needed to find the controlling nodes of the Boolean functions. Further, improved algorithms for detecting controlling nodes in large-scale unate networks are given and numerically studied.
Abstract: This paper addresses space time convolutional code design using continuous phase modulation (CPM). The possibility of constructing full diversity space time codes is investigated. A linear modulation approximation to CPM is done. Using the Gram-Schmidt orthogonalization transform the CPM signal is generated as a vector with finite energy in a different Euclidean space. A serially concatenated CPM construction is considered in searching channel codes which are able to exploit maximum diversity. Design criteria based on the encoding scheme are derived for an arbitrary number of transmit antennas. The investigations are done for a quasi-static Rayleigh fading channel.
Abstract: Algebraic decoding algorithms are commonly applied for the decoding of Reed-Solomon codes. Their main advantages are low computational complexity and predictable decoding capabilities. Many algorithms can be extended for correction of both errors and erasures. This enables the decoder to exploit binary quantized reliability information obtained from the transmission channel: Received symbols with high reliability are forwarded to the decoding algorithm while symbols with low reliability are erased. In this paper we investigate adaptive single-trial error/erasure decoding of Reed-Solomon codes, i.e. we derive an adaptive erasing strategy which minimizes the residual codeword error probability after decoding. Our result is applicable to any error/erasure decoding algorithm as long as its decoding capabilities can be expressed by a decoder capability function. Examples are Bounded Minimum Distance decoding with the Berlekamp-Massey- or the Sugiyama algorithms and the Guruswami-Sudan list decoder.
Abstract: The inference of genetic regulatory networks in the Boolean network model is considered. Given a set of measurements, a reasonably good approximation of the Boolean functions attached to each of the n nodes has to be found. Besides the fact that measurements are inherently noisy, another problem to deal with, is the huge amount of irrelevant data, as it is reasonable to assume that each node is only controlled by an unknown subset of all possible nodes. An algorithm is proposed based on previous work of Mossel et al. It proceeds by estimating the Fourier spectra of the unknown Boolean functions. Although it requires slightly more samples than exhaustive search, it provides a significant speed up. It is shown that the running time can be further decreased for functions with low average sensitivity and the so-called nested canalyzing functions which were claimed to be an important class of functions for genetic regulatory networks.
Abstract: Ensembles of Boolean networks using linear random threshold functions with memory are considered. Such ensembles have been studied previously by Szejka et al.. They obtained analytical results for the order parameter which can be used to predict the expected behavior of a network randomly drawn from the ensemble. Using numerical simulations of randomly drawn networks, Szejka et al. found marked deviations from the predicted behavior. In this work improved analytical results are provided that better match up the numerical results. Furthermore, the critical point in their analysis is identified. In the model studied, each node is not only dependent on the K regular inputs, but also on the previous state of the node. The results show that this feedback loop accounts for the low order parameter and tolerance on random errors, even for networks with high in-degree.
Abstract: The problem of estimating the Fourier spectra of Boolean functions using noisy non-uniformly drawn random examples is considered. In particular, arbitrary product distributions on the n-dimensional attribute vectors are assumed. The attributes are disturbed by noise also following a product distribution. Under these conditions the problem of estimating the Fourier spectra is considered. A general expression is derived that allows the construction of estimators of the Fourier spectra. This results can be applied to learn functions that are concentrated on the lower part of their spectra. As an application of the presented results an algorithm is shown that infers the relevant variables of so-called 1-low Boolean juntas.
Abstract: The Transmission Control Protocol (TCP) was designed to provide reliable transport services in wired networks. In such networks, packet losses mainly occur due to congestion. Hence, TCP was designed to apply congestion avoidance techniques to cope with packet losses. Nowadays, TCP is also utilized in wireless networks where, besides congestion, numerous other reasons for packet losses exist. This results in reduced throughput and increased transmission round-trip time when the state of the wireless channel is bad. We propose a new network layer, that transparently sits below the transport layer and hides non congestion-imposed packet losses from TCP. The network coding in this new layer is based on the well-known class of Maximum Distance Separable (MDS) codes.
Abstract: We investigate adaptive single-trial error/erasure decoding of binary codes whose decoder is able to correct õ errors and àerasures if ûõ + âÂ⬠\textless; dmin -1. Thereby, dmin is the minimum Hamming distance and û õ R, 1 \textless; û \textless; 2, is the tradeoff parameter between errors and erasures. The error/erasure decoder allows to exploit soft information by treating a set of most unreliable received symbols as erasures. The obvious question here is, how this erasing should be performed, i.e. how the unreliable symbols that must be erased in order to obtain the smallest possible residual codeword error probability can be determined. This was answered before for the case of fixed erasing, where only the channel state and not the individual symbol reliabilities of each received vector are taken into consideration. In this paper, we address the adaptive case, where the optimal erasing strategy is determined for every given received vector.
Abstract: The problem of learning an affine Boolean function from noisy examples is considered. This problem is equivalent to the decoding of a binary message encoded with a random linear code and can be also viewed as the problem to decode a message encoded with a randomly punctured Reed-Muller code of first order. The error exponent of the error probability of a learning machine based on spectral learning techniques is shown to be lower bounded by the random coding error exponent.
Abstract: Random Boolean networks are considered. It is shown that when using a certain class of distributions on the set of Boolean functions to construct the network, the expectation of the average sensitivity is equal to the order parameter proposed by James Lynch. This turns out to be a special case of a result about the expectation of the l-sensitivity of random Boolean functions.
Abstract: We consider Boolean functions with noisy inputs. I.e., each binary input is sent over a binary symmetric channel with crossover probability isin before fed into the function. By proving an upper bound for the average l-sensitivity, we show that Boolean functions with average sensitivity less or equal 1 will not amplify the noise at their input. This means, that on average the probability that the output of the function is different from the output of the same function without noise, is less or equal e.
Abstract: Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network? To identify these nodes, a notion that quantifies the determinative power of an input over states in the network is needed. We argue that the mutual information (MI) between a subset of the inputs X = X_1, ..., X_n of node i and the function f_i(X)$ associated with node i quantifies the determinative power of this subset of inputs over node i. To study the relation of determinative power to sensitivity to perturbations, we relate the MI to measures of perturbations, such as the influence of a variable, in terms of inequalities. The result shows that, maybe surprisingly, an input that has large influence does not necessarily have large determinative power. The main tool for the analysis is Fourier analysis of Boolean functions. Whether a function is sensitive to perturbations or not, and which are the determinative inputs, depends on which coefficients the Fourier spectrum is concentrated on. We also consider unate functions which play an important role in genetic regulatory networks. For those, a particular relation between the influence and MI is found. As an application of our methods, we analyze the large-scale regulatory network of E. coli numerically: We identify the most determinative nodes and show that a small set of those reduces the overall uncertainty of network states significantly. The network is also found to be tolerant to perturbations of its inputs, which can be seen from the Fourier spectrum of its functions.
