Search

Microbial genomes and RNA sequences comprise an important part of biological big data. CVTree is a whole-genome based and alignment-free method whereas LVTree is based on alignment of 16S rRNA sequences. They provide two independent ways to construct phylogenetic trees and to extract taxonomic information for prokaryotes. The automation of these two approaches make the study of prokaryotic phylogeny and classification by-product of big data analysis and come as a rescue to the declining discipline of taxonomy. Especially, the whole-genome based CVTree not only provides a tool for large-scale study but also possesses high resolution power at the species level and below, a distinctive feature beyond the reach of 16S rRNA sequence analysis. These methods taken together may open new directions in microbiological research. This paper is a brief review of our recent work.

An interactive tool to visualize the K-string composition of long DNA sequences including bacterial complete genomes is described. It is especially useful for exploring short palindromic structures in the sequences. The SeeDNA program runs on Red Hat Linux with GTK+ support. It displays two-dimensional (2D) or one-dimensional (1D) histograms of the K-string distribution of a given sequence and/or its randomized counterpart. It is also capable of showing the difference of K-string distributions between two sequences. The C source code using the GTK+ package is freely available.

A faithful phylogeny and an objective taxonomy for prokaryotes should agree with each other and ultimately follow the genome data. With the number of sequenced genomes reaching tens of thousands, both tree inference and detailed comparison with taxonomy are great challenges. We now provide one solution in the latest Release 3.0 of the alignment-free and whole-genome-based web server CVTree3. The server resides in a cluster of 64 cores and is equipped with an interactive, collapsible, and expandable tree display. It is capable of comparing the tree branching order with prokaryotic classification at all taxonomic ranks from domains down to species and strains. CVTree3 allows for inquiry by taxon names and trial on lineage modifications. In addition, it reports a summary of monophyletic and non-monophyletic taxa at all ranks as well as produces print-quality subtree figures. After giving an overview of retrospective verification of the CVTree approach, the power of the new server is described for the mega-classification of prokaryotes and determination of taxonomic placement of some newly-sequenced genomes. A few discrepancies between CVTree and 16S rRNA analyses are also summarized with regard to possible taxonomic revisions. CVTree3 is freely accessible to all users at http://tlife.fudan.edu.cn/cvtree3/ without login requirements.

A tripartite comparison of Archaea phylogeny and taxonomy at and above the rank order is reported: (1) the whole-genome-based and alignment-free CVTree using 179 genomes; (2) the 16S rRNA analysis exemplified by the All-Species Living Tree with 366 archaeal sequences; and (3) the Second Edition of Bergey’s Manual of Systematic Bacteriology complemented by some current literature. A high degree of agreement is reached at these ranks. From the newly proposed archaeal phyla, Korarchaeota, Thaumarchaeota, Nanoarchaeota and Aigarchaeota, to the recent suggestion to divide the class Halobacteria into three orders, all gain substantial support from CVTree. In addition, the CVTree helped to determine the taxonomic position of some newly sequenced genomes without proper lineage information. A few discrepancies between the CVTree and the 16S rRNA approaches call for further investigation.

Using an enlarged alphabet of K-tuples is the way to carry out alignment-free comparison of genomes in the composition vector (CV) approach to prokaryotic phylogeny. We summarize the known aspects concerning the choice of K and examine the results of using CVs with subtraction of a statistical background for K=3–9 and using raw CVs without subtraction for K=1–12. The criterion for evaluation consists in direct comparison with taxonomy. For prokaryotes the best performances are obtained for K=5 and 6 with subtraction and for K=11, 12 or even more without subtraction. In general, CVs with subtractions are slightly better and less CPU consuming, but CVs without subtraction may provide complementary information.

Shigella species and Escherichia coli are closely related organisms. Early phenotyping experiments and several recent molecular studies put Shigella within the species E. coli. However, the whole-genome-based, alignment-free and parameter-free CVTree approach shows convincingly that four established Shigella species, Shigella boydii, Shigella sonnei, Shigella felxneri and Shigella dysenteriae, are distinct from E. coli strains, and form sister species to E. coli within the genus Escherichia. In view of the overall success and high resolution power of the CVTree approach, this result should be taken seriously. We hope that the present report may promote further in-depth study of the Shigella-E. coli relationship.

The number of sequenced genomes of Archaea, Bacteria, and Fungi accumulates rapidly. Several thousands genomes of these unicellular organisms will be available in a few years. Due to the extremely large difference in genome size and gene content it is difficult to use the traditional alignment-based method to infer phylogeny from the genomes. An alignment-free and whole-genome-based approach called CVTree has been developed and successfully applied to these organisms. As CVTree has been successfully applied to genomes of viruses, chloroplasts, Bacteria, Archaea and fungi, in this brief review we will mainly touch on some mathematical problems related to the foundation of the new approach, including a few yet unsolved problems, such as the violation of the triangular inequalities of the dissimilarity measure used in the CVTree method.

Composition vector trees (CVTrees) are inferred from whole-genome data by an alignment-free and parameter-free method. The agreement of these trees with the corresponding taxonomy provides an objective justification of the inferred phylogeny. In this work, we show the stability and self-consistency of CVTrees by performing bootstrap and jackknife re-sampling tests adapted to this alignment-free approach. Our ultimate goal is to advocate the viewpoint that time-consuming statistical re-sampling tests can be avoided at all in using this alignment-free approach. Agreement with taxonomy should be taken as a major criterion to estimate prokaryotic phylogenetic trees.

Composition vector approach to prokaryotic phylogeny provides an alignment-free and parameter-free method based on whole-genome data. It has also been applied to viruses and fungi. In all studied cases the inferred phylogenetic relationships agree well with taxonomic knowledge in major groupings and fine branchings. In this review article, after demonstrating its successful application to a collection of 892 genomes including 62 Archaea, 822 Bacteria and 8 Eukarya, we will outline some ongoing work towards the foundations of this new approach.

We perform an exhaustive, taxon by taxon, comparison of the branchings in the composition vector trees (CVTrees) inferred from 432 prokaryotic genomes available on 31 December 2006, with the bacteriologists' taxonomy--primarily the latest online Outline of the Bergey's Manual of Systematic Bacteriology. The CVTree phylogeny agrees very well with the Bergey's taxonomy in majority of fine branchings and overall structures. At the same time most of the differences between the trees and the Manual have been known to biologists to some extent and may hint at taxonomic revisions. Instead of demonstrating the overwhelming agreement this paper puts emphasis on the biological implications of the differences.

A formal language is called factorizable if any substring of a word in it also belongs to the language. Symbolic sequences from symbolic dynamics make factorizable languages by definition. In studying avoided and under-represented strings in bacterial genomes we have defined a factorizable language for each complete genome. Recently, in studying the problem of uniqueness of reconstruction of a protein sequence from its constituent K -peptides we encounter again factorizable language which helps to build a finite state automaton to recognize the uniqueness of reconstruction. We present a brief review of these applications of factorizable languages from dynamics to biology.

The statistical properties of the size distribution of DNA segments separating identical oligonucleotides are studied. For representative eukaryotes (Homo sapiens, Mus musculus, Saccharomyces cereviciae, Oryza sativa, Arabidopsis thaliana) we have demonstrated the existence of long-range correlations for the distances separating oligonucleotides of sizes 4, 5 and 6, which carry a promoter signature. This observation is independent of the consensus sequence used by the organism, as in the case of O. sativa (which mainly uses the CG promoter box) and A. thaliana (which mainly uses the TATA promoter box). If we use two parameters to characterise the size distribution separating oligonucleotides, we observe that oligonucleotides containing promoter signatures cluster together, away from the others. (c) 2005 Elsevier B.V. All rights reserved.

Udgivelsesdato: 2006-Apr-27 After the completion of a draft human genome sequence, the International Human Genome Sequencing Consortium has proceeded to finish and annotate each of the 24 chromosomes comprising the human genome. Here we describe the sequencing and analysis of human chromosome 3, one of the largest human chromosomes. Chromosome 3 comprises just four contigs, one of which currently represents the longest unbroken stretch of finished DNA sequence known so far. The chromosome is remarkable in having the lowest rate of segmental duplication in the genome. It also includes a chemokine receptor gene cluster as well as numerous loci involved in multiple human cancers such as the gene encoding FHIT, which contains the most common constitutive fragile site in the genome, FRA3B. Using genomic sequence from chimpanzee and rhesus macaque, we were able to characterize the breakpoints defining a large pericentric inversion that occurred some time after the split of Homininae from Ponginae, and propose an evolutionary history of the inversion.

This is a brief review on critical slowing down near the Feigenbaum period-doubling bifurcation points and its consequences. The slowing down of numerical convergence leads to an "operational" fractal dimension D=2/3 at a finite order bifurcation point. There is a cross-over to D-0=0.538... when the order goes to infinity, i.e., to the Feigenbaum accumulation point. The problem of whether there exists a "super-scaling" for the dimension spectrum D-q(W) that does not depend on the primitive word W underlying the period-n-tupling sequence seems to remain open.

With several rice genome projects approaching completion gene prediction/finding by computer algorithms has become an urgent task. Two test sets were constructed by mapping the newly published 28,469 full-length KOME rice cDNA to the RGP BAC clone sequences of Oryza sativa ssp. japonica: a single-gene set of 550 sequences and a multi-gene set of 62 sequences with 271 genes. These data sets were used to evaluate five ab initio gene prediction programs: RiceHMM, GlimmerR, GeneMark, FGENSH and BGF. The predictions were compared on nucleotide, exon and whole gene structure levels using commonly accepted measures and several new measures. The test results show a progress in performance in chronological order. At the same time complementarity of the programs hints on the possibility of further improvement and on the feasibility of reaching better performance by combining several gene-finders.

Phylogenetic tree of coronaviruses (CoVs) including the human SARS-associated virus is reconstructed from complete genomes by using our newly developed K-string composition approach. The relation of the human SARS-CoV to other coronaviruses, i.e. the rooting of the tree is suggested by choosing an appropriate outgroup. SARS-CoV makes a separate group closer but still distant from G2 (CoVs in mammalian host). The relation between different isolates of the human SARS virus is inferred by first constructing an ultrametric distance matrix from counting sequence variations in the genomes. The resulting tree is consistent with clinic relations between the SARS-CoV isolates. In addition to a larger variety of coronavirus genomes these results provide phylogenetic knowledge based on independent novel methodology as compared to recent phylogenetic studies on SARS-CoV.

We present a brief review of a series of on-going work on bacterial phylogeny. We propose a new method to infer relatedness of prokaryotes from their complete genome data without using sequence alignment, leading to results comparable with the bacteriologist's systematics as reflected in the latest 2001 edition of Bergey's Manual of Systematic Bacteriology.1 We only touch on the mathematical aspects of the method. The biological implications of our results will be published elsewhere.

We have produced a draft sequence of the rice genome for the most widely cultivated subspecies in China, Oryza sativa L. ssp. indica , by whole-genome shotgun sequencing. The genome was 466 megabases in size, with an estimated 46,022 to 55,615 genes. Functional coverage in the assembled sequences was 92.0%. About 42.2% of the genome was in exact 20-nucleotide oligomer repeats, and most of the transposons were in the intergenic regions between genes. Although 80.6% of predicted Arabidopsis thaliana genes had a homolog in rice, only 49.4% of predicted rice genes had a homolog in A. thaliana . The large proportion of rice genes with no recognizable homologs is due to a gradient in the GC content of rice coding sequences.

The sequence of the rice genome holds fundamental information for its biology, including physiology, genetics, development, and evolution, as well as information on many beneficial phenotypes of economic significance. Using a "whole genome shotgun" approach, we have produced a draft rice genome sequence of Oryza sativa ssp. indica, the major crop rice subspecies in China and many other regions of Asia. The draft genome sequence is constructed from over 4.3 million successful sequencing traces with an accumulative total length of 2214.9 Mb. The initial assembly of the non-redundant sequences reached 409.76 Mb in length, based on 3.30 million successful sequencing traces with a total length of 1797.4 Mb from an indica variant cultivar 93-11, giving an estimated coverage of 95.29% of the rice genome with an average base accuracy of higher than 99%. The coverage of the draft sequence, the randomness of the sequence distribution, and the consistency of BIG-ASSEMBLER, a custom-designed software package used for the initial assembly, were verified rigorously by comparisons against finished BAC clone sequences from both indica and japanica strains, available from the public databases. Over all, 96.3% of full-length cDNAs, 96.4% of STS, STR, RFLP markers, 94.0% of ESTs and 94.9% unigene clusters were identified from the draft sequence. Our preliminary analysis on the data set shows that our rice draft sequence is consistent with the comman standard accepted by the genome sequencing community. The unconditional release of the draft to the public also undoubtedly provides a fundamental resource to the international scientific communities to facilitate genomic and genetic studies on rice biology.

Symbolic sequences generated by symbolic dynamics of a dynamical system belong to a special class of language in which any admissible word is factorisable as well as prolongable. From a complete genome sequence of an organism, one may also define a factorizable language. A factorizable language enjoys the nice property that it is entirely determined by the set of minimal fobidden words or distinct excluded blocks (DEBs). We use this property to calculate the fractal dimension of patterns related to a visualisation scheme of under-represented strings in bacterial complete genomes within the limit of infinitely long strings. The same problem may be solved by using a purely combinatorial approach. The methods described in this paper may be applied to other regular fractals with self-similar and self-overlapping structure. (C) 2000 Elsevier Science B.V. All rights reserved.

The visualization of avoided and under-represented strings in some bacterial complete genomes raises a combinatorial problem which may be solved either by using the Goulden-Jackson cluster method or by construction of the minimal finite automaton defined by the set of forbidden words of the corresponding language.

A visualization scheme of avoided and under-represented strings in complete genomes reveals some nice patterns which become precise fractals in the non-biological limit of infinitely long strings. There arises the problem of calculating the dimensions of these fractals with self-similar and self-overlapping structures. Direct counting of avoided strings in a complete genome raises the problem of distinguishing true and redundant avoided strings of a given length knowing the number of shorter ones. The two problems turn out to be one and are solved exactly by using two different methods: combinatorics and language theory.

Recent progress of symbolic dynamics of one- and especially two-dimensional maps has enabled us to construct symbolic dynamics for systems of ordinary differential equations (ODEs). Numerical study under the guidance of symbolic dynamics is capable to yield global results on chaotic and periodic regimes in systems of dissipative ODEs which cannot be obtained neither by purely analytical means nor by numerical work alone. By constructing symbolic dynamics of 1D and 2D maps from the Poincare sections all unstable periodic orbits up to a given length at a fixed parameter set may be located and all stable periodic orbits up to a given length may be found in a wide parameter range. This knowledge, in turn, tells much about the nature of the chaotic limits. Applied to the Lorenz equations, this approach has led to a nomenclature, i.e., absolute periods and symbolic names, of stable and unstable periodic orbits for an autonomous system. Symmetry breakings and restorations as well as coexistence of different regimes are also analyzed by using symbolic dynamics., Comment: 35 pages, LaTeX, 13 Postscript figures, uses psfig.tex. The revision concerns a bug at the end of hlzfig12.ps which prevented the printing of the whole .ps file from page 24