Dynamical properties of model gene networks and implications for the inverse problem.

We study the inverse problem, or the "reverse-engineering" problem, for two abstract models of gene expression dynamics, discrete-time Boolean networks and continuous-time switching networks. Formally, the inverse problem is similar for both types of networks. For each gene, its regulators and its Boolean dynamics function must be identified. However, differences in the dynamical properties of these two types of networks affect the amount of data that is necessary for solving the inverse problem. We derive estimates for the average amounts of time series data required to solve the inverse problem for randomly generated Boolean and continuous-time switching networks. We also derive a lower bound on the amount of data needed that holds for both types of networks. We find that the amount of data required is logarithmic in the number of genes for Boolean networks, matching the general lower bound and previous theory, but are superlinear in the number of genes for continuous-time switching networks. We also find that the amount of data needed scales as 2(K), where K is the number of regulators per gene, rather than 2(2K), as previous theory suggests.

Inferring models of gene expression dynamics.

We study the problem of identifying genetic networks in which expression dynamics are modeled by a differential equation that uses logical rules to specify time derivatives. We make three main contributions. First, we describe computationally efficient procedures for identifying the structure and dynamics of such networks from expression time series. Second, we derive predictions for the expected amount of data needed to identify randomly generated networks. Third, if expression values are available for only some of the genes, we show that the structure of the network for these "visible" genes can be identified and that the size and overall complexity of the network can be estimated. We validate these procedures and predictions using simulation experiments based on randomly generated networks with up to 30,000 genes and 17 distinct regulators per gene and on a network that models floral morphogenesis in Arabidopsis thaliana.

Ancestral maximum likelihood of evolutionary trees is hard.

Maximum likelihood (ML) (Neyman, 1971) is an increasingly popular optimality criterion for selecting evolutionary trees. Finding optimal ML trees appears to be a very hard computational task--in particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years, no such hardness result has been obtained so far for ML. In this work we make a first step in this direction by proving that ancestral maximum likelihood (AML) is NP-complete. The input to this problem is a set of aligned sequences of equal length and the goal is to find a tree and an assignment of ancestral sequences for all of that tree's internal vertices such that the likelihood of generating both the ancestral and contemporary sequences is maximized. Our NP-hardness proof follows that for MP given in (Day, Johnson and Sankoff, 1986) in that we use the same reduction from Vertex Cover; however, the proof of correctness for this reduction relative to AML is different and substantially more involved.

Towards quality control for DNA microarrays.

We present a framework for detecting probes in oligonucleotide microarrays that may add significant error to measurements in hybridization experiments. Four types of so-called degenerate probe behavior are considered: secondary structure formation, self-dimerization, cross-hybridization, and dimerization. The framework uses a well-established model for computing the free energy of nucleic acid sequence hybridization and a novel method for the detection of patterns in hybridization experiment data. Our primary result is the identification of unique patterns in hybridization experiment data that are shown to correlate with each type of degenerate probe behavior. A support function for identifying degenerate probes from a large set of hybridization experiments is given and some preliminary experimental results are given for the Affymetrix HuGeneFL GeneChip. Finally, we show a strong relationship between the Affymetrix discrimination measure for a probe and the free-energy estimate from theoretical models of hybridization. In particular, probes on the HuGeneFL GeneChip with high free-energy estimates (weak hybridization) have almost always approximately zero discrimination. The framework can be applied to any Affymetrix oligonucleotide array, and the software is made freely available to the community.