Search PubMed⌕ Search

Biomedical subjects

M Vingron

Publications and source records attributed to M Vingron.

At least 55 records · Page 3Linked to original sources
PubMed1998

A polyhedral approach to RNA sequence structure alignment.

Ribonucleic acid (RNA) is a polymer composed of four bases denoted A, C, G, and U. It generally is a single-stranded molecule where the bases form hydrogen bonds within the same molecule leading to structure formation. In comparing different homologous RNA molecules it is important to consider both the base sequence and the structure of the molecules. Traditional alignment algorithms can only account for the sequence of bases, but not for the base pairings. Considering the structure leads to significant computational problems because of the dependencies introduced by the base pairings. In this paper we address the problem of optimally aligning a given RNA sequence of unknown structure to one of known sequence and structure. We phrase the problem as an integer linear program and then solve it using methods from polyhedral combinatorics. In our computational experiments we could solve large problem instances--23S ribosomal RNA with more than 1400 bases--a size intractable for former algorithms.

Algorithms↗
PubMed1998

Statistics of large-scale sequence searching.

MOTIVATION: Database search programs such as FASTA, BLAST or a rigorous Smith-Waterman algorithm produce lists of database entries, which are assumed to be related to the query. The computation of statistical significance of similarity scores is well established for single pairs of sequences and using purely random models. However, the multi-trial context of a database search poses new problems. The credibility of a certain score obtained in a database search decreases with the amount of data that is compared. To improve p-value computation for database search experiments, statistical properties of the databases, such as the distribution of sequence length and effects induced by frequently repeated sequence patterns, need to be taken into account. RESULTS: We investigated the SWISS-PROT protein database Release 31.0 running extensive simulations of database searches. A discrepancy is observed between the theoretical predictions and the empirical distribution. To correct for this, we evaluate the statistical significance of scores in the context of a database search by a contrasting semi-random model. This model enhances purely random models by one additional parameter reflecting individual statistical properties of real databases. We call this parameter the effective size of the database. CONTACT: r.spang@dkfz-heidelberg.de;m.vingron@dkfz-hei del berg.de

Computational Biology↗
PubMed1998

Towards detection of orthologues in sequence databases.

MOTIVATION: Numerous homologous sequences from diverse species can be retrieved from databases using programs such as BLAST. However, due to multigene families, evolutionary relationship often cannot be easily determined and proper functional assignment becomes difficult. Thus, discrimination between orthologues and paralogues within BLAST output lists of homologous sequences becomes more and more important. RESULT: We therefore developed a method that attempts to construct a reconciled tree from a gene tree of selected sequences and its corresponding phylogenetic tree of the species involved (species tree). An interface on the Web is developed to enable users to analyse the BLAST result. BLAST outputs are parsed and, for the selected sequences, multiple alignments are constructed either globally or for local regions. Bootstrapped trees are returned and compared with the expected species tree. In cases of discrepancies, gene duplications are assumed and a reconciled tree is computed. The reconciled tree shows probable orthologues and paralogues as predicted.

Computational Biology↗
PubMed1998

A set-theoretic approach to database searching and clustering.

MOTIVATION: In this paper, we introduce an iterative method of database searching and apply it to design a database clustering algorithm applicable to an entire protein database. The clustering procedure relies on the quality of the database searching routine and further improves its results based on a set-theoretic analysis of a highly redundant yet efficient to generate cluster system. RESULTS: Overall, we achieve unambiguous assignment of 80% of SWISS-PROT sequences to non-overlapping sequence clusters in an entirely automatic fashion. Our results are compared to an expert-generated clustering for validation. The database searching method is fast and the clustering technique does not require time-consuming all-against-all comparison. This allows for fast clustering of large amounts of sequences. AVAILABILITY: The resulting clustering for the PIR1 (Release 51) and SWISS-PROT (Release 34) databases is available over the Internet from http://www.dkfz-heidelberg.de/tbi/services/modest/b rowsesysters.pl. CONTACT: a.krause@dkfz-heidelberg.de; m.vingron@dkfz-heidelberg.de

Algorithms↗
PubMed1997

A new subfamily of vertebrate calpains lacking a calmodulin-like domain: implications for calpain regulation and evolution.

Calpains are calcium-dependent intracellular nonlysosomal proteases that are believed to participate in signal transduction. In vertebrates, five different calpains have so far been identified, of which three, mu-, m-, and mu/m-calpain, are ubiquitously expressed while the other two, nCL-1 (p94) and nCL-2, exhibit a restricted tissue distribution. We have identified two new vertebrate calpain genes, Capn5 and Capn6. The human and mouse amino acid sequences of these new calpains are the most divergent of the vertebrate calpains identified. They possess most of the residues conserved in calpain family members but the C-terminal region lacks any homology to the calmodulin-like domain of other vertebrate calpains. They both exhibit significant homology over the entire coding region to the protein encoded by the gene tra-3, involved in nematode sex determination, and Capn5 may represent its vertebrate orthologue. The predicted Capn6 protein lacks critical active site residues and may not be proteolytically active. Both genes are differentially expressed in human tissues with highest RNA levels for Capn5 occurring in the testis, liver, trachea, colon, and kidney, while Capn6 is highly expressed only in the placenta sample of the 50 tissues examined. Phylogenetic analysis suggests that the vertebrate calpains arose through a series of gene duplication events that began before the initial divergence of the vertebrate and invertebrate lineages. The discovery of these two new calpains highlights a hitherto unknown complexity of the calpain family with subclasses perhaps possessing different modes of regulation.

Amino Acid Sequence↗
PubMed1997

Towards integration of multiple alignment and phylogenetic tree construction.

A central problem in the study of molecular evolution is the reconstruction of the history of a set of biological sequences in the form of a phylogenetic tree. One step in calculating this tree is the computation of a multiple alignment. Most existing approaches treat the two problems of multiple alignment and tree construction as separate while in fact they influence each other. Based on three-way alignments of pre-aligned groups of sequences we adapt a commonly used tree construction procedure to produce both tree and multiple alignment simultaneously. In contrast to existing iterative algorithms the new method can change alignments made early in the course of the computation at a later stage. A sufficient criterion to prevent the introduction of edges with negative length reduces the number of three-way alignments that need to be computed. Applications of the new approach to the alignment of protein and of nucleic acid sequences are presented.

Amino Acid Sequence↗
PubMed1997

The deferred path heuristic for the generalized tree alignment problem.

Many multiple alignment methods implicitly or explicitly try to minimize the amount of biological change implied by an alignment. At the level of sequences, biological change is measured along a phylogenetic tree, a structure frequently being predicted only after the multiple alignment instead of together with it. The Generalized Tree Alignment problem addresses both questions simultaneously. It can formally be viewed as a Steiner tree problem in sequence space and our approach merges a path heuristic for the construction of a Steiner tree with a clustering method as usually applied only to distance data. This combination is achieved using sequence graphs, a data structure for efficient representation of similar sequences. Although somewhat slower in practice than an earlier method by Hein (1989) the current approach achieves significantly better results in terms of the underlying scoring function. Furthermore, a variant of the algorithm is introduced that maintains a guaranteed error bound of (2 - 2/n) for n sequences.

Algorithms↗
PubMed1997

A New Method for Database Searching and Clustering.

An iterative database searching method is introduced and applied to the design of a database clustering procedure. The search method virtually never produces false positive hits while determining meaningfully large sets of sequences related to the query. A novel set-theoretic database clustering algorithm exploits this feature and avoids a traditional, distance-based clustering step. This makes it fast and applicable to data-sets of the size of, e.g., the Swiss-Prot database. In practice we achieve unambiguous assignment of 80% of Swiss-Prot sequences to non-overlapping sequence clusters in an entirely automatic fashion.

Journal Article↗
PubMed1996

Near-optimal sequence alignment.

Recent advances in algorithmic techniques and statistics of sequence alignment have helped to make near-optimal alignments an important tool in the delineation of biologically valid alignments. Near-optimal alignments serve to judge the reliability of portions of a sequence alignment. The statistical assessment of suboptimal alignment scores makes sequence alignments less dependent on gap-penalty choice.

Algorithms↗
PubMed1996

Quantifying the local reliability of a sequence alignment.

We present a method for attributing a measure of reliability to a residue pair in an optimal alignment of two protein sequences. Validation based on a database of structurally correct alignments [Pascarella and Argos (1992) Protein Engng, 5, 121-137] shows that correctly aligned parts of a sequence alignment systematically receive high scores in this measure. The higher the sequence similarity between two sequences, the larger is the fraction found of the correct parts of the alignment. We used these observations to design a program that draws a reliability curve along an optimal alignment reflecting the chances for each residue pair to be aligned correctly.

Algorithms↗
PubMed1994

Rapid and accurate estimates of statistical significance for sequence data base searches.

A central question in sequence comparison is the statistical significance of an observed similarity. For local alignment containing gaps to optimize sequence similarity this problem has so far not been solved mathematically. Using as a basis the Chen-Stein theory of Poisson approximation, we present a practical method to approximate the probability that a local alignment score is a result of chance alone. For a set of similarity scores and gap penalties only one simulation of random alignments needs to be calculated to derive the key information allowing us to estimate the significance of any alignment calculated under this setting. We present applications to data base searching and the analysis of pairwise and self-comparisons of proteins.

Algorithms↗
PubMed1994

Sequence alignment and penalty choice. Review of concepts, case studies and implications.

Alignment algorithms to compare DNA or amino acid sequences are widely used tools in molecular biology. The algorithms depend on the setting of various parameters, most notably gap penalties. The effect that such parameters have on the resulting alignments is still poorly understood. This paper begins by reviewing two recent advances in algorithms and probability that enable us to take a new approach to this question. The first tool we introduce is a newly developed method to delineate efficiently all optimal alignments arising under all choices of parameters. The second tool comprises insights into the statistical behavior of optimal alignment scores. From this we gain a better understanding of the dependence of alignments on parameters in general. We propose novel criteria to detect biologically good alignments and highlight some specific features about the interaction between similarity matrices and gap penalties. To illustrate our analysis we present a detailed study of the comparison of two immunoglobulin sequences.

Algorithms↗
PubMed1993

Weighting in sequence space: a comparison of methods in terms of generalized sequences.

Four methods for weighting aligned biological sequences have recently appeared that differ mathematically, philosophically, and in their results. Thus, while there is consensus about the need to weight sequences, the method to use is contentious. A geometric analysis based on a continuous sequence space is presented that provides a common framework in which to compare the methods. It is concluded that there are two "best" methods. When the sequences are known to be phylogenetically related and a tree can be generated without introducing excessive stress into the data, the method of Altschul et al. [Altschul, S. F., Carroll, R. J. & Lipman, D. J. (1989) J. Mol. Biol. 207, 647-653] is appropriate. When the sequences are not known to be phylogenetically related or a tree cannot be produced without unduly distorting the distances between the sequences, a modification of the method of Sibbald and Argos [Sibbald, P. R. & Argos, P. (1990) J. Mol. Biol. 216, 813-818] is preferable.

Amino Acid Sequence↗
PubMed1993

On the specificity of carboxypeptidase N, a comparative study.

The structure of the enzymatically active subunit of human plasma carboxypeptidase N was modeled based on the homology with bovine carboxypeptidase A. The active site of carboxypeptidase N is well conserved in comparison with carboxypeptidase A. From a comparison of energetically favorable binding sites for different atomic probe groups a hypothesis for the differences in substrate specificity between carboxypeptidases A and N was derived. Small synthetic peptide substrates were synthesized to confirm this hypothesis. This study shows that even with very low homology model building by homology can be employed to build models of sufficient quality to aid in drug design.

Amino Acid Sequence↗
PubMed1992

Molecular cloning and structural analysis of genes from Zea mays (L.) coding for members of the ras-related ypt gene family.

We have isolated, cloned, and characterized two cDNAs from Zea mays (L.), denoted yptm1 and yptm2, encoding proteins related to the ypt protein family. Amino acid similarity scores with YPT1 from yeast and ypt from mouse are in the range of 70% for yptm1 and 74% for yptm2, respectively, whereas similarities with p21 ras and other ras-related proteins are less than 40%. Most amino acid residues showing identity are clustered in the GTP/GDP binding domain. In addition, two cysteine residues close to the C-terminal ends, known to be palmitoylated and necessary for membrane binding in all eukaryotic ras-related proteins that have been characterized so far, are conserved in the maize genes as well. Northern blot hybridization analysis of poly(A)+ mRNA from etiolated maize coleoptiles revealed single mRNA species of approximately the same size as the isolated cDNAs. The gene for yptm1 is expressed at very low levels in maize coleoptiles and tissue culture cells. The gene for yptm2 is expressed at higher levels and is differentially represented in RNAs isolated from various organs of maize plants, with its highest level in leaves and flowers. The structural similarity of the genes identified suggests that they could be involved in the control of secretory processes.

Amino Acid Sequence↗
PubMed1992

Comparative molecular modeling of the active subunit of human kininase I.

The structure of the enzymatically active subunit of human plasma carboxypeptidase N was determined by computer aided model building by homology using the structural coordinates from carboxypeptidase A. The active site of carboxypeptidase N has been well conserved in comparison with carboxypeptidase A. Differences in substrate specificity can be explained by the comparison of energetically favorable binding sites for different atomic probe groups.

Amino Acid Sequence↗
PubMed1991

Motif recognition and alignment for many sequences by comparison of dot-matrices.

Calculation of dot-matrices is a widespread tool in the search for sequence similarities. When sequences are distant, even this approach may fail to point out common regions. If several plots calculated for all members of a sequence set consistently displayed a similarity between them, this would increase its credibility. We present an algorithm to delineate dot-plot agreement. A novel procedure based on matrix multiplication is developed to identify common patterns and reliably aligned regions in a set of distantly related sequences. The algorithm finds motifs independent of input sequence lengths and reduces the dependence on gap penalties. When sequences share greater similarity, the same approach converts to a multiple sequence alignment procedure.

Algorithms↗