Biomedical subjects

T D Wu

Publications and source records attributed to T D Wu.

6 recordsLinked to original sources

PubMed1998

Highly specific protein sequence motifs for genome analysis.

We present a method for discovering conserved sequence motifs from families of aligned protein sequences. The method has been implemented as a computer program called EMOTIF (http://motif. stanford.edu/emotif). Given an aligned set of protein sequences, EMOTIF generates a set of motifs with a wide range of specificities and sensitivities. EMOTIF also can generate motifs that describe possible subfamilies of a protein superfamily. A disjunction of such motifs often can represent the entire superfamily with high specificity and sensitivity. We have used EMOTIF to generate sets of motifs from all 7,000 protein alignments in the BLOCKS and PRINTS databases. The resulting database, called IDENTIFY (http://motif. stanford.edu/identify), contains more than 50,000 motifs. For each alignment, the database contains several motifs having a probability of matching a false positive that range from 10(-10) to 10(-5). Highly specific motifs are well suited for searching entire proteomes, while generating very few false predictions. IDENTIFY assigns biological functions to 25-30% of all proteins encoded by the Saccharomyces cerevisiae genome and by several bacterial genomes. In particular, IDENTIFY assigned functions to 172 of proteins of unknown function in the yeast genome.

Amino Acid Sequence↗

PubMed1997

Enumerating and ranking discrete motifs.

Discrete motifs that discriminate functional classes of proteins are useful for classifying new sequences, capturing structural constraints, and identifying protein subclasses. Despite the fact that the space of such motifs can grow exponentially with sequence length and number, we show that in practice it usually does not, and we describe a technique that infers motifs from aligned protein sequences by exhaustively searching this space. Our method generates sequence motifs over a wide range of recall and precision, and chooses a representative motif based on a score that we derive from both statistical and information-theoretic frameworks. Finally, we show that the selected motifs perform well in practice, classifying unseen sequences with extremely high precision, and infer protein subclasses that correspond to known biochemical classes.

Algorithms↗

PubMed1996

A segment-based dynamic programming algorithm for predicting gene structure.

An algorithm called segment-based dynamic programming is described for predicting gene structure from a sequence of genomic DNA. The algorithm explores the space of gene structures that satisfy junctional and frame constraints and finds the gene structure that optimizes the sum of junctional and segmental scoring functions. Junctional constraints specify acceptable sites of initiation, termination, and splicing, whereas frame constraints ensure that the total exon length is a multiple of three and that no in-frame stop codons occur within exons or at exon-exon junctions. By computing over segments, segment-based dynamic programming maintains reading frame and phase information for each segment, it can assemble exons in-frame as well as score them in-frame. The algorithm is used to quantify the computational power of constraints. Experimental results show that frame constraints reduce the size of the search space by several orders of magnitude and that cardinality constraints place an asymptotic limit on the size of the search space. The algorithm is also used to compare the accuracy of different methods for assembly and scoring. A scoring scheme based on fifth-order Markov hexamer frequencies is presented and used in three objective functions, corresponding to in-frame, frame-independent, and frame-maximal scoring strategies. Experimental results show that in-frame assembly improves specificity only slightly over frame-independent assembly, whereas in-frame scoring improves specificity substantially over frame-independent and frame-maximal scoring.

Algorithms↗

PubMed1996

Discovering empirically conserved amino acid substitution groups in databases of protein families.

This paper introduces a method for identifying empirically conserved amino acid substitution groups. In contrast with existing approaches that view amino acid substitution as a pairwise phenomenon, the method presented here identifies conserved groups of amino acids using a data structure called a conditional distribution matrix. The conditional distribution matrix extends the concept of a pairwise substitution matrix by changing the context of substitution from a single amino acid to a group of amino acids. The matrix tabulates information from a database of protein families that contains numerous aligned positions. Each row in the matrix contains the distribution of amino acids in those aligned positions that contain a given conditioning group of amino acids. The method converts a database of protein families into a conditional distribution matrix and then examines each possible substitution group for evidence of conservation. The algorithm is applied to the BLOCKS and HSSP databases. Twenty amino acid substitution groups are found to be conserved empirically in both databases. These groups provide insight into biochemical properties that are conserved in protein evolution.

Algorithms↗

PubMed1995

Identification of protein motifs using conserved amino acid properties and partitioning techniques.

Analyzing a set of protein sequences involves a fundamental relationship between the coherency of the set and the specificity of the motif that describes it. Motifs may be obscured by training sets that contain incoherent sequences, in part due to protein subclasses, contamination, or errors. We develop an algorithm for motif identification that systematically explores possible patterns of coherency within a set of protein sequences. Our algorithm constructs alternative partitions of the training set data, where one subset of each partition is presumed to contain coherent data and is used for forming a motif. The motif is represented by multiple overlapping amino acid groups based on evolutionary, biochemical, or physical properties. We demonstrate our method on a training set of reverse transcriptases that contains subclasses, sequence errors, misalignments, and contaminating sequences. Despite these complications, our program identifies a novel motif for the subclass of retroviral and retrovirus-related reverse transcriptases. This motif has a much higher specificity than previously reported motifs and suggests the importance of conserved hydrophilic and hydrophobic residues in the structure of reverse transcriptases.

Algorithms↗

PubMed1991

A problem decomposition method for efficient diagnosis and interpretation of multiple disorders.

Diagnosis of multiple disorders can be made more efficient by reasoning explicitly about problem decompositions. A diagnostic problem can be decomposed by hypothesizing about common and disjoint cause relationships among the given symptoms. The resulting structure exploits computational principles of causal intersection, subproblem independence, and minimal factorability to increase efficiency. By assigning structure to a problem, the symptom decomposition approach offers a new type of decision-support task called symptom interpretation. Experimental results indicate that symptom decomposition yields substantial increases in performance compared to existing methods for multidisorder diagnosis.

Algorithms↗