Detection and resolution of closely related satellite DNA sequences by molecular cloning.

Highly repeated satellite DNAs often consist of mixtures of DNAs with closely related repeating sequences. By cloning individual molecules we have resolved the 1.705 g/cm³ satellite DNA of Drosophila melanogaster into two distinct components: poly$\text{d}\text{A-A-G-A-G}\text{T-T-C-T-C}$ and poly$\text{d}\text{A-A-G-A-G-A-G}\text{T-T-C-T-C-T-C}$. The presence of two distinct sequences within this physically homogeneous satellite DNA had not previously been detected by standard physical, chemical, or sequencing techniques. Both cloning and direct sequence analysis suggest that the five-base-pair and seven-base-pair repeating units reside on separate molecules and are not interspersed with each other.     

Cloning and characterization of a complex satellite DNA from Drosophila melanogaster.

The sequence organization of the 1.688 satellite DNA (density 1.688 g/cm³ in CsCl) has been investigated, and this satellite has been found to differ from the other D. melanogaster satellite DNAs in having a much greater sequence complexity. Purification of 1.688 satellite DNA by successive equilibrium density centrifugations yielded a fraction 77% pure. Segments of satellite DNA were isolated by molecular cloning in the plasmid vector pSC101. One recombinant plasmid contained a segment of 1.688 satellite DNA 5.8 kilobase pairs in size and was stable during propagation in E. coli. Recognition sites for restriction enzymes from Haemophilus aegyptius (Hae III), Haemophilus influenzae f (Hinf) and Arthrobacter luteus (Alu I) were mapped in the satellite DNA of this hybrid plasmid. The spacing of Hae III, Hinf and two Alu I sites at regular intervals of about 365 base pairs is strong evidence that the sequence complexity of this satellite DNA is 365 base pairs. Further evidence comes from the finding that both gradient-purified and cloned 1.688 satellite DNA renature with their Hae III sites in register. The Hae III and Hinf sites in gradient-purified satellite DNA have been shown by Manteuil, Hamer and Thomas (1975) and Shen, Wiesehahn and Hearst (1976) to be distributed at intervals of 365 base pairs and integral multiples thereof. These investigators proposed that some of the sites in an otherwise regular array have been randomly inactivated. Cloned satellite DNA provided a hybridization probe for sensitive studies of the arrangement of these recognition sites in gradient-purified satellite DNA. Some regions of satellite DNA were found to contain many fewer recognition sites than expected from the proposed models. These findings suggest that different regions of 1.688 satellite DNA may exhibit different arrangements of Hae III and Hinf recognition sites.     

MAXAMIZE. A DNA sequencing strategy advisor.

The MAXAMIZE advisory system determines from user-provided restriction maps an optimal strategy to do nucleotide sequencing by methods involving end-labeled fragments. The maps may be either simple linear restriction maps of fragments or complex circular maps including restriction sites of a vector. The whole system is interactive and is written in the Genetic English language provided by the GENESIS System, a molecular genetics knowledge representation and manipulation package. In addition, MAXAMIZE provides bookkeeping facilities for sequencing and offers advise on how to verify the newly obtained sequence data.     

DNA topoisomerase II from Drosophila melanogaster. Relaxation of supercoiled DNA

In order to study the double-strand DNA passage reaction of eukaryotic type II topoisomerases, a quantitative assay to monitor the enzymic conversion of supercoiled circular DNA to relaxed circular DNA was developed. Under conditions of maximal activity, relaxation catalyzed by the Drosophila melanogaster topoisomerase II was processive and the energy of activation was 14.3 kcal . mol-1. Removal of supercoils was accompanied by the hydrolysis of either ATP or dATP to inorganic phosphate and the corresponding nucleoside diphosphate. Apparent Km values were 200 microM for pBR322 plasmid DNA, 140 microM for SV40 viral DNA, 280 microM for ATP, and 630 microM for dATP. The turnover number for the Drosophila enzyme was at least 200 supercoils of DNA relaxed/min/molecule of topoisomerase II. The enzyme interacts preferentially with negatively supercoiled DNA over relaxed molecules, is capable of removing positive superhelical twists, and was found to be strongly inhibited by single-stranded DNA. Kinetic and inhibition studies indicated that the beta and gamma phosphate groups, the 2'-OH of the ribose sugar, and the C6-NH2 of the adenine ring are important for the interaction of ATP with the enzyme. While the binding of ATP to Drosophila topoisomerase II was sufficient to induce a DNA strand passage event, hydrolysis was required for enzyme turnover. The ATPase activity of the topoisomerase was stimulated 17-fold by the presence of negatively supercoiled DNA and approximately 4 molecules of ATP were hydrolyzed/supercoil removed. Finally, a kinetic model describing the switch from a processive to a distributive relaxation reaction is presented.     

The EMOTIF database

The EMOTIF database is a collection of more than 170 000 highly specific and sensitive protein sequence motifs representing conserved biochemical properties and biological functions. These protein motifs are derived from 7697 sequence alignments in the BLOCKS+ database (released on June 23, 2000) and all 8244 protein sequence alignments in the PRINTS database (version 27.0) using the emotif-maker algorithm developed by Nevill-Manning et al. (Nevill-Manning,C.G., Wu,T.D. and Brutlag,D.L. (1998) Proc. Natl Acad. Sci. USA, 95, 5865-5871; Nevill-Manning,C.G., Sethi,K.S., Wu,T. D. and Brutlag,D.L. (1997) ISMB-97, 5, 202-209). Since the amino acids and the groups of amino acids in these sequence motifs represent critical positions conserved in evolution, search algorithms employing the EMOTIF patterns can identify and classify more widely divergent sequences than methods based on global sequence similarity. The emotif protein pattern database is available at http://motif.stanford.edu/emotif/.     

Fast probabilistic analysis of sequence function using scoring matrices

MOTIVATION: We present techniques for increasing the speed of sequence analysis using scoring matrices. Our techniques are based on calculating, for a given scoring matrix, the quantile function, which assigns a probability, or p, value to each segmental score. Our techniques also permit the user to specify a p threshold to indicate the desired trade-off between sensitivity and speed for a particular sequence analysis. The resulting increase in speed should allow scoring matrices to be used more widely in large-scale sequencing and annotation projects. RESULTS: We develop three techniques for increasing the speed of sequence analysis: probability filtering, lookahead scoring, and permuted lookahead scoring. In probability filtering, we compute the score threshold that corresponds to the user-specified p threshold. We use the score threshold to limit the number of segments that are retained in the search process. In lookahead scoring, we test intermediate scores to determine whether they will possibly exceed the score threshold. In permuted lookahead scoring, we score each segment in a particular order designed to maximize the likelihood of early termination. Our two lookahead scoring techniques reduce substantially the number of residues that must be examined. The fraction of residues examined ranges from 62 to 6%, depending on the p threshold chosen by the user. These techniques permit sequence analysis with scoring matrices at speeds that are several times faster than existing programs. On a database of 12 177 alignment blocks, our techniques permit sequence analysis at a speed of 225 residues/s for a p threshold of 10-6, and 541 residues/s for a p threshold of 10-20. In order to compute the quantile function, we may use either an independence assumption or a Markov assumption. We measure the effect of first- and second-order Markov assumptions and find that they tend to raise the p value of segments, when compared with the independence assumption, by average ratios of 1.30 and 1.69, respectively. We also compare our technique with the empirical 99. 5th percentile scores compiled in the BLOCKSPLUS database, and find that they correspond on average to a p value of 1.5 x 10-5. AVAILABILITY: The techniques described above are implemented in a software package called EMATRIX. This package is available from the authors for free academic use or for licensed commercial use. The EMATRIX set of programs is also available on the Internet at http://motif.stanford.edu/ematrix.     

Dynamic use of multiple parameter sets in sequence alignment

The level of conservation between two homologous sequences often varies among sequence regions; functionally important domains are more conserved than the remaining regions. Thus, multiple parameter sets should be used in alignment of homologous sequences with a stringent parameter set for highly conserved regions and a moderate parameter set for weakly conserved regions. We describe an alignment algorithm to allow dynamic use of multiple parameter sets with different levels of stringency in computation of an optimal alignment of two sequences. The algorithm dynamically considers various candidate alignments, partitions each candidate alignment into sections, and determines the most appropriate set of parameter values for each section of the alignment. The algorithm and its local alignment version are implemented in a computer program named GAP4. The local alignment algorithm in GAP4, that in its predecessor GAP3, and an ordinary local alignment program SIM were evaluated on 257716 pairs of homologous sequences from 100 protein families. On 168475 of the 257716 pairs (a rate of 65.4%), alignments from GAP4 were more statistically significant than alignments from GAP3 and SIM.     

MotifCut: regulatory motifs finding with maximum density subgraphs

MOTIVATION: DNA motif finding is one of the core problems in computational biology, for which several probabilistic and discrete approaches have been developed. Most existing methods formulate motif finding as an intractable optimization problem and rely either on expectation maximization (EM) or on local heuristic searches. Another challenge is the choice of motif model: simpler models such as the position-specific scoring matrix (PSSM) impose biologically unrealistic assumptions such as independence of the motif positions, while more involved models are harder to parametrize and learn. RESULTS: We present MotifCut, a graph-theoretic approach to motif finding leading to a convex optimization problem with a polynomial time solution. We build a graph where the vertices represent all k-mers in the input sequences, and edges represent pairwise k-mer similarity. In this graph, we search for a motif as the maximum density subgraph, which is a set of k-mers that exhibit a large number of pairwise similarities. Our formulation does not make strong assumptions regarding the structure of the motif and in practice both motifs that fit well the PSSM model, and those that exhibit strong dependencies between position pairs are found as dense subgraphs. We benchmark MotifCut on both synthetic and real yeast motifs, and find that it compares favorably to existing popular methods. The ability of MotifCut to detect motifs appears to scale well with increasing input size. Moreover, the motifs we discover are different from those discovered by the other methods. AVAILABILITY: MotifCut server and other materials can be found at motifcut.stanford.edu.