Sequencing-by-hybridization at the information-theory bound: an optimal algorithm.

In a recent paper (Preparata et aL, 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well-defined periodic pattern. It has been shown (Preparata et al, 1999) that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given size library of probes) is significantly better than the standard scheme based on oligomer probes. In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance that comes within a small constant factor (about 2) of the information-theory bound. Moreover, this performance is achieved while maintaining running time linear in the target sequence length.

Optimal reconstruction of a sequence from its probes.

An important combinatorial problem, motivated by DNA sequencing in molecular biology, is the reconstruction of a sequence over a small finite alphabet from the collection of its probes (the sequence spectrum), obtained by sliding a fixed sampling pattern over the sequence. Such construction is required for Sequencing-by-Hybridization (SBH), a novel DNA sequencing technique based on an array (SBH chip) of short nucleotide sequences (probes). Once the sequence spectrum is biochemically obtained, a combinatorial method is used to reconstruct the DNA sequence from its spectrum. Since technology limits the number of probes on the SBH chip, a challenging combinatorial question is the design of a smallest set of probes that can sequence an arbitrary DNA string of a given length. We present in this work a novel probe design, crucially based on the use of universal bases [bases that bind to any nucleotide (Loakes and Brown, 1994)] that drastically improves the performance of the SBH process and asymptotically approaches the information-theoretic bound up to a constant factor. Furthermore, the sequencing algorithm we propose is substantially simpler than the Eulerian path method used in previous solutions of this problem.

Ciliate evolution: the ribosomal phylogenies of the tetrahymenine ciliates.

We have assembled and analyzed nucleotide sequences for several different rRNA components from tetrahymenine ciliates. These include previously published and some new 5S and 5.8S rRNAs for a total of 18 species. We also report sequences for some 30 species obtained by primer extension analysis of a region near the 5' end of the 23S rRNAs (region 580). Phylogenetic trees have been constructed for these species, utilizing heuristics (shifting ditypic site analysis) described in a companion paper. The trees based on these sequences are consistent with each other and with those based on longer sequences of the 17S rRNA. They show the tetrahymenines to consist of a number of distinctive clusters of species. The clusters (ribosets) are homogeneous with respect to certain life history characteristics, especially the mode of mating type determination, but are inhomogeneous with respect to some morphological and life history features, such as cyst formation and adaptations to parasitism or carnivory. Using the same molecular data, we also begin to explore the relationships of the tetrahymenines to some other ciliate taxa and to some other protists.

Shifting ditypic site analysis: heuristics for expanding the phylogenetic range of nucleotide sequences in Sankoff analyses.

We describe and illustrate a simple heuristic approach to the Sankoff methods for construction of parsimonious evolutionary trees from nucleotide sequence data. The procedure is intended to permit more valid inferences, particularly from relatively short sequences, concerning relationships among taxa separated for long time intervals. The procedure is based on the great variability of evolutionary plasticity among sites in the molecules and removes from consideration the more highly variable sites. Editing is accomplished after classifying sites in carefully aligned arrays of sequences. Only "ditypic sites," i.e., sites observed in only two evolutionary states within the array, are used in making phylogenetic inferences. This strategy makes possible the construction of good approximations to the most parsimonious Steiner trees, by means of efficient programs that require "dense species arrays," i.e., species sets that differ from each other by relatively small numbers of differences in conservative sites. The technique is illustrated with 5S and 5.8S rRNA sequence data from published catalogs.