An exhaustive tree-searching algorithm for high-resolution computer-assisted nucleotide sequence analysis

A new computer search strategy has been devised for high-resolutionnucleotide sequence analysis. The strategy differs from thoseused by earlier sequence analysing programs in that it is exhaustiveand capable of detecting all possible homologies and other typesof relationships between or within sequences irrespective ofthe pattern of matches and mismatches encountered. The implementationof this strategy into a working algorithm is described. Received on March 1, 1985; accepted on April 24, 1985     

Molecular evolution of a peptide GPCR ligand driven by artificial neural networks

Peptide ligands of G protein-coupled receptors constitute valuable natural lead structures for the development of highly selective drugs and high-affinity tools to probe ligand-receptor interaction. Currently, pharmacological and metabolic modification of natural peptides involves either an iterative trial-and-error process based on structure-activity relationships or screening of peptide libraries that contain many structural variants of the native molecule. Here, we present a novel neural network architecture for the improvement of metabolic stability without loss of bioactivity. In this approach the peptide sequence determines the topology of the neural network and each cell corresponds one-to-one to a single amino acid of the peptide chain. Using a training set, the learning algorithm calculated weights for each cell. The resulting network calculated the fitness function in a genetic algorithm to explore the virtual space of all possible peptides. The network training was based on gradient descent techniques which rely on the efficient calculation of the gradient by back-propagation. After three consecutive cycles of sequence design by the neural network, peptide synthesis and bioassay this new approach yielded a ligand with 70fold higher metabolic stability compared to the wild type peptide without loss of the subnanomolar activity in the biological assay. Combining specialized neural networks with an exploration of the combinatorial amino acid sequence space by genetic algorithms represents a novel rational strategy for peptide design and optimization.     

Analysis of the Secondary Structure of ITS1 in Pectinidae: Implications for Phylogenetic Reconstruction and Structural Evolution

It is at present difficult to accurately position gaps in sequence alignment and to determine substructural homology in structure alignment when reconstructing phylogenies based on highly divergent sequences. Therefore, we have developed a new strategy for inferring phylogenies based on highly divergent sequences. In this new strategy, the whole secondary structure presented as a string in bracket notation is used as phylogenetic characters to infer phylogenetic relationships. It is no longer necessary to decompose the secondary structure into homologous substructural components. In this study, reliable phylogenetic relationships of eight species in Pectinidae were inferred from the structure alignment, but not from sequence alignment, even with the aid of structural information. The results suggest that this new strategy should be useful for inferring phylogenetic relationships based on highly divergent sequences. Moreover, the structural evolution of ITS1 in Pectinidae was also investigated. The whole ITS1 structure could be divided into four structural domains. Compensatory changes were found in all four structural domains. Structural motifs in these domains were identified further. These motifs, especially those in D2 and D3, may have important functions in the maturation of rRNAs.     

Embedding strategies for effective use of information from multiple sequence alignments.

We describe a new strategy for utilizing multiple sequence alignment information to detect distant relationships in searches of sequence databases. A single sequence representing a protein family is enriched by replacing conserved regions with position-specific scoring matrices (PSSMs) or consensus residues derived from multiple alignments of family members. In comprehensive tests of these and other family representations, PSSM-embedded queries produced the best results overall when used with a special version of the Smith-Waterman searching algorithm. Moreover, embedding consensus residues instead of PSSMs improved performance with readily available single sequence query searching programs, such as BLAST and FASTA. Embedding PSSMs or consensus residues into a representative sequence improves searching performance by extracting multiple alignment information from motif regions while retaining single sequence information where alignment is uncertain.     

Recognizing very distant sequence relationships among proteins by family profile analysis.

Family profile analysis (FPA), described in this paper, compares all available homologous amino acid sequences of a target family with the profile of a probe family while conventional sequence profile analysis (Gribskov M, Lüthy R, Eisenberg D. Meth Enzymol 1990;183:146-159) considers only a single target sequence in comparison with the probe family. The increased input of sequence information in FPA expands the range for sequence-based recognition of structural relationships. In the FPA algorithm, Zscores of each of the target sequences, obtained from a probe profile search over all known amino acid sequences, are averaged and then compared with the scores for sequences of 100 reference families in the same probe family search. The resulting F-Zscore of the target family, expressed in "effective standard deviations" of the mean Zscores of the reference families, with value above a threshold of 3.5 indicates a statistically significant evolutionary relationship between the target and probe families. The sensitivity of FPA to sequence information was tested with several protein families where distant relationships have been verified from known tertiary protein architectures, which included vitamin B6-dependent enzymes, (beta/alpha)8-barrel proteins, beta-trefoil proteins, and globins. In comparison to other methods, FPA proved to be significantly more sensitive, finding numerous new homologies. The FPA technique is not only useful to test a suspected relationship between probe and target families but also identifies possible target families in profile searches over all known primary structures.     

A workbench for multiple alignment construction and analysis

Multiple sequence alignment can be a useful technique for studying molecular evolution, as well as for analyzing relationships between structure or function and primary sequence. We have developed for this purpose an interactive program, MACAW (Multiple Alignment Construction and Analysis Workbench), that allows the user to construct multiple alignments by locating, analyzing, editing, and combining "blocks" of aligned sequence segments. MACAW incorporates several novel features. (1) Regions of local similarity are located by a new search algorithm that avoids many of the limitations of previous techniques. (2) The statistical significance of blocks of similarity is evaluated using a recently developed mathematical theory. (3) Candidate blocks may be evaluated for potential inclusion in a multiple alignment using a variety of visualization tools. (4) A user interface permits each block to be edited by moving its boundaries or by eliminating particular segments, and blocks may be linked to form a composite multiple alignment. No completely automatic program is likely to deal effectively with all the complexities of the multiple alignment problem; by combining a powerful similarity search algorithm with flexible editing, analysis and display tools, MACAW allows the alignment strategy to be tailored to the problem at hand.     

一个新的多序列比对算法

多序列比对是生物信息学中基础而又重要的序列分析方法.本文提出一种新的多序列比对算法,该算法综合了渐进比对方法和迭代策略,采用加权函数以调整序列的有偏分布,用neighbor-joining方法构建指导树以确定渐进比对的顺序.通过对BAlibASE中142组蛋白质序列比对的测试,验证了本算法的有效性.与Multalin算法比较的结果表明,本算法能有效地提高分歧较大序列的比对准确率.     

Sigma: multiple alignment of weakly-conserved non-coding DNA sequence

Background  

Existing tools for multiple-sequence alignment focus on aligning protein sequence or protein-coding DNA sequence, and are often based on extensions to Needleman-Wunsch-like pairwise alignment methods. We introduce a new tool, Sigma, with a new algorithm and scoring scheme designed specifically for non-coding DNA sequence. This problem acquires importance with the increasing number of published sequences of closely-related species. In particular, studies of gene regulation seek to take advantage of comparative genomics, and recent algorithms for finding regulatory sites in phylogenetically-related intergenic sequence require alignment as a preprocessing step. Much can also be learned about evolution from intergenic DNA, which tends to evolve faster than coding DNA. Sigma uses a strategy of seeking the best possible gapless local alignments (a strategy earlier used by DiAlign), at each step making the best possible alignment consistent with existing alignments, and scores the significance of the alignment based on the lengths of the aligned fragments and a background model which may be supplied or estimated from an auxiliary file of intergenic DNA.     

GeneRAGE: a robust algorithm for sequence clustering and domain detection

MOTIVATION: Efficient, accurate and automatic clustering of large protein sequence datasets, such as complete proteomes, into families, according to sequence similarity. Detection and correction of false positive and negative relationships with subsequent detection and resolution of multi-domain proteins. RESULTS: A new algorithm for the automatic clustering of protein sequence datasets has been developed. This algorithm represents all similarity relationships within the dataset in a binary matrix. Removal of false positives is achieved through subsequent symmetrification of the matrix using a Smith-Waterman dynamic programming alignment algorithm. Detection of multi-domain protein families and further false positive relationships within the symmetrical matrix is achieved through iterative processing of matrix elements with successive rounds of Smith-Waterman dynamic programming alignments. Recursive single-linkage clustering of the corrected matrix allows efficient and accurate family representation for each protein in the dataset. Initial clusters containing multi-domain families, are split into their constituent clusters using the information obtained by the multi-domain detection step. This algorithm can hence quickly and accurately cluster large protein datasets into families. Problems due to the presence of multi-domain proteins are minimized, allowing more precise clustering information to be obtained automatically. AVAILABILITY: GeneRAGE (version 1.0) executable binaries for most platforms may be obtained from the authors on request. The system is available to academic users free of charge under license.     

A novel feature-based method for whole genome phylogenetic analysis without alignment: application to HEV genotyping and subtyping

Traditional phylogenetic analysis is based on multiple sequence alignment. With the development of worldwide genome sequencing project, more and more completely sequenced genomes become available. However, traditional sequence alignment tools are impossible to deal with large-scale genome sequence. So, the development of new algorithms to infer phylogenetic relationship without alignment from whole genome information represents a new direction of phylogenetic study in the post-genome era. In the present study, a novel algorithm based on BBC (base-base correlation) is proposed to analyze the phylogenetic relationships of HEV (Hepatitis E virus). When 48 HEV genome sequences are analyzed, the phylogenetic tree that is constructed based on BBC algorithm is well consistent with that of previous study. When compared with methods of sequence alignment, the merit of BBC algorithm appears to be more rapid in calculating evolutionary distances of whole genome sequence and not requires any human intervention, such as gene identification, parameter selection. BBC algorithm can serve as an alternative to rapidly construct phylogenetic trees and infer evolutionary relationships.     

The prediction of virus mutation using neural networks and rough set techniques

Viral evolution remains to be a main obstacle in the effectiveness of antiviral treatments. The ability to predict this evolution will help in the early detection of drug-resistant strains and will potentially facilitate the design of more efficient antiviral treatments. Various tools has been utilized in genome studies to achieve this goal. One of these tools is machine learning, which facilitates the study of structure-activity relationships, secondary and tertiary structure evolution prediction, and sequence error correction. This work proposes a novel machine learning technique for the prediction of the possible point mutations that appear on alignments of primary RNA sequence structure. It predicts the genotype of each nucleotide in the RNA sequence, and proves that a nucleotide in an RNA sequence changes based on the other nucleotides in the sequence. Neural networks technique is utilized in order to predict new strains, then a rough set theory based algorithm is introduced to extract these point mutation patterns. This algorithm is applied on a number of aligned RNA isolates time-series species of the Newcastle virus. Two different data sets from two sources are used in the validation of these techniques. The results show that the accuracy of this technique in predicting the nucleotides in the new generation is as high as 75 %. The mutation rules are visualized for the analysis of the correlation between different nucleotides in the same RNA sequence.     

Reconstruction of gene networks using Bayesian learning and manipulation experiments

MOTIVATION: The analysis of high-throughput experimental data, for example from microarray experiments, is currently seen as a promising way of finding regulatory relationships between genes. Bayesian networks have been suggested for learning gene regulatory networks from observational data. Not all causal relationships can be inferred from correlation data alone. Often several equivalent but different directed graphs explain the data equally well. Intervention experiments where genes are manipulated can help to narrow down the range of possible networks. RESULTS: We describe an active learning algorithm that suggests an optimized sequence of intervention experiments. Simulation experiments show that our selection scheme is better than an unguided choice of interventions in learning the correct network and compares favorably in running time and results with methods based on value of information calculations.     

A new distance measure for comparing sequence profiles based on path lengths along an entropy surface

We describe a new distance measure for comparing DNA sequence profiles. For this measure, columns in a multiple alignment are treated as character frequency vectors (sum of the frequencies equal to one). The distance between two vectors is based on minimum path length along an entropy surface. Path length is estimated using a random graph generated on the entropy surface and Dijkstra's algorithm for all shortest paths to a source. We use the new distance measure to analyze similarities within familes of tandem repeats in the C. elegans genome and show that this new measure gives more accurate refinement of family relationships than a method based on comparing consensus sequences.     

Improving genetic algorithms for protein folding simulations by systematic crossover

To improve protein folding simulations, we investigated a new search strategy in combination with the simple genetic algorithm on a two-dimensional lattice model. This search strategy, we called systematic crossover, couples the best individuals, tests every possible crossover point, and takes the two best individuals for the next generation. We compared the standard genetic algorithm with and without this new implementation for various chain lengths and showed that this strategy finds local minima with better energy values and is significantly faster in identifying the global minimum than the standard genetic algorithm.     

A study of a hierarchical structure of proteins and ligand binding sites of receptors using the triangular spatial relationship-based structure comparison method and development of a size-filtering feature designed for comparing different sizes of protein structures

The presence of receptors and the specific binding of the ligands determine nearly all cellular responses. Binding of a ligand to its receptor causes conformational changes of the receptor that triggers the subsequent signaling cascade. Therefore, systematically studying structures of receptors will provide insight into their functions. We have developed the triangular spatial relationship (TSR)-based method where all possible triangles are constructed with C_α atoms of a protein as vertices. Every triangle is represented by an integer denoted as a “key” computed through the TSR algorithm. A structure is thereby represented by a vector of integers. In this study, we have first defined substructures using different types of keys. Second, using different types of keys represents a new way to interpret structure hierarchical relations and differences between structures and sequences. Third, we demonstrate the effects of sequence similarity as well as sample size on the structure-based classifications. Fourth, we show identification of structure motifs, and the motifs containing multiple triangles connected by either an edge or a vertex are mapped to the ligand binding sites of the receptors. The structure motifs are valuable resources for the researchers in the field of signal transduction. Next, we propose amino-acid scoring matrices that capture “evolutionary closeness” information based on BLOSUM62 matrix, and present the development of a new visualization method where keys are organized according to evolutionary closeness and shown in a 2D image. This new visualization opens a window for developing tools with the aim of identification of specific and common substructures by scanning pixels and neighboring pixels. Finally, we report a new algorithm called as size filtering that is designed to improve structure comparison of large proteins with small proteins. Collectively, we provide an in-depth interpretation of structure relations through the detailed analyses of different types of keys and their associated key occurrence frequencies, geometries, and labels. In summary, we consider this study as a new computational platform where keys are served as a bridge to connect sequence and structure as well as structure and function for a deep understanding of sequence, structure, and function relationships of the protein family.     

A new sequence distance measure for phylogenetic tree construction

MOTIVATION: Most existing approaches for phylogenetic inference use multiple alignment of sequences and assume some sort of an evolutionary model. The multiple alignment strategy does not work for all types of data, e.g. whole genome phylogeny, and the evolutionary models may not always be correct. We propose a new sequence distance measure based on the relative information between the sequences using Lempel-Ziv complexity. The distance matrix thus obtained can be used to construct phylogenetic trees. RESULTS: The proposed approach does not require sequence alignment and is totally automatic. The algorithm has successfully constructed consistent phylogenies for real and simulated data sets. AVAILABILITY: Available on request from the authors.     

Simulating the Folding Pathway of RNA Secondary Structure Using the Modified Ant Colony Algorithm

<正> A new method for simulating the folding pathway of RNA secondary structure using the modified ant colony algorithmis proposed.For a given RNA sequence,the set of all possible stems is obtained and the energy of each stem iscalculated and stored at the initial stage.Furthermore,a more realistic formula is used to compute the energy ofmulti-branch loop in the following iteration.Then a folding pathway is simulated,including such processes as constructionof the heuristic information,the rule of initializing the pheromone,the mechanism of choosing the initial andnext stem and the strategy of updating the pheromone between two different stems.Finally by testing RNA sequences withknown secondary structures from the public databases,we analyze the experimental data to select appropriate values forparameters.The measure indexes show that our procedure is more consistent with phylogenetically proven structures thansoftware RNAstructure sometimes and more effective than the standard Genetic Algorithm.     

The relationship between n-gram patterns and protein secondary structure

An n-gram pattern (NP{n,m}) in a protein sequence is a set of n residues and m wildcards in a window of size n+m. Each window of n+m amino acids is associated with a collection of NP{n,m} patterns based on the combinatorics of n+m objects taken m at a time. NP{n,m} patterns that are shared between sequences reflect evolutionary relationships. Recently the authors developed an alignment-independent protein classification algorithm based on shared NP{4,2} patterns that compared favorably to PSI-BLAST. Theoretically, NP{4,2} patterns should also reflect secondary structure propensity since they contain all possible n-grams for 1 < or = n < or = 4 and a window of 6 residues is wide enough to capture periodicities in the 2 < or = n < or = 5 range. This sparked interest in differentiating the information content in NP{4,2} patterns related to evolution from the content related to local propensity. The probability of alpha-, beta-, and coil components was determined for every NP{4,2} pattern over all the chains in the Protein Data Bank (PDB). An algorithm exclusively based on the Z-values of these distributions was developed, which accurately predicted 71-76% of alpha-helical segments and 62-67% of beta-sheets in rigorous jackknife tests. This provided evidence for the strong correlation between NP{4,2} patterns and secondary structure. By grouping PDB chains into subsets with increasing levels of sequence identity, it was also possible to separate the evolutionary and local propensity contributions to the classification process. The results showed that information derived from evolutionary relationships was more important for beta-sheet prediction than alpha-helix prediction.