A graph-based clustering method applied to protein sequences

The number of amino acid sequences is increasing very rapidly in the protein databases like Swiss-Prot, Uniprot, PIR and others, but the structure of only some amino acid sequences are found in the Protein Data Bank. Thus, an important problem in genomics is automatically clustering homologous protein sequences when only sequence information is available. Here, we use graph theoretic techniques for clustering amino acid sequences. A similarity graph is defined and clusters in that graph correspond to connected subgraphs. Cluster analysis seeks grouping of amino acid sequences into subsets based on distance or similarity score between pairs of sequences. Our goal is to find disjoint subsets, called clusters, such that two criteria are satisfied: homogeneity: sequences in the same cluster are highly similar to each other; and separation: sequences in different clusters have low similarity to each other. We tested our method on several subsets of SCOP (Structural Classification of proteins) database, a gold standard for protein structure classification. The results show that for a given set of proteins the number of clusters we obtained is close to the superfamilies in that set; there are fewer singeltons; and the method correctly groups most remote homologs.     

A method to recognize distant repeats in protein sequences

An automated algorithm is presented that delineates protein sequence fragments which display similarity. The method incorporates a selection of a number of local nonoverlapping sequence alignments with the highest similarity scores and a graphtheoretical approach to elucidate the consistent start and end points of the fragments comprising one or more ensembles of related subsequences. The procedure allows the simultaneous identification of different types of repeats within one sequence. A multiple alignment of the resulting fragments is performed and a consensus sequence derived from the ensemble(s). Finally, a profile is constructed form the multiple alignment to detect possible and more distant members within the sequence. The method tolerates mutations in the repeats as well as insertions and deletions. The sequence spans between the various repeats or repeat clusters may be of different lengths. The technique has been applied to a number of proteins where the repeating fragments have been derived from information additional to the protein sequences. © 1993 Wiley-Liss, Inc.     

Extraction of symbolic determinants common to a family of biological sequences

A set of sequences can be defined by their common subsequences, and the length of these is a measure of the overall resemblance of the set. Each subsequence corresponds to a succession of symbols embedded in every sequence, following the same order but not necessarily contiguous. Determining the longest common subsequence (LCS) requires the exhaustive testing of all possible common subsequences, which sum up to about 2L, if L is the length of the shortest sequence. We present a polynomial algorithm (O(n X L4), where n is the number of sequences) for generating strings related to the LCS and constructed with the sequence alphabet and an indetermination symbol. Such strings are iteratively improved by deleting indetermination symbols and concomitantly introducing the greatest number of alphabet symbols. Processed accordingly, nucleic acid and protein sequences lead to key-words encompassing the salient positions of homologous chains, which can be used for aligning or classifying them, as well as for finding related sequences in data banks.     

A new method for quantifying residue conservation and its applications to the protein folding nucleus

The conservation of residues in columns of a multiple sequence alignment (MSA) reflects the importance of these residues for maintaining the structure and function of a protein. To date, many scores have been suggested for quantifying residue conservation, but none has achieved the full rigor both in biology and statistics. In this paper, we present a new approach for measuring the evolutionary conservation at aligned positions. Our conservation measure is related to the logarithmic probabilities for aligned positions, and combines the physicochemical properties and the frequencies of amino acids. Such a measure is both biologically and statistically meaningful. For testing the relationship between an amino acid's evolutionary conservation and its role in the Phi-value defined protein folding kinetics, our results indicate that the folding nucleus residues may not be significantly more conserved than other residues by using the biological-relevance weighted statistical scoring method suggested in this paper as an alternative to entropy-based procedures.     

CLAGen: a tool for clustering and annotating gene sequences using a suffix tree algorithm

Most multiple gene sequence alignment methods rely on conventions regarding the score of a multiple alignment in pairwise fashion. Therefore, as the number of sequences increases, the runtime of sequencing expands exponentially. In order to solve the problem, this paper presents a multiple sequence alignment method using a linear-time suffix tree algorithm to cluster similar sequences at one time without pairwise alignment. After searching for common subsequences, cross-matching common subsequences were generated, and sometimes inexact matching was found. So, a procedure aimed at masking the inexact cross-matching pairs was suggested here. In addition, BLAST was combined with a clustering tool in order to annotate the clusters generated by suffix tree clustering. The proposed method for clustering and annotating genes consists of the following steps: (1) construction of a suffix tree; (2) searching and overlapping common subsequences; (3) grouping subsequence pairs; (4) masking cross-matching pairs; (5) clustering gene sequences; (6) annotating gene clusters by the BLAST search. The performance of the proposed system, CLAGen, was successfully evaluated with 42 gene sequences in a TCA cycle (a citrate cycle) of bacteria. The system generated 11 clusters and found the longest subsequences of each cluster, which are biologically significant.     

The posterior probability distribution of alignments and its application to parameter estimation of evolutionary trees and to optimization of multiple alignments

How to sample alignments from their posterior probability distribution given two strings is shown. This is extended to sampling alignments of more than two strings. The result is first applied to the estimation of the edges of a given evolutionary tree over several strings. Second, when used in conjunction with simulated annealing, it gives a stochastic search method for an optimal multiple alignment.Correspondence to: L. Allison     

From analysis of protein structural alignments toward a novel approach to align protein sequences

Alignment of protein sequences is a key step in most computational methods for prediction of protein function and homology-based modeling of three-dimensional (3D)-structure. We investigated correspondence between "gold standard" alignments of 3D protein structures and the sequence alignments produced by the Smith-Waterman algorithm, currently the most sensitive method for pair-wise alignment of sequences. The results of this analysis enabled development of a novel method to align a pair of protein sequences. The comparison of the Smith-Waterman and structure alignments focused on their inner structure and especially on the continuous ungapped alignment segments, "islands" between gaps. Approximately one third of the islands in the gold standard alignments have negative or low positive score, and their recognition is below the sensitivity limit of the Smith-Waterman algorithm. From the alignment accuracy perspective, the time spent by the algorithm while working in these unalignable regions is unnecessary. We considered features of the standard similarity scoring function responsible for this phenomenon and suggested an alternative hierarchical algorithm, which explicitly addresses high scoring regions. This algorithm is considerably faster than the Smith-Waterman algorithm, whereas resulting alignments are in average of the same quality with respect to the gold standard. This finding shows that the decrease of alignment accuracy is not necessarily a price for the computational efficiency.     

New method for global alignment of 2 DNA sequences by the tree data structure

We introduce a new approach to investigate problem of DNA sequence alignment. The method consists of three parts: (i) simple alignment algorithm, (ii) extension algorithm for largest common substring, (iii) graphical simple alignment tree (GSA tree). The approach firstly obtains a graphical representation of scores of DNA sequences by the scoring equation R₀*R−S₀*S−T₀*(a+bk). Then a GSA tree is constructed to facilitate solving the problem for global alignment of 2 DNA sequences. Finally we give several practical examples to illustrate the utility and practicality of the approach.     

A systematic search for protein signature sequences.

Signature sequences are contiguous patterns of amino acids 10-50 residues long that are associated with a particular structure or function in proteins. These may be of three types (by our nomenclature): superfamily signatures, remnant homologies, and motifs. We have performed a systematic search through a database of protein sequences to automatically and preferentially find remnant homologies and motifs. This was accomplished in three steps: 1. We generated a nonredundant sequence database. 2. We used BLAST3 (Altschul and Lipman, Proc. Natl. Acad. Sci. U.S.A. 87:5509-5513, 1990) to generate local pairwise and triplet sequence alignments for every protein in the database vs. every other. 3. We selected "interesting" alignments and grouped them into clusters. We find that most of the clusters contain segments from proteins which share a common structure or function. Many of them correspond to signatures previously noted in the literature. We discuss three previously recognized motifs in detail (FAD/NAD-binding, ATP/GTP-binding, and cytochrome b5-like domains) to demonstrate how the alignments generated by our procedure are consistent with previous work and make structural and functional sense. We also discuss two signatures (for N-acetyltransferases and glycerol-phosphate binding) which to our knowledge have not been previously recognized.     

ProteoMix: an integrated and flexible system for interactively analyzing large numbers of protein sequences

ProteoMix is a suite of JAVA programs for identifying, annotating and predicting regions of interest in large sets of amino acid sequences, according to systematic and consistent criteria. It is based on two concepts (1) the integration of results from different sequence analysis tools increases the prediction reliability; and (2) the integration protocol is critical and needs to be easily adaptable in a case-by-case manner. ProteoMix was designed to analyze simultaneously multiple protein sequences using several bioinformatics tools, merge the results of the analyses using logical functions and display them on an integrated viewer. In addition, new sequences can be added seamlessly to an analysis performed on an initial set of sequences. ProteoMix has a modular design, and bioinformatics tools are run on remote servers accessed using the Internet Simple Object Access Protocol (SOAP), ensuring the swift implementation of additional tools. ProteoMix has a user-friendly interactive graphical user interface environment and runs on PCs with Microsoft OS. AVAILABILITY: ProteoMix is freely available for academic users at http://bio.gsc.riken.jp/ProteoMix/     

Automatic identification of large collections of protein-coding or rRNA sequences

The number of available genomic sequences is growing very fast, due to the development of massive sequencing techniques. Sequence identification is needed and contributes to the assessment of gene and species evolutionary relationships. Automated bioinformatics tools are thus necessary to carry out these identification operations in an accurate and fast way. We developed HoSeqI (Homologous Sequence Identification), a software environment allowing this kind of automated sequence identification using homologous gene family databases. HoSeqI is accessible through a Web interface (http://pbil.univ-lyon1.fr/software/HoSeqI/) allowing to identify one or several sequences and to visualize resulting alignments and phylogenetic trees. We also implemented another application, MultiHoSeqI, to quickly add a large set of sequences to a family database in order to identify them, to update the database, or to help automatic genome annotation. Lately, we developed an application, ChiSeqI (Chimeric Sequence Identification), to automate the processes of identification of bacterial 16S ribosomal RNA sequences and of detection of chimeric sequences.     

Bilateral similarity function: A novel and universal method for similarity analysis of biological sequences

Bilateral similarity function is designed for analyzing the similarities of biological sequences such as DNA, RNA secondary structure or protein in this paper. The defined function can perform comprehensive comparison between sequences remarkably well, both in terms of the Hamming distance of two compared sequences and the corresponding location difference. Compared with the existing methods for similarity analysis, the examination of similarities/dissimilarities illustrates that the proposed method with the computational complexity of O(N) is effective for these three kinds of biological sequences, and bears the universality for them.     

新型粒子群优化算法在多序列联配中的应用

将粒子群优化算法应用于序列联配,提出了一种改进的粒子群优化算法,该算法在粒子群的进化过程中根据粒子的适应值动态地调整粒子群的惯性权重与粒子群飞行速度范围,提高了算法的收敛速度和收敛精度;针对PSO算法可能出现的早熟现象,引入重新初始化机制,增强了算法的搜索能力,实验表明该算法是有效的。     

大数量序列的PCR保守引物设计实践

引物设计前的序列的全面检索,未注释序列的归类,经多序列比对求带有模糊碱基代码标识(IUPAC ambiguity codes)的共有序列,对设计高质量的引物至关重要,是引物设计过程的难点。目前,综合性核酸序列分析软件,单功能应用软件,在解决上述问题时均显不足。应用互联网提供的在线生物应用程序实践了一种多程序组合使用设计大数量序列的保守引物的方法,探讨了实现大数量序列的保守引物设计的一般流程。     

Aligning,analyzing, and visualizing sequences for antibody engineering: Automated recognition of immunoglobulin variable region features

The analysis and comparison of large numbers of immunoglobulin (Ig) sequences that arise during an antibody selection campaign can be time‐consuming and tedious. Typically, the identification and annotation of framework as well as complementarity‐determining regions (CDRs) is based on multiple sequence alignments using standardized numbering schemes, which allow identification of equivalent residues among different family members but often necessitate expert knowledge and manual intervention. Moreover, due to the enormous length variability of some CDRs the benefit of conventional Ig numbering schemes is limited and the calculation of correct sequence alignments can become challenging. Whereas, in principle, a well established set of rules permits the assignment of CDRs from the amino acid sequence alone, no currently available sequence alignment editor provides an algorithm to annotate new Ig sequences accordingly. Here we present a unique pattern matching method implemented into our recently developed ANTIC ALIgN editor that automatically identifies all hypervariable and framework regions in experimentally elucidated antibody sequences using so‐called “regular expressions.” By combination of this widely supported software syntax with the unique capabilities of real‐time aligning, editing and analyzing extended sets of amino acid and/or nucleotide sequences simultaneously on a local workstation, ANTIC ALIgN provides a powerful utility for antibody engineering. Proteins 2016; 85:65–71. © 2016 Wiley Periodicals, Inc.     

Systematic exploration of guide-tree topology effects for small protein alignments

Background

Guide-trees are used as part of an essential heuristic to enable the calculation of multiple sequence alignments. They have been the focus of much method development but there has been little effort at determining systematically, which guide-trees, if any, give the best alignments. Some guide-tree construction schemes are based on pair-wise distances amongst unaligned sequences. Others try to emulate an underlying evolutionary tree and involve various iteration methods.

Results

We explore all possible guide-trees for a set of protein alignments of up to eight sequences. We find that pairwise distance based default guide-trees sometimes outperform evolutionary guide-trees, as measured by structure derived reference alignments. However, default guide-trees fall way short of the optimum attainable scores. On average chained guide-trees perform better than balanced ones but are not better than default guide-trees for small alignments.

Conclusions

Alignment methods that use Consistency or hidden Markov models to make alignments are less susceptible to sub-optimal guide-trees than simpler methods, that basically use conventional sequence alignment between profiles. The latter appear to be affected positively by evolutionary based guide-trees for difficult alignments and negatively for easy alignments. One phylogeny aware alignment program can strongly discriminate between good and bad guide-trees. The results for randomly chained guide-trees improve with the number of sequences.

Electronic supplementary material

The online version of this article (doi:10.1186/1471-2105-15-338) contains supplementary material, which is available to authorized users.     

Predicting protein interaction sites from residue spatial sequence profile and evolution rate

This paper proposes a novel method that can predict protein interaction sites in heterocomplexes using residue spatial sequence profile and evolution rate approaches. The former represents the information of multiple sequence alignments while the latter corresponds to a residue's evolutionary conservation score based on a phylogenetic tree. Three predictors using a support vector machines algorithm are constructed to predict whether a surface residue is a part of a protein-protein interface. The efficiency and the effectiveness of our proposed approach is verified by its better prediction performance compared with other models. The study is based on a non-redundant data set of heterodimers consisting of 69 protein chains.     

Alignment of protein sequences by their profiles

The accuracy of an alignment between two protein sequences can be improved by including other detectably related sequences in the comparison. We optimize and benchmark such an approach that relies on aligning two multiple sequence alignments, each one including one of the two protein sequences. Thirteen different protocols for creating and comparing profiles corresponding to the multiple sequence alignments are implemented in the SALIGN command of MODELLER. A test set of 200 pairwise, structure-based alignments with sequence identities below 40% is used to benchmark the 13 protocols as well as a number of previously described sequence alignment methods, including heuristic pairwise sequence alignment by BLAST, pairwise sequence alignment by global dynamic programming with an affine gap penalty function by the ALIGN command of MODELLER, sequence-profile alignment by PSI-BLAST, Hidden Markov Model methods implemented in SAM and LOBSTER, pairwise sequence alignment relying on predicted local structure by SEA, and multiple sequence alignment by CLUSTALW and COMPASS. The alignment accuracies of the best new protocols were significantly better than those of the other tested methods. For example, the fraction of the correctly aligned residues relative to the structure-based alignment by the best protocol is 56%, which can be compared with the accuracies of 26%, 42%, 43%, 48%, 50%, 49%, 43%, and 43% for the other methods, respectively. The new method is currently applied to large-scale comparative protein structure modeling of all known sequences.     

Evolutionary analysis of cytochrome b sequences in some perciformes: Evidence for a slower rate of evolution than in mammals

To obtain information relative to the phylogenesis and microevolutionary rate of fish mitochondrial DNA, the nucleotide sequence of cytochrome b gene in seven fish species belonging to the order of Perciformes was determined. Sequence analysis showed that fish mitochondrial DNA has a nucleotide compositional bias similar to that of sharks but lower compared to mammals and birds. Quantitative evolutionary analysis, carried out by using a markovian stochastic model, clarifies some phylogenetic relationships within the Perciformes order, particularly in the Scombridae family, and between Perciformes, Gadiformes, Cypriniformes, and Acipenseriformes. The molecular clock of mitochondrial DNA was calibrated with the nucleotide substitution rate of cytochrome b gene in five shark species having divergence times inferred from paleontological estimates. The results of such analysis showed that Acipenseriformes diverged from Perciformes by about 200 MY, that the Perciformes common ancestor dates back to 150 MY, and that fish mitochondrial DNA has a nucleotide substitution rate three to five times lower than that of mammals.Correspondence to: C. SacconeThe nucleotide sequences reported in this paper have been submitted to the GenBank/EMBL Data Library with accession numbers X81562 (Sarda sarda), X81563 (Thunnus thynnus), X81564 (Scomber scombrus), X81565 (Oreochromis mossambicus), X81566 (Dicentrarchus labrax), X81567 (Boops hoops), X81568 (Trachurus trachurus)     

A simple and efficient method to determine the terminal sequences of restriction fragments containing known sequences.

We present an improvement of the inverse PCR method for the determination of end sequences of restriction fragments containing unknown DNA sequences flanked by known segments. In this approach, a short "bridge" DNA is inserted during the self-ligation step of the inverse PCR technique. This bridge DNA acts as primer annealing sites for amplification and subsequent direct sequencing. Successive PCR amplifications enable selective amplification of the unknown sequences from a complex mixture. Unlike previously described methods, our method does not require special materials, such as synthetic adapters or biotinylated primers that must be prepared each time to adapt the target. Furthermore, no complex steps such as dephosphorylation or purification are needed. Our method can save time and reduce the cost of cloning unknown sequences; it is ideal for routine, rapid gene walking. We applied this method to a GC-rich bacterial genome and succeeded in determining the end sequences of a 4.5-kb fragment.