A comparison of the 16S ribosomal RNAs from mesophilic and thermophilic bacilli: Some modifications in the sanger method for RNA sequencing

Summary Two modifications in the Sanger two dimensional electrophoretic procedure for RNA analysis are reported. One increases resolution on the primary fingerprint to the point that digests of large RNAs, of the size 1500–3000 nucleotides yield well resolved fingerprint patterns. The other is a novel endonucleolytic procedure that proves useful in determining sequences of the large oligonucleotides produced by T1 ribonuclease.These modifications have been used in determining the catalogs of oligomers produced by T1 ribonuclease digestion of 16S rRNAs from three related organisms,Bacillus subtilis, B.pumilus andB.stearothermophilus. The possible effects of adaptation to a thermophilic niche on ribosomal RNA primary structure and the phylogenetic relatedness of the two mesophilic Bacilli are discussed.This is contribution No.6 in a series on procaryote phylogeny.     

A fast exact sequential algorithm for the partial digest problem

Background

Restriction site analysis involves determining the locations of restriction sites after the process of digestion by reconstructing their positions based on the lengths of the cut DNA. Using different reaction times with a single enzyme to cut DNA is a technique known as a partial digestion. Determining the exact locations of restriction sites following a partial digestion is challenging due to the computational time required even with the best known practical algorithm.

Results

In this paper, we introduce an efficient algorithm to find the exact solution for the partial digest problem. The algorithm is able to find all possible solutions for the input and works by traversing the solution tree with a breadth-first search in two stages and deleting all repeated subproblems. Two types of simulated data, random and Zhang, are used to measure the efficiency of the algorithm. We also apply the algorithm to real data for the Luciferase gene and the E. coli K12 genome.

Conclusion

Our algorithm is a fast tool to find the exact solution for the partial digest problem. The percentage of improvement is more than 75% over the best known practical algorithm for the worst case. For large numbers of inputs, our algorithm is able to solve the problem in a suitable time, while the best known practical algorithm is unable.

     

Discontinuously synthesized mRNA from Trypanosoma brucei contains the highly methylated 5' cap structure, m7GpppA*A*C(2'-O)mU*A

Trypanosoma brucei mRNA is discontinuously synthesized via the 5' addition of a "mini-exon" sequence. The mini-exon-specific cap structure was purified from a complete RNase T2 and phosphatase digest of in vivo 32P-labeled poly(A)+RNA. The purified cap structure was sequenced by a series of partial and complete enzymatic digests by nuclease P1 and venom phosphodiesterase. This approach demonstrated that the T. brucei mini-exon cap structure consists of N7-methylguanosine linked in a conventional 5'-5' triphosphate bond to five nucleotides, in the sequence A*A*C(2'-O)mU*A (asterisks denote modifications that were not fully characterized in this work). 2'-O-methylations and other modifications appear to be present in this novel cap structure, which could have a functional role in the metabolism of the mini-exon.     

The impact of two-dimensional pulsed-field gel electrophoresis techniques for the consistent and complete mapping of bacterial genomes: refined physical map of Pseudomonas aeruginosa PAO.

The SpeI/DpnI map of the 5.9 Mb Pseudomonas aeruginosa PAO (DSM 1707) genome was refined by two-dimensional (2D) pulsed-field gel electrophoresis techniques (PFGE) which allow the complete and consistent physical mapping of any bacterial genome of interest. Single restriction digests were repetitively separated by PFGE employing different pulse times and ramps in order to detect all bands with optimum resolution. Fragment order was evaluated from the pattern of 2D PFGE gels: 1. Partial-complete digestion. A partial restriction digest was separated in the first dimension, redigested to completion, and subsequently perpendicularly resolved in the second dimension. 2D-gel comparisons of the ethidium bromide stain of all fragments and of the autoradiogram of end-labeled partial digestion fragments was nearly sufficient for the construction of the macrorestriction map. 2. Reciprocal gels. A complete restriction digest with enzyme A was run in the first dimension, redigested with enzyme B, and separated in the second orthogonal direction. The order of restriction digests was reverse on the second gel. In case of two rare-cutters, fragments were visualized by ethidium bromide staining or hybridization with genomic DNA. If a frequent and a rare cutter were employed, linking fragments were identified by end-labeling of the first digest. 3. A few small fragments were isolated by preparative PFGE and used as a probe for Southern analysis.--38 SpeI and 15 DpnI fragments were positioned on the map. The zero point was relocated to the 'origin of replication'. The anonymous mapping techniques described herein are unbiased by repetitive DNA, unclonable genomic regions, unfavourable location of restriction sites, or cloning artifacts as frequently encountered in other top-down or bottom-up approaches.     

Evaluation of polymer sequence fragment data using graph theory

Much of recent work to determine primary structures of nucleic acids and proteins employs the “fragmentation” or “overlap” stratagem. Typically, a preparation of a given polymer with unknown sequence is purified and then subjected to an enzyme known to cut the polymer at certain specific sites. The quantities and sequences of the resulting fragments are determined. For RNA primary sequences, pancreatic ribonuclease and T1 ribonuclease are ordinarily used as fragmenting enzymes. A technique is described for evaluating such fragment data. It has the following properties: It is easily determined whether or not the fragment data is inconsistent. It is always possible to determine the first and last nucleotides of the unknown sequence from the data of two limit digests. Consistent data from two limit digests can always be fitted into a convenient conceptual framework developed within the theory of graphs. In most cases, partial digest information can be used to modify the framework constructed from two limit digests, as such information is obtained. An efficient analysis of all fragment data in this conceptual framework can always be made. One can detect inconsistencies and can generate the entire list of polymer sequences consistent with the fragment data.     

An ab Initio Algorithm for Low-Resolution 3-D Reconstructions from Cryoelectron Microscopy Images

A statistical method for determining low-resolution 3-D reconstructions of virus particles from cryoelectron microscope images by an ab initio algorithm is described. The method begins with a novel linear reconstruction method that generates a spherically symmetric reconstruction, which is followed by a nonlinear reconstruction method implementing an expectation-maximization procedure using the spherically symmetric reconstruction as an initial condition and resulting in a reconstruction with icosahedral symmetry. An important characteristic of the complete method is that very little need be known about the particle before the reconstruction is computed, in particular, only the type of symmetry and inner and outer radii. The method is demonstrated on synthetic cowpea mosaic virus data, and its robustness to 5% errors in the contrast transfer function, 5% errors in the location of the center of the particles in the images, and 5% distortion in the 3-D structure from which the images are derived is demonstrated numerically.     

Direct determination of DNA nucleotide sequences: structure of a fragment of bacteriophage phiX172 DNA

Methods for the direct determination of nucleotide sequences in DNA have been developed and used to determine the complete primary structure of a fragment of bacteriophage φX174 DNA which is 48 residues in length. This fragment was liberated from φX DNA by digestion at low temperature and high ionic strength with the T4 phage-induced endonuclease IV. The fragment was redigested with endonuclease IV under vigorous conditions and the products fractionated two-dimensionally providing a characteristic endonuclease IV “fingerprint” of the fragment. The Burton (Burton &; Petersen, 1960) depurination reaction was used to characterize the redigestion products and identify the pyrimidine residues at their 5′ and 3′ termini. These oligonucleotide products were then fully sequenced by partial exonuclease digestion with spleen and snake venom phosphodiesterase and analysis of the fractionated digests by base composition, depurination, and 5′ end-group analysis using exonuclease I. Rules for the interpretation of two-dimensional fingerprints of partial exonuclease digests, which rapidly provide sequence information by simple inspection, were also deduced. To derive the complete structure of the fragment, the fully sequenced oligonucleotides were ordered by characterizing large, overlapping, partial endonuclease IV digestion products by means of the depurination reaction. The sequencing methods described are general and may be used for the direct determination of the primary structures of other fragments of DNA.     

Assignment of the Disulfide Bridges in Bothropstoxin-I, a Myonecrotic Lys49 PLA2 Homolog from Bothrops jararacussu Snake Venom

Bothropstoxin-I (BthTX-I), a Lys49 phospholipase A₂ homolog with no apparent catalytic activity, was first isolated from Bothrops jararacussu snake venom and completely sequenced in this laboratory. It is a 121-amino-acid single polypeptide chain, highly myonecrotic, despite its inability to catalyze hydrolysis of egg yolk phospholipids, and has 14 half-cystine residues identified at positions 27, 29, 44, 45, 50, 51, 61, 84, 91, 96, 98, 105, 123, and 131 (numbering according to the conventional alignment including gaps, so that the last residue is Cys 131). In order to access its seven disulfide bridges, two strategies were followed: (1) Sequencing of isolated peptides from (tryptic + SV₈) and chymotryptic digests by Edman-dansyl degradation; (2) crystallization of the protein and determination of the crystal structure so that at least two additional disulfide bridges could be identified in the final electron density map. Identification of the disulfide-containing peptides from the enzymatic digests was achieved following the disappearance of the original peptides from the HPLC profile after reduction and carboxymethylation of the digest. Following this procedure, four bridges were initially identified from the tryptic and SV₈ digests: Cys50-Cys131, Cys51-Cys98, Cys61-Cys91, and Cys84-Cys96. From the chymotryptic digest other peptides were isolated either containing some of the above bridges, therefore confirming the results from the tryptic digest, or presenting a new bond between Cys27 and Cys123. The two remaining bridges were identified as Cys29-Cys45 and Cys44-Cys105 by determination of the crystal structure, showing that BthTX-I disulfide bonds follow the normal pattern of group II PLA₂s.     

Panulirus interruptus hemocyanin. The elucidation of the complete amino acid sequence of subunit a

As a final step in the elucidation of the primary structure of subunit a of Panulirus interruptus hemocyanin (657 residues, Mr 75696 excluding two copper ions and carbohydrate), the amino acid sequence of the largest fragment obtained by limited trypsinolysis was determined. The elucidation of the sequence of residues 176-657, comprising domains two and three, was mainly based on two digests, with CNBr and trypsin, respectively, from both of which a complete set of peptides was obtained. Additional sequence information was obtained from a digest with Staphylococcus aureus V8 protease and from one fragment obtained by cleaving subunit a with hydroxylamine. A block during Edman degradations indicated an Asn-Gly sequence at positions 597-598, although only aspartic acid was identified at position 597.     

The complete primary structure of late lactation protein from quokka (Setonix brachyurus)

The complete primary structure of the late lactation protein from the milk of quokka (Setonix brachyurus) is presented. The amino acid sequence was established by N-terminal sequence analysis of high-performance liquid chromatography purified intact protein and peptides isolated from chemical and enzymatic digests of the protein. The protein contains 158 residues including four cysteines. The sequence comparison with the tamar wallaby (Macropus eugenii) late lactation protein shows only five differences. The protein is identified as a new member of a novel late lactation protein family present in the milk of marsupials.     

Restriction endonuclease mapping of R27 (TP117), an incompatibility group HI subgroup 1 plasmid from Salmonella typhimurium

A circular map of the IncHI plasmid R27 corresponding to a genome size of 182 kb was established using the restriction endonucleases ApaI, XbaI, and PstI. The map was derived from the results obtained by hybridizing individual ApaI and XbaI fragments to blotted digests of the plasmid, as well as from complete and partial digests. Analysis of a deletion mutant derived by in vitro digestion with PstI and of transfer-defective and tetracycline-sensitive deletion mutants of R27 derived by Tn5 insertion were instrumental in determining the positions of some fragments.     

The amino acid sequence of rabbit J chain in secretory immunoglobulin A.

The primary structure of rabbit J chain, which occurs covalently bound to secretory IgA, was determined. J chain was isolated in its S-carboxymethylated form, in one step, by SDS/PAGE followed by electro-elution; 5 nmol of protein (approx. 75 micrograms), in all, was necessary for the determination of the complete sequence by the 'shot-gun' microsquencing technique; with the use of several site-specific endoproteinases, the various digests of S-carboxymethylated J chain were separated by micro-bore reverse-phase h.p.l.c. and the partial N-terminal sequences of all peptides were analysed. From the sequence alignment, gaps were filled by further extensive sequencing of the relevant overlapping fragments isolated from selected digests. Rabbit J chain comprises 136 amino acid residues, out of which eight are conserved cysteine residues, and is more closely similar to the human sequence (73.5% identify) than to the mouse sequence (68% identity). There is one unique glycosylation site at asparagine-48.     

Comparison of protein structures by growing neighborhood alignments

Background  

Design of protein structure comparison algorithm is an important research issue, having far reaching implications. In this article, we describe a protein structure comparison scheme, which is capable of detecting correct alignments even in difficult cases, e.g. non-topological similarities. The proposed method computes protein structure alignments by comparing, small substructures, called neighborhoods. Two different types of neighborhoods, sequence and structure, are defined, and two algorithms arising out of the scheme are detailed. A new method for computing equivalences having non-topological similarities from pairwise similarity score is described. A novel and fast technique for comparing sequence neighborhoods is also developed.     

The structure of bovine rhodopsin

We have isolated 16 peptides from a cyanogen bromide digest of rhodopsin. These cyanogen bromide peptides account for the complete composition of the protein. Methionine-containing peptides from other chemical and enzymatic digests of rhodopsin have allowed us to place the cyanogen bromide peptides in order, yielding the sequence of the protein. We have completed the sequence of most of the cyanogen bromide peptides. This information, in conjunction with that from other laboratories, forms the basis for our prediction of the secondary structure of the protein and how it may be arranged in the disk membrane.     

Simplified partial digest problem: enumerative and dynamic programming algorithms

We study the Simplified Partial Digest Problem (SPDP), which is a mathematical model for a new simplified partial digest method of genome mapping. This method is easy for laboratory implementation and robust with respect to the experimental errors. SPDP is NP-hard in the strong sense. We present an $O(n2;n)$ time enumerative algorithm and an O(n(2q)) time dynamic programming algorithm for the error-free SPDP, where $n$ is the number of restriction sites and n is the number of distinct intersite distances. We also give examples of the problem, in which there are 2(n+2)/(3)-1 non-congruent solutions. These examples partially answer a question recently posed in the literature about the number of solutions of SPDP. We adapt our enumerative algorithm for handling SPDP with imprecise input data. Finally, we describe and discuss the results of the computer experiments with our algorithms.     

The restriction scaffold problem.

Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation, and relative distance is unknown. We propose here a new technique that supplements the shotgun assembly data by experimentally simple and commonly used complete restriction digests of the target. By computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order, and distance. We give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. The key to the success of the search scheme is the very rapid solution of two time-critical subproblems that are solved to optimality in linear time. Our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using six enzymes, most datasets of 13 contigs spanning 300kb can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. Hence, the technique has a potential to provide real help to finishing. Even without closing all gaps, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.     

Algorithms for optical mapping.

Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The problem is complicated by uncertainty as to the orientation of the molecules and by erroneous detection of cuts. In this paper we study the problem of constructing a restriction map based on optical mapping data. We give several variants of a polynomial reconstruction algorithm, as well as an algorithm that is exponential in the number of cut sites, and hence is appropriate only for small number of cut sites. We give a simple probabilistic model for data generation and for the errors and prove probabilistic upper and lower bounds on the number of molecules needed by each algorithm in order to obtain a correct map, expressed as a function of the number of cut sites and the error parameters. To the best of our knowledge, this is the first probabilistic analysis of algorithms for the problem. We also provide experimental results confirming that our algorithms are highly effective on simulated data.     

A stochastic online algorithm for unloading boxes from a conveyor line

This article discusses the problem of unloading a sequence of boxes from a single conveyor line with a minimum number of moves. The problem under study is efficiently solvable with dynamic programming if the complete sequence of boxes is known in advance. In practice, however, the problem typically occurs in a real-time setting where the boxes are simultaneously placed on and picked from the conveyor line. Moreover, a large part of the sequence is often not visible. As a result, only a part of the sequence is known when deciding which boxes to move next. We develop an online algorithm that evaluates the quality of each possible move with a scenario-based stochastic method. Two versions of the algorithm are analyzed: in one version, the quality of each scenario is measured with an exact method, while a heuristic technique is applied in the second version. We evaluate the performance of the proposed algorithms using extensive computational experiments and establish a simple policy for determining which version to choose for specific problems. Numerical results show that the proposed approach consistently provides high-quality results, and compares favorably with the best known deterministic online algorithms. Indeed, the new approach typically provides results with relative gaps of 1–5% to the optimum, which is about 20–80% lower than those obtained with the best deterministic approach.     

An improved method of partially digesting plant megabase DNA suitable for YAC cloning: application to the construction of a 5.5 genome equivalent YAC library of tomato

An improved method for preparing partially digested tomato DNA has been developed, that is suitable for YAC cloning. It involves (i) isolation of high molecular-weight DNA from agarose-embedded leaf protoplasts, (ii) controlled partial digestion in situ using Eco RI endonuclease in the presence of Eco RI methylase (M. Eco RI), and (iii) fractionation of the partial digest on a Clamped Homogeneous Electric Fields (CHEF) gel. Unlike methods commonly used for generating partial digests, the present method allows one to produce digests in which the bulk of restriction fragments are of the desired size. Use of these partial digests in constructing YAC libraries of the tomato lines Moneymaker- Cf4 and VFNT Cherry resulted in libraries (total 21 060 clones, 5.5 genome equivalents) in which 80% of the YACs have inserts between 200 and 600 kb. Both libraries have been screened with selected RFLP markers linked to the Cladosporium fulvum Cf4 locus on chromosome 1, using a three-dimensional PCR-based screening technique. To this end, the RFLP markers have been sequenced to allow for the synthesis of specific primers. Thus, for each marker tested several YAC clones have been isolated, including a family of clones that carry leucine-rich repeat sequences located around the Cf4/ Cf9 locus.     

Sampling Solution Traces for the Problem of Sorting Permutations by Signed Reversals

ABSTRACT: BACKGROUND: Traditional algorithms to solve the problem of sorting by signed reversals output just one optimal solution while the space of all optimal solutions can be huge. A so-called trace represents a group of solutions which share the same set of reversals that must be applied to sort the original permutation following a partial ordering. By using traces, we therefore can represent the set of optimal solutions in a more compact way. Algorithms for enumerating the complete set of traces of solutions were developed. However, due to their exponential complexity, their practical use is limited to small permutations. A partial enumeration of traces is a sampling of the complete set of traces and can be an alternative for the study of distinct evolutionary scenarios of big permutations. Ideally, the sampling should be done uniformly from the space of all optimal solutions. This is however conjectured to be #P-complete. RESULTS: We propose and evaluate three algorithms for producing a sampling of the complete set of traces that instead can be shown in practice to preserve some of the characteristics of the space of all solutions. The first algorithm (RA) performs the construction of traces through a random selection of reversals on the list of optimal 1-sequences. The second algorithm (DFALT) consists in a slight modification of an algorithm that performs the complete enumeration of traces. Finally, the third algorithm (SWA) is based on a sliding window strategy to improve the enumeration of traces. All proposed algorithms were able to enumerate traces for permutations with up to 200 elements. CONCLUSIONS: We analysed the distribution of the enumerated traces with respect to their height and average reversal length. Various works indicate that the reversal length can be an important aspect in genome rearrangements. The algorithms RA and SWA show a tendency to lose traces with high average reversal length. Such traces are however rare, and qualitatively our results show that, for testable-sized permutations, the algorithms DFALT and SWA produce distributions which approximate the reversal length distributions observed with a complete enumeration of the set of traces.