PubMed Health⌕ Search

SEARCH · PubMed Health

Results for “Sequence Alignment”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 361 records · Page 20Linked to original sources

Computational methods for protein secondary structure prediction using multiple sequence alignments.

Efforts to use computers in predicting the secondary structure of proteins based only on primary structure information started over a quarter century ago [1-3]. Although the results were encouraging initially, the accuracy of the pioneering methods generally did not attain the level required for using predictions of secondary structures reliably in modelling the three-dimensional topology of proteins. During the last decade, however, the introduction of new computational techniques as well as the use of multiple sequence information has lead to a dramatic increase in the success rate of prediction methods, such that successful 3D modelling based on predicted secondary structure has become feasible [e.g., Ref 4]. This review is aimed at presenting an overview of the scale of the secondary structure prediction problem and associated pitfalls, as well as the history of the development of computational prediction methods. As recent successful strategies for secondary structure prediction all rely on multiple sequence information, some methods for accurate protein multiple sequence alignments will also be described. While the main focus is on prediction methods for globular proteins, also the prediction of trans-membrane segments within membrane proteins will be briefly summarised. Finally, an integrated iterative approach tying secondary structure prediction and multiple alignment will be introduced [5].

Algorithms↗

Bayesian adaptive sequence alignment algorithms.

The selection of a scoring matrix and gap penalty parameters continues to be an important problem in sequence alignment. We describe here an algorithm, the 'Bayes block aligner, which bypasses this requirement. Instead of requiring a fixed set of parameter settings, this algorithm returns the Bayesian posterior probability for the number of gaps and for the scoring matrices in any series of interest. Furthermore, instead of returning the single best alignment for the chosen parameter settings, this algorithm returns the posterior distribution of all alignments considering the full range of gapping and scoring matrices selected, weighing each in proportion to its probability based on the data. We compared the Bayes aligner with the popular Smith-Waterman algorithm with parameter settings from the literature which had been optimized for the identification of structural neighbors, and found that the Bayes aligner correctly identified more structural neighbors. In a detailed examination of the alignment of a pair of kinase and a pair of GTPase sequences, we illustrate the algorithm's potential to identify subsequences that are conserved to different degrees. In addition, this example shows that the Bayes aligner returns an alignment-free assessment of the distance between a pair of sequences.

Adenylate Kinase↗

Sequence alignment of 18S ribosomal RNA and the basal relationships of Adephagan beetles: evidence for monophyly of aquatic families and the placement of Trachypachidae.

Current hypotheses regarding family relationships in the suborder Adephaga (Coleoptera) are conflicting. Here we report full-length 18S ribosomal RNA sequences of 39 adephagans and 13 outgroup taxa. Data analysis focused on the impact of sequence alignment on tree topology, using two principally different approaches. Tree alignments, which seek to minimize indels and substitutions on the tree in a single step, as implemented in an approximate procedure by the computer program POY, were contrasted with a more traditional procedure based on alignments followed by phylogenetic inference based on parsimony, likelihood, and distance analyses. Despite substantial differences between the procedures, phylogenetic conclusions regarding basal relationships within Adephaga and relationships between the four suborders of Coleoptera were broadly similar. The analysis weakly supports monophyly of Adephaga, with Polyphaga usually as its sister, and the two small suborders Myxophaga and Archostemata basal to them. In some analyses, however, Polyphaga was reconstructed as having arisen from within Hydradephaga. Adephaga generally split into two monophyletic groups, corresponding to the terrestrial Geadephaga and the aquatic Hydradephaga, as initially proposed by Crowson in 1955, consistent with a single colonization of the aquatic environment by adephagan ancestors and contradicting the recent proposition of three independent invasions. A monophyletic Hydradephaga is consistently, though not strongly, supported under most analyses, and a parametric bootstrapping test significantly rejects an hypothesis of nonmonophyly. The enigmatic Trachypachidae, which exhibit many similarities to aquatic forms but whose species are entirely terrestrial, were usually recovered as a basal lineage within Geadephaga. Strong evidence opposes the view that terrestrial trachypachids are related to the dytiscoid water beetles.

Animals↗

MSAID: multiple sequence alignment based on a measure of information discrepancy.

We propose an algorithm of global multiple sequence alignment that is based on a measure of what we call information discrepancy. The algorithm follows a progressive alignment iteration strategy that makes use of what we call a function of degree of disagreement (FDOD). MSAID begins with distance calculation of pairwise sequences, based on FDOD as a numerical scoring measure. In the next step, the resulting distance matrix is used to construct a guide tree via the neighbor-joining method. The tree is then used to produce a multiple alignment. Current alignment is next used to produce a new matrix and a new tree (with FDOD scoring measure again). This iterative process continues until convergence criteria (or a stopping rule) are satisfied. MSAID was tested and compared with other prior methods by using reference alignments from BAliBASE 2.01. For the alignments with no large N/C-terminal extensions or internal insertions MSAID received the top overall average in the tests. Moreover, the results of testing indicate that MSAID performs as well as other alignment methods with an occasional tendency to perform better than these prior techniques. We, therefore, believe that MSAID is a solid and reliable method of choice, which is often (if not always) superior to other global alignment techniques.

Algorithms↗

Genome-wide detection of alternative splicing in expressed sequences using partial order multiple sequence alignment graphs.

We present a method for high-throughput alternative splicing detection in expressed sequence data. This method effectively copes with many of the problems inherent in making inferences about splicing and alternative splicing on the basis of EST sequences, which in addition to being fragmentary and full of sequencing errors, may also be chimeric, misoriented, or contaminated with genomic sequence. Our method, which relies both on the Partial Order Alignment (POA) program for constructing multiple sequence alignments, and its Heaviest Bundling function for generating consensus sequences, accounts for the real complexity of expressed sequence data by building and analyzing a single multiple sequence alignment containing all of the expressed sequences in a particular cluster aligned to genomic sequence. We illustrate application of this method to human UniGene Cluster Hs.1162, which contains expressed sequences from the human HLA-DMB gene. We have used this method to generate databases, published elsewhere, of splices and alternative splicing relationships for the human, mouse and rat genomes. We present statistics from these calculations, as well as the CPU time for running our method on expressed sequence clusters of varying size, to verify that it truly scales to complete genomes.

Alternative Splicing↗

Multiple sequence alignment with the Divide-and-Conquer method.

An improved algorithm for the simultaneous alignment of multiple protein and nucleic acid sequences, the Divide-and-Conquer Alignment procedure (DCA), is presented. The basic method described in Tönges,et al. (1996) (Tönges, U., Perrey, S.W., Stoye, J., Dress, A.W.M., 1996. A general method for fast multiple sequence alignment. Gene, 172, GC33-GC41) is generalized to align any number of sequences to work arbitrary (e.g. affine linear) gap penalty functions. Also, the practical efficiency of the method is improved so that families of more than 10 sequences can now be aligned simultaneously within a few seconds or minutes. After a brief description of the general method, we assess the time and memory requirements of our implementation of DCA. We present several examples showing that the program is able to deal with real-world alignment problems.

Algorithms↗

Singular value decomposition analysis of protein sequence alignment score data.

One of the standard tools for the analysis of data arranged in matrix form is singular value decomposition (SVD). Few applications to genomic data have been reported to date mainly for the analysis of gene expression microarray data. We review SVD properties, examine mathematical terms and assumptions implicit in the SVD formalism, and show that SVD can be applied to the analysis of matrices representing pairwise alignment scores between large sets of protein sequences. In particular, we illustrate SVD capabilities for data dimension reduction and for clustering protein sequences. A comparison is performed between SVD-generated clusters of proteins and annotation reported in the SWISS-PROT Database for a set of protein sequences forming the calycin superfamily, entailing all entries corresponding to the lipocalin, cytosolic fatty acid-binding protein, and avidin-streptavidin Prosite patterns.

Amino Acid Sequence↗

WebVar: A resource for the rapid estimation of relative site variability from multiple sequence alignments.

UNLABELLED: WebVar is an online resource that provides estimates of relative site variability from multiple alignments of homologous protein or nucleic acid sequences. WebVar provides a variety of graphic and textual representations of estimates, designed to assist in phylogenetic analysis. AVAILABILITY: The WebVar server is located at http://www.pesolelab.it/Tools/WebVar.html

Algorithms↗

Multiple sequence alignment with the Clustal series of programs.

The Clustal series of programs are widely used in molecular biology for the multiple alignment of both nucleic acid and protein sequences and for preparing phylogenetic trees. The popularity of the programs depends on a number of factors, including not only the accuracy of the results, but also the robustness, portability and user-friendliness of the programs. New features include NEXUS and FASTA format output, printing range numbers and faster tree calculation. Although, Clustal was originally developed to run on a local computer, numerous Web servers have been set up, notably at the EBI (European Bioinformatics Institute) (http://www.ebi.ac.uk/clustalw/).

Algorithms↗

Identification of potential ferric binding residues in the iron-binding protein of pathogenic Neisseria meningitidis through structure-based multiple sequence alignments.

The ferric iron-binding proteins of pathogenic Neisseria display structural and metal-binding properties characteristic of the transferrin family. In the absence of structural data for the ferric iron-binding proteins, spacial folding templates have been derived for the meningococcal protein from complete and partial structure-based multiple sequence alignments with structurally related proteins. The templates have been used to identify a number of potential iron-binding residues. These include four residues that are identical with the iron coordinating ligands of transferrin, but only two reside within equivalent structural elements.

Bacterial Outer Membrane Proteins↗

Gap costs for multiple sequence alignment.

Standard methods for aligning pairs of biological sequences charge for the most common mutations, which are substitutions, deletions and insertions. Because a single mutation may insert or delete several nucleotides, gap costs that are not directly proportional to gap length are usually the most effective. How to extend such gap costs to alignments of three or more sequences is not immediately obvious, and a variety of approaches have been taken. This paper argues that, since gap and substitution costs together specify optimal alignments, they should be defined using a common rationale. Specifically, a new definition of gap costs for multiple alignments is proposed and compared with previous ones. Since the new definition links a multiple alignment's cost to that of its pairwise projections, it allows knowledge gained about two-sequence alignments to bear on the multiple alignment problem. Also, such linkage is a key element of recent algorithms that have rendered practical the simultaneous alignment of as many as six sequences.

Animals↗

Direct RNA motif definition and identification from multiple sequence alignments using secondary structure profiles.

We present here a new approach to the problem of defining RNA signatures and finding their occurrences in sequence databases. The proposed method is based on "secondary structure profiles". An RNA sequence alignment with secondary structure information is used as an input. Two types of weight matrices/profiles are constructed from this alignment: single strands are represented by a classical lod-scores profile while helical regions are represented by an extended "helical profile" comprising 16 lod-scores per position, one for each of the 16 possible base-pairs. Database searches are then conducted using a simultaneous search for helical profiles and dynamic programming alignment of single strand profiles. The algorithm has been implemented into a new software, ERPIN, that performs both profile construction and database search. Applications are presented for several RNA motifs. The automated use of sequence information in both single-stranded and helical regions yields better sensitivity/specificity ratios than descriptor-based programs. Furthermore, since the translation of alignments into profiles is straightforward with ERPIN, iterative searches can easily be conducted to enrich collections of homologous RNAs.

Algorithms↗

Making sense of score statistics for sequence alignments.

The search for similarity between two biological sequences lies at the core of many applications in bioinformatics. This paper aims to highlight a few of the principles that should be kept in mind when evaluating the statistical significance of alignments between sequences. The extreme value distribution is first introduced, which in most cases describes the distribution of alignment scores between a query and a database. The effects of the similarity matrix and gap penalty values on the score distribution are then examined, and it is shown that the alignment statistics can undergo an abrupt phase transition. A few types of random sequence databases used in the estimation of statistical significance are presented, and the statistics employed by the BLAST, FASTA and PRSS programs are compared. Finally the different strategies used to assess the statistical significance of the matches produced by profiles and hidden Markov models are presented.

Amino Acid Sequence↗

Exploring the propensities of helices in PrP(C) to form beta sheet using NMR structures and sequence alignments.

Neurodegenerative diseases induced by transmissible spongiform encephalopathies are associated with prions. The most spectacular event in the formation of the infectious scrapie form, referred to as PrP(Sc), is the conformational change from the predominantly alpha-helical conformation of PrP(C) to the PrP(Sc) state that is rich in beta-sheet content. Using sequence alignments and structural analysis of the available nuclear magnetic resonance structures of PrP(C), we explore the propensities of helices in PrP(C) to be in a beta-strand conformation. Comparison of a number of structural characteristics (such as solvent accessible area, distribution of (Phi, Psi) angles, mismatches in hydrogen bonds, nature of residues in local and nonlocal contacts, distribution of regular densities of amino acids, clustering of hydrophobic and hydrophilic residues in helices) between PrP(C) structures and a databank of "normal" proteins shows that the most unusual features are found in helix 2 (H2) (residues 172-194) followed by helix 1 (H1) (residues 144-153). In particular, the C-terminal residues in H2 are frustrated in their helical state. The databank of normal proteins consists of 58 helical proteins, 36 alpha+beta proteins, and 31 beta-sheet proteins. Our conclusions are also substantiated by gapless threading calculations that show that the normalized Z-scores of prion proteins are similar to those of other alpha+beta proteins with low helical content. Application of the recently introduced notion of discordance, namely, incompatibility of the predicted and observed secondary structures, also points to the frustration of H2 not only in the wild type but also in mutants of human PrP(C). This suggests that the instability of PrP(C) proteins may play a role in their being susceptible to the profound conformational change. Our analysis shows that, in addition to the previously proposed role for the segment (90-120) and possibly H1, the C-terminus of H2 and possibly N-terminus may play a role in the alpha-->beta transition. An implication of our results is that the ease of polymerization depends on the unfolding rate of the monomer. Sequence alignments show that helices in avian prion proteins (chicken, duck, crane) are better accommodated in a helical state, which might explain the absence of PrP(Sc) formation over finite time scales in these species. From this analysis, we predict that correlated mutations that reduce the frustration in the second half of helix 2 in mammalian prion proteins could inhibit the formation of PrP(Sc).

Amino Acid Sequence↗

M-Coffee: combining multiple sequence alignment methods with T-Coffee.

We introduce M-Coffee, a meta-method for assembling multiple sequence alignments (MSA) by combining the output of several individual methods into one single MSA. M-Coffee is an extension of T-Coffee and uses consistency to estimate a consensus alignment. We show that the procedure is robust to variations in the choice of constituent methods and reasonably tolerant to duplicate MSAs. We also show that performances can be improved by carefully selecting the constituent methods. M-Coffee outperforms all the individual methods on three major reference datasets: HOMSTRAD, Prefab and Balibase. We also show that on a case-by-case basis, M-Coffee is twice as likely to deliver the best alignment than any individual method. Given a collection of pre-computed MSAs, M-Coffee has similar CPU requirements to the original T-Coffee. M-Coffee is a freeware open-source package available from http://www.tcoffee.org/.

Algorithms↗

Statistical significance of probabilistic sequence alignment and related local hidden Markov models.

The score statistics of probabilistic gapped local alignment of random sequences is investigated both analytically and numerically. The full probabilistic algorithm (e.g., the "local" version of maximum-likelihood or hidden Markov model method) is found to have anomalous statistics. A modified "semi-probabilistic" alignment consisting of a hybrid of Smith-Waterman and probabilistic alignment is then proposed and studied in detail. It is predicted that the score statistics of the hybrid algorithm is of the Gumbel universal form, with the key Gumbel parameter lambda taking on a fixed asymptotic value for a wide variety of scoring systems and parameters. A simple recipe for the computation of the "relative entropy," and from it the finite size correction to lambda, is also given. These predictions compare well with direct numerical simulations for sequences of lengths between 100 and 1,000 examined using various PAM substitution scores and affine gap functions. The sensitivity of the hybrid method in the detection of sequence homology is also studied using correlated sequences generated from toy mutation models. It is found to be comparable to that of the Smith-Waterman alignment and significantly better than the Viterbi version of the probabilistic alignment.

Algorithms↗

Fold assembly of small proteins using monte carlo simulations driven by restraints derived from multiple sequence alignments.

The feasibility of predicting the global fold of small proteins by incorporating predicted secondary and tertiary restraints into ab initio folding simulations has been demonstrated on a test set comprised of 20 non-homologous proteins, of which one was a blind prediction of target 42 in the recent CASP2 contest. These proteins contain from 37 to 100 residues and represent all secondary structural classes and a representative variety of global topologies. Secondary structure restraints are provided by the PHD secondary structure prediction algorithm that incorporates multiple sequence information. Predicted tertiary restraints are derived from multiple sequence alignments via a two-step process. First, seed side-chain contacts are identified from correlated mutation analysis, and then a threading-based algorithm is used to expand the number of these seed contacts. A lattice-based reduced protein model and a folding algorithm designed to incorporate these predicted restraints is described. Depending upon fold complexity, it is possible to assemble native-like topologies whose coordinate root-mean-square deviation from native is between 3.0 A and 6.5 A. The requisite level of accuracy in side-chain contact map prediction can be roughly 25% on average, provided that about 60% of the contact predictions are correct within +/-1 residue and 95% of the predictions are correct within +/-4 residues. Precision in tertiary contact prediction is more critical than absolute accuracy. Furthermore, only a subset of the tertiary contacts, on the order of 25% of the total, is sufficient for successful topology assembly. Overall, this study suggests that the use of restraints derived from multiple sequence alignments combined with a fold assembly algorithm holds considerable promise for the prediction of the global topology of small proteins.

Amino Acid Sequence↗