Position Weight Matrices (PWMs) are probabilistic representations of signals in sequences. They are widely used to model approximate patterns in DNA or in protein sequences. The usage of PWMs needs as a prerequisite to knowing the statistical significance of a word according to its score. This is done by defining the P-value of a score, which is the probability that the background model can achieve a score larger than or equal to the observed value. This gives rise to the following problem: Given a P-value, find the corresponding score threshold. Existing methods rely on dynamic programming or probability generating functions. For many examples of PWMs, they fail to give accurate results in a reasonable amount of time. The contribution of this paper is two fold. First, we study the theoretical complexity of the problem, and we prove that it is NP-hard. Then, we describe a novel algorithm that solves the P-value problem efficiently. The main idea is to use a series of discretized score distributions that improves the final result step by step until some convergence criterion is met. Moreover, the algorithm is capable of calculating the exact P-value without any error, even for matrices with non-integer coefficient values. The same approach is also used to devise an accurate algorithm for the reverse problem: finding the P-value for a given score. Both methods are implemented in a software called TFM-PVALUE, that is freely available. We have tested TFM-PVALUE on a large set of PWMs representing transcription factor binding sites. Experimental results show that it achieves better performance in terms of computational time and precision than existing tools.

Single-celled apicomplexan parasites are known to cause major diseases in humans and animals including malaria, toxoplasmosis, and coccidiosis. The presence of apicoplasts with the remnant of a plastid-like DNA argues that these parasites evolved from photosynthetic ancestors possibly related to the dinoflagellates. Toxoplasma gondii displays amylopectin-like polymers within the cytoplasm of the dormant brain cysts. Here we report a detailed structural and comparative analysis of the Toxoplasma gondii, green alga Chlamydomonas reinhardtii, and dinoflagellate Crypthecodinium cohnii storage polysaccharides. We show Toxoplasma gondii amylopectin to be similar to the semicrystalline floridean starch accumulated by red algae. Unlike green plants or algae, the nuclear DNA sequences as well as biochemical and phylogenetic analysis argue that the Toxoplasma gondii amylopectin pathway has evolved from a totally different UDP-glucose-based metabolism similar to that of the floridean starch accumulating red alga Cyanidioschyzon merolae and, to a lesser extent, to those of glycogen storing animals or fungi. In both red algae and apicomplexan parasites, isoamylase and glucan–water dikinase sequences are proposed to explain the appearance of semicrystalline starch-like polymers. Our results have built a case for the separate evolution of semicrystalline storage polysaccharides upon acquisition of photosynthesis in eukaryotes.

Mitochondrial genomes (mitogenomes) in higher plants can induce cytoplasmic male sterility and be somehow involved in nuclear-cytoplasmic interactions affecting plant growth and agronomic performance. They are larger and more complex than in other eukaryotes, due to their recombinogenic nature. For most plants, the mitochondrial DNA (mtDNA) can be represented as a single circular chromosome, the so-called master molecule, which includes repeated sequences that recombine frequently, generating sub-genomic molecules in various proportions. Based on the relevance of the potato crop worldwide, herewith we report the complete mtDNA sequence of two S. tuberosum cultivars, namely Cicero and Désirée, and a comprehensive study of its expression, based on high-coverage RNA sequencing data. We found that the potato mitogenome has a multi-partite architecture, divided in at least three independent molecules that according to our data should behave as autonomous chromosomes. Inter-cultivar variability was null, while comparative analyses with other species of the Solanaceae family allowed the investigation of the evolutionary history of their mitogenomes. The RNA-seq data revealed peculiarities in transcriptional and post-transcriptional processing of mRNAs. These included co-transcription of genes with open reading frames that are probably expressed, methylation of an rRNA at a position that should impact translation efficiency and extensive RNA editing, with a high proportion of partial editing implying frequent mis-targeting by the editing machinery.

Despite their monophyletic origin, mitochondrial (mt) genomes of plants and animals have developed contrasted evolutionary paths over time. Animal mt genomes are generally small, compact, and exhibit high mutation rates, whereas plant mt genomes exhibit low mutation rates, little compactness, larger sizes, and highly rearranged structures. We present the (nearly) whole sequences of five new mt genomes in the Beta genus: four from Beta vulgaris and one from B. macrocarpa, a sister species belonging to the same Beta section. We pooled our results with two previously sequenced genomes of B. vulgaris and studied genome diversity at the species level with an emphasis on cytoplasmic male-sterilizing (CMS) genomes. We showed that, contrary to what was previously assumed, all three CMS genomes belong to a single sterile lineage. In addition, the CMSs seem to have undergone an acceleration of the rates of substitution and rearrangement. This study suggests that male sterility emergence might have been favored by faster rates of evolution, unless CMS itself caused faster evolution.

Background: Despite their monophyletic origin, animal and plant mitochondrial genomes have been described as exhibiting different modes of evolution. Indeed, plant mitochondrial genomes feature a larger size, a lower mutation rate and more rearrangements than their animal counterparts. Gene order variation in animal mitochondrial genomes is often described as being due to translocation and inversion events, but tandem duplication followed by loss has also been proposed as an alternative process. In plant mitochondrial genomes, at the species level, gene shuffling and duplicate occurrence are such that no clear phylogeny has ever been identified, when considering genome structure variation. Results: In this study we analyzed the whole sequences of eight mitochondrial genomes from maize and teosintes in order to comprehend the events that led to their structural features, i.e. the order of genes, tRNAs, rRNAs, ORFs, pseudogenes and non-coding sequences shared by all mitogenomes and duplicate occurrences. We suggest a tandem duplication model similar to the one described in animals, except that some duplicates can remain. This model enabled us to develop a manual method to deal with duplicates, a recurrent problem in rearrangement analyses. The phylogenetic tree exclusively based on rearrangement and duplication events is congruent with the tree based on sequence polymorphism, validating our evolution model. Conclusions: This study suggests more similarity than usually reported between plant and animal mitochondrial genomes in their mode of evolution. Further work will consist of developing new tools in order to automatically look for signatures of tandem duplication events in other plant mitogenomes and evaluate the occurrence of this process on a larger scale.

MOTIVATION: Evolution acts in several ways on DNA: either by mutating a base, or by inserting, deleting or copying a segment of the sequence (Ruddle, 1997; Russell, 1994; Li and Grauer, 1991). Classical alignment methods deal with point mutations (Waterman, 1995), genome-level mutations are studied using genome rearrangement distances (Bafna and Pevzner, 1993, 1995; Kececioglu and Sankoff, 1994; Kececioglu and Ravi, 1995). The latter distances generally operate, not on the sequences, but on an ordered list of genes. To our knowledge, no measure of distance attempts to compare sequences using a general set of segment-based operations. RESULTS: Here we define a new family of distances, called transformation distances, which quantify the dissimilarity between two sequences in terms of segment-based events. We focus on the case where segment-copy, -reverse-copy and -insertion are allowed in our set of operations. Those events are weighted by their description length, but other sets of weights are possible when biological information is available. The transformation distance from sequence S to sequence T is then the Minimum Description Length among all possible scripts that build T knowing S with segment-based operations. The underlying idea is related to Kolmogorov complexity theory. We present an algorithm which, given two sequences S and T, computes exactly and efficiently the transformation distance from S to T. Unlike alignment methods, the method we propose does not necessarily respect the order of the residues within the compared sequences and is therefore able to account for duplications and translocations that cannot be properly described by sequence alignment. A biological application on Tnt1 tobacco retrotransposon is presented. AVAILABILITY: The algorithm and the graphical interface can be downloaded at http://www.lifl.fr/ approximately varre/TD