Narrow Results

We revisit the DOUBLE DIGEST problem, which occurs in sequencing of large DNA strings and consists of reconstructing the relative positions of cut sites from two different enzymes. We first show that DOUBLE DIGEST is strongly NP-complete, improving upon previous results that only showed weak NP-completeness. Even the (experimentally more meaningful) variation in which we disallow coincident cut sites turns out to be strongly NP-complete. In the second part, we model errors in data as they occur in real-life experiments: we propose several optimization variations of DOUBLE DIGEST that model partial cleavage errors. We then show that most of these variations are hard to approximate. In the third part, we investigate variations with the additional restriction that coincident cut sites are disallowed, and we show that it is NP-hard to even find feasible solutions in this case, thus making it impossible to guarantee any approximation ratio at all.

The problem of resolving genotypes into haplotypes, under the perfect phylogeny model, has been under intensive study recently. All studies so far handled missing data entries in a heuristic manner. We prove that the perfect phylogeny haplotype problem is NP-complete when some of the data entries are missing, even when the phylogeny is rooted. We define a biologically motivated probabilistic model for genotype generation and for the way missing data occur. Under this model, we provide an algorithm, which takes an expected polynomial time. In tests on simulated data, our algorithm quickly resolves the genotypes under high rates of missing entries.

Identifying regions of DNA with extreme statistical characteristics is an important aspect of the structural analysis of complete genomes. Linguistic methods, mainly based on estimating word frequency, can be used for this as they allow for the delineation of regions of low complexity. Low complexity may be due to biased nucleotide composition, by tandem- or dispersed repeats, by palindrome-hairpin structures, as well as by a combination of all these features. We developed software tools in which various numerical measures of text complexity are implemented, including combinatorial and linguistic ones. We also added Hurst exponent estimate to the software to measure dependencies in DNA sequences. By applying these tools to various functional genomic regions, we demonstrate that the complexity of introns and regulatory regions is lower than that of coding regions, whilst Hurst exponent is larger. Further analysis of promoter sequences revealed that the lower complexity of these regions is associated with long-range correlations caused by transcription factor binding sites.

All complex life on Earth is composed of ‘eukaryotic’ cells. Eukaryotes arose just once in 4 billion years, via an endosymbiosis — bacteria entered a simple host cell, evolving into mitochondria, the ‘powerhouses’ of complex cells. Mitochondria lost most of their genes, retaining only those needed for respiration, giving eukaryotes ‘multi-bacterial’ power without the costs of maintaining thousands of complete bacterial genomes. These energy savings supported a substantial expansion in nuclear genome size, and far more protein synthesis from each gene.

The efficiency of complex industrialized farming systems are compared to that of natural environmental systems while taking into account economic and environmental benefit as well as the needs of farmers and cattle.

Tierra is a digital simulation of evolution for which the stated goal was the development of open-ended complexity and a digital “Cambrian Explosion.” However, Tierra failed to produce such a result. A closer inspection “ Tierran evolution's adaptations show very few instances of adaptation through the production of new information. Instead, most changes result from removing or rearranging the existing pieces within a Tierra program. The open-ended development of complexity depends on the ability to generate new information, but this is precisely what Tierra struggles to do. The character of Tierran adaptation does not allow for open-ended complexity but is similar to the character of adaptations found in the biological world.