Search PubMed⌕ Search

Biomedical subjects

R Durbin

Publications and source records attributed to R Durbin.

At least 37 records · Page 2Linked to original sources
PubMed1998

Dynamic programming alignment accuracy.

Algorithms for generating alignments of biological sequences have inherent statistical limitations when it comes to the accuracy of the alignments they produce. Using simulations, we measure the accuracy of the standard global dynamic programming method and show that it can be reasonably well modelled by an "edge wander" approximation to the distribution of the optimal scoring path around the correct path in the vicinity of a gap. We also give a table from which accuracy values can be predicted for commonly used scoring schemes and sequence divergences (the PAM and BLOSUM series). Finally we describe how to calculate the expected accuracy of a given alignment, and show how this can be used to construct an optimal accuracy alignment algorithm which generates significantly more accurate alignments than standard dynamic programming methods in simulated experiments.

Algorithms↗
PubMed1998

Sequence assembly with CAFTOOLS.

Large-scale genomic sequencing requires a software infrastructure to support and integrate applications that are not directly compatible. We describe a suite of software tools built around the Common Assembly Format (CAF), a comprehensive representation of a sequence assembly as a text file. These tools form the backbone of sequencing informatics at the Sanger Centre and the Genome Sequencing Center. The CAF format is intentionally flexible, and our Perl and C libraries, which parse and manipulate it, provide powerful tools for creating new applications as well as wrappers to incorporate other software. The tools are available free by anonymous FTP from ftp://ftp.sanger.ac.uk/pub/badger/.

Algorithms↗
PubMed1997

Analysis of protein domain families in Caenorhabditis elegans.

The Caenorhabditis elegans genome sequencing project has completed over half of this nematode's 100-Mb genome. Proteins predicted in the finished sequence have been compiled and released in the data-base Wormpep. Presented here is a comprehensive analysis of protein domain families in Wormpep 11, which comprises 7299 proteins. The relative abundance of common protein domain families was counted by comparing all Wormpep proteins to the Pfam collection of protein families, which is based on recognition by hidden Markov models. This analysis also identified a number of previously unannotated domains. To investigate new apparently nematode-specific protein families, Wormpep was clustered into domain families on the basis of sequence similarity using the Domainer program. The largest clusters that lacked clear homology to proteins outside Nematoda were analyzed in further detail, after which some could be assigned a putative function. We compared all proteins in Wormpep 11 to proteins in the human, Saccharomyces cerevisiae, and Haemophilus influenzae genomes. Among the results are the estimation that over two-thirds of the currently known human proteins are likely to have a homologue in the whole C. elegans genome and that a significant number of proteins are well conserved between C. elegans and H. influenzae, that are not found in S. cerevisiae.

Amino Acid Sequence↗
PubMed1997

Pfam: a comprehensive database of protein domain families based on seed alignments.

Databases of multiple sequence alignments are a valuable aid to protein sequence classification and analysis. One of the main challenges when constructing such a database is to simultaneously satisfy the conflicting demands of completeness on the one hand and quality of alignment and domain definitions on the other. The latter properties are best dealt with by manual approaches, whereas completeness in practice is only amenable to automatic methods. Herein we present a database based on hidden Markov model profiles (HMMs), which combines high quality and completeness. Our database, Pfam, consists of parts A and B. Pfam-A is curated and contains well-characterized protein domain families with high quality alignments, which are maintained by using manually checked seed alignments and HMMs to find and align all members. Pfam-B contains sequence families that were generated automatically by applying the Domainer algorithm to cluster and align the remaining protein sequences after removal of Pfam-A domains. By using Pfam, a large number of previously unannotated proteins from the Caenorhabditis elegans genome project were classified. We have also identified many novel family memberships in known proteins, including new kazal, Fibronectin type III, and response regulator receiver domains. Pfam-A families have permanent accession numbers and form a library of HMMs available for searching and automatic annotation of new protein sequences.

Amino Acid Sequence↗
PubMed1997

Gene expression and development databases for C. elegans

The nematode worm C. elegans, with its transparent body, is an excellent vehicle for studying developmental gene expression during embryogenesis and throughout its short life. Expression data from in-situ hybridization, immunolocalization and reporter constructs have been put into the ACeDB database, which is used to store and disseminate most types of C. elegans data, and is also widely used for genome-sequencing projects. In the database, the gene-expression patterns are linked to genes, sequences, cells, organs and the developmental stage in which expression occurs. An accessory program 'Angler' can be used to browse sectional Nomarski images of the worm embryo during early development, and to relate these images to overlaid cell lineage data and 3-D schematic views of cell positions.Copyright 1997 Academic Press Limited Copyright 1997Academic Press Limited

Journal Article↗
PubMed1997

Dynamite: a flexible code generating language for dynamic programming methods used in sequence comparison.

We have developed a code generating language, called Dynamite, specialised for the production and subsequent manipulation of complex dynamic programming methods for biological sequence comparison. From a relatively simple text definition file Dynamite will produce a variety of implementations of a dynamic programming method, including database searches and linear space alignments. The speed of the generated code is comparable to hand written code, and the additional flexibility has proved invaluable in designing and testing new algorithms. An innovation is a flexible labelling system, which can be used to annotate the original sequences with biological information. We illustrate the Dynamite syntax and flexibility by showing definitions for dynamic programming routines (i) to align two protein sequences under the assumption that they are both poly-topic transmembrane proteins, with the simultaneous assignment of transmembrane helices and (ii) to align protein information to genomic DNA, allowing for introns and sequencing error.

Algorithms↗
PubMed1995

A dot-matrix program with dynamic threshold control suited for genomic DNA and protein sequence analysis.

Graphical dot-matrix plots can provide the most complete and detailed comparison of two sequences. Presented here is DOTTER2, a dot-plot program for X-windows which can compare DNA or protein sequences, and also DNA versus protein. The main novel feature of DOTTER is that the user can vary the stringency cutoffs interactively, so that the dot-matrix only needs to be calculated once. This is possible thanks to a 'Greyramp tool' that was developed to change the displayed stringency of the matrix by dynamically changing the greyscale rendering of the dots. The Greyramp tool allows the user to interactively change the lower and upper score limit for the greyscale rendering. This allows exploration of the separation between signal and noise, and fine-grained visualisation of different score levels in the dot-matrix. Other useful features are dot-matrix compression, mouse-controlled zooming, sequence alignment display and saving/loading of dot-matrices. Since the matrix only has to be calculated once and since the algorithm is fast and linear in space, DOTTER is practical to use even for sequences as long as cosmids. DOTTER was integrated in the gene-modelling module of the genomic database system ACEDB3. This was done via the homology viewer BLIXEM in a way that also allows segments from the BLAST suite of searching programs to be superimposed on top of the full dot-matrix. This feature can also be used for very quick finding of the strongest matches. As examples, we analyse a Caenorhabditis elegans cosmid with several tandem repeat families, and illustrate how DOTTER can improve gene modelling.

Amino Acid Sequence↗
PubMed1995

Comparative sequence analysis of the human and pufferfish Huntington's disease genes.

The Huntington's disease (HD) gene encodes a novel protein with as yet no known function. In order to identify the functionally important domains of this protein, we have cloned and sequenced the homologue of the HD gene in the pufferfish, Fugu rubripes. The Fugu HD gene spans only 23 kb of genomic DNA, compared to the 170 kb human gene, and yet all 67 exons are conserved. The first coding exon, the site of the disease-causing triplet repeat, is highly conserved. However, the glutamine repeat in Fugu consists of just four residues. We also show that gene order may be conserved over longer stretches of the two genomes. Our work describes a detailed example of sequence comparison between human and Fugu, and illustrates the power of the pufferfish genome as a model system in the analysis of human genes.

Amino Acid Sequence↗
PubMed1995

Method for calculation of probability of matching a bounded regular expression in a random data string.

A method is presented for determining within strict bounds the probability of matching a regular expression with a match start point in a given section of a random data string. The method in general requires time and space exponential in the number of optional characters in the regular expression, but in practice was used to determine bounds for probabilities of matching all the ProSite patterns without difficulty.

Algorithms↗
PubMed1995

Maximum discrimination hidden Markov models of sequence consensus.

We introduce a maximum discrimination method for building hidden Markov models (HMMs) of protein or nucleic acid primary sequence consensus. The method compensates for biased representation in sequence data sets, superseding the need for sequence weighting methods. Maximum discrimination HMMs are more sensitive for detecting distant sequence homologs than various other HMM methods or BLAST when tested on globin and protein kinase catalytic domain sequences.

Algorithms↗
PubMed1994

RNA sequence analysis using covariance models.

We describe a general approach to several RNA sequence analysis problems using probabilistic models that flexibly describe the secondary structure and primary sequence consensus of an RNA sequence family. We call these models 'covariance models'. A covariance model of tRNA sequences is an extremely sensitive and discriminative tool for searching for additional tRNAs and tRNA-related sequences in sequence databases. A model can be built automatically from an existing sequence alignment. We also describe an algorithm for learning a model and hence a consensus secondary structure from initially unaligned example sequences and no prior structural information. Models trained on unaligned tRNA examples correctly predict tRNA secondary structure and produce high-quality multiple alignments. The approach may be applied to any family of small RNA sequences.

Algorithms↗
PubMed1994

A workbench for large-scale sequence homology analysis.

When routinely analysing very long stretches of DNA sequences produced by genome sequencing projects, detailed analysis of database search results becomes exceedingly time consuming. To reduce the tedious browsing of large quantities of protein similarities, two programs, MSPcrunch and Blixem, were developed, which assist in processing the results from the database search programs in the BLAST suite. MSPcrunch removes biased composition and redundant matches while keeping weak matches that are consistent with a larger gapped alignment. This makes BLAST searching in practice more sensitive and reduces the risk of overlooking distant similarities. Blixem is a multiple sequence alignment viewer for X-windows which makes it significantly easier to scan and evaluate the matches ratified by MSPcrunch. In Blixem, matches to the translated DNA query sequence are simultaneously aligned in three frames. Also, the distribution of matches over the whole DNA query is displayed. Examples of usage are drawn from 36 C. elegans cosmid clones totalling 1.2 megabases, to which these tools were applied.

Algorithms↗
PubMed1994

An expert system for processing sequence homology data.

When confronted with the task of finding homology to large numbers of sequences, database searching tools such as Blast and Fasta generate prohibitively large amounts of information. An automatic way of making most of the decisions a trained sequence analyst would make was developed by means of a rule-based expert system combined with an algorithm to avoid non-informative biased residue composition matches. The results found relevant by the system are presented in a very concise and clear way, so that the homology can be assessed with minimum effort. The expert system, HSPcrunch, was implemented to process the output to the programs in the BLAST suite. HSPcrunch embodies rules on detecting distant similarities when pairs of weak matches are consistent with a larger gapped alignment, i.e. when Blast has broken a longer gapped alignment up into smaller ungapped ones. This way, more distant similarities can be detected with no or little side-effects of more spurious matches. The rules for how small the gaps must be to be considered significant have been derived empirically. Currently a set of rules are used that operate on two different scoring levels, one for very weak matches that have very small gaps and one for medium weak matches that have slightly larger gaps. This set of rules proved to be robust for most cases and gives high fidelity separation between real homologies and spurious matches. One of the most important rules for reducing the amount of output is to limit the number of overlapping matches to the same region of the query sequence.(ABSTRACT TRUNCATED AT 250 WORDS)

Amino Acid Sequence↗
PubMed1992

A survey of expressed genes in Caenorhabditis elegans.

As an adjunct to the genomic sequencing of Caenorhabditis elegans, we have investigated a representative cDNA library of 1,517 clones. A single sequence read has been obtained from the 5' end of each clone, allowing its characterization with respect to the public databases, and the clones are being localized on the genome map. The result is the identification of about 1,200 of the estimated 15,000 genes of C. elegans. More than 30% of the inferred protein sequences have significant similarity to existing sequences in the databases, providing a route towards in vivo analysis of known genes in the nematode. These clones also provide material for assessing the accuracy of predicted exons and splicing patterns and will lead to a more accurate estimate of the total number of genes in the organism than has hitherto been available.

Animals↗