Aligning coding sequences with frameshift extension penalties

Background

Frameshift translation is an important phenomenon that contributes to the appearance of novel coding DNA sequences (CDS) and functions in gene evolution, by allowing alternative amino acid translations of gene coding regions. Frameshift translations can be identified by aligning two CDS, from a same gene or from homologous genes, while accounting for their codon structure. Two main classes of algorithms have been proposed to solve the problem of aligning CDS, either by amino acid sequence alignment back-translation, or by simultaneously accounting for the nucleotide and amino acid levels. The former does not allow to account for frameshift translations and up to now, the latter exclusively accounts for frameshift translation initiation, not considering the length of the translation disruption caused by a frameshift.

Results

We introduce a new scoring scheme with an algorithm for the pairwise alignment of CDS accounting for frameshift translation initiation and length, while simultaneously considering nucleotide and amino acid sequences. The main specificity of the scoring scheme is the introduction of a penalty cost accounting for frameshift extension length to compute an adequate similarity score for a CDS alignment. The second specificity of the model is that the search space of the problem solved is the set of all feasible alignments between two CDS. Previous approaches have considered restricted search space or additional constraints on the decomposition of an alignment into length-3 sub-alignments. The algorithm described in this paper has the same asymptotic time complexity as the classical Needleman–Wunsch algorithm.

Conclusions

We compare the method to other CDS alignment methods based on an application to the comparison of pairs of CDS from homologous human, mouse and cow genes of ten mammalian gene families from the Ensembl-Compara database. The results show that our method is particularly robust to parameter changes as compared to existing methods. It also appears to be a good compromise, performing well both in the presence and absence of frameshift translations. An implementation of the method is available at https://github.com/UdeS-CoBIUS/FsePSA.

     

A non-local gap-penalty for profile alignment

The length of an alignment of biological sequences is typically longer than the mean length of its component sequences. (This arises from the insertion of gaps in the alignment.) When such an alignment is used as a profile for the alignment of further sequences (or profiles), it will have a bias toward additional sequences that match the length of the profile, rather than the mean length of sequences in the profile, as the alignment of these well entail fewer (or smaller) insertions) so avoiding gap-penalties). An algorithm is described to correct this bias that entails monitoring the correspondence, for every pair of positions, of the mean separations in both profiles as they are aligned. The correction was incorporated into a standard dynamic programming algorithm through a modification of the gap-penalty, but, unlike other approaches, this modification is not local and takes into consideration the overall alignment of the sequences. This implies that the algorithm cannot guarantee to find the optimal alignment, but tests suggest that close approximations are obtained. The method was tested on protein families by measuring the area in the parameter space of the phase containing the correct multiple alignment. No improvement (increase in phase area) was found with a family that required few gaps to be aligned correctly. However, for highly gapped alignments, a 50% increase in area was obtained with one family and the correct alignment was found for another that could not be aligned with the unbiased method.     

Sequence alignment with an appropriate substitution matrix.

A widely used algorithm for computing an optimal local alignment between two sequences requires a parameter set with a substitution matrix and gap penalties. It is recognized that a proper parameter set should be selected to suit the level of conservation between sequences. We describe an algorithm for selecting an appropriate substitution matrix at given gap penalties for computing an optimal local alignment between two sequences. In the algorithm, a substitution matrix that leads to the maximum alignment similarity score is selected among substitution matrices at various evolutionary distances. The evolutionary distance of the selected substitution matrix is defined as the distance of the computed alignment. To show the effects of gap penalties on alignments and their distances and help select appropriate gap penalties, alignments and their distances are computed at various gap penalties. The algorithm has been implemented as a computer program named SimDist. The SimDist program was compared with an existing local alignment program named SIM for finding reciprocally best-matching pairs (RBPs) of sequences in each of 100 protein families, where RBPs are commonly used as an operational definition of orthologous sequences. SimDist produced more accurate results than SIM on 50 of the 100 families, whereas both programs produced the same results on the other 50 families. SimDist was also used to compare three types of substitution matrices in scoring 444,461 pairs of homologous sequences from the 100 families.     

Periodic distributions of hydrophobic amino acids allows the definition of fundamental building blocks to align distantly related proteins

Several studies on large and small families of proteins proved in a general manner that hydrophobic amino acids are globally conserved even if they are subjected to high rate substitution. Statistical analysis of amino acids evolution within blocks of hydrophobic amino acids detected in sequences suggests their usage as a basic structural pattern to align pairs of proteins of less than 25% sequence identity, with no need of knowing their 3D structure. The authors present a new global alignment method and an automatic tool for Proteins with HYdrophobic Blocks ALignment (PHYBAL) based on the combinatorics of overlapping hydrophobic blocks. Two substitution matrices modeling a different selective pressure inside and outside hydrophobic blocks are constructed, the Inside Hydrophobic Blocks Matrix and the Outside Hydrophobic Blocks Matrix, and a 4D space of gap values is explored. PHYBAL performance is evaluated against Needleman and Wunsch algorithm run with Blosum 30, Blosum 45, Blosum 62, Gonnet, HSDM, PAM250, Johnson and Remote Homo matrices. PHYBAL behavior is analyzed on eight randomly selected pairs of proteins of >30% sequence identity that cover a large spectrum of structural properties. It is also validated on two large datasets, the 127 pairs of the Domingues dataset with >30% sequence identity, and 181 pairs issued from BAliBASE 2.0 and ranked by percentage of identity from 7 to 25%. Results confirm the importance of considering substitution matrices modeling hydrophobic contexts and a 4D space of gap values in aligning distantly related proteins. Two new notions of local and global stability are defined to assess the robustness of an alignment algorithm and the accuracy of PHYBAL. A new notion, the SAD-coefficient, to assess the difficulty of structural alignment is also introduced. PHYBAL has been compared with Hydrophobic Cluster Analysis and HMMSUM methods.     

Edge lengths of trees from sequence data

Frequently there is a need to determine lengths associated with each edge of a phylogenetic tree, as these are often used as an indication of relative time intervals. Where this tree has been constructed from sequence data of r characters for n taxa, using the maximum parsimony model, an edge length can be determined from the differences between the inferred sequences of the end vertices of that edge. These inferred sequences are often not uniquely defined; a range of possible sequences are possible at a given internal vertex. In this paper we introduce an efficient [O(r×n)] algorithm which calculates the range of lengths on any edge over all the minimal labelings and significantly reduces the number of potential cases to be considered to obtain an objective measure of edge length.     

Optimal alignment between groups of sequences and its application to multiple sequence alignment

Four algorithms, A–D, were developed to align two groupsof biological sequences. Algorithm A is equivalent to the conventionaldynamic programming method widely used for aligning ordinarysequences, whereas algorithms B – D are designed to evaluatethe cost for a deletion/insertion more accurately when internalgaps are present in either or both groups of sequences. Rigorousoptimization of the ‘sum of pairs’ (SP) score isachieved by algorithm D, whose average performance is closeto O(MNL²) where M and N are numbers of sequences included inthe two groups and L is the mean length of the sequences. AlgorithmB uses some app mximations to cope with profile-based operations,whereas algorithm C is a simpler variant of algorithm D. Thesegroup-to-group alignment algorithms were applied to multiplesequence alignment with two iterative strategies: a progressivemethod based on a given binary tree and a randomized grouping-realignmentmethod. The advantages and disadvantages of the four algorithmsare discussed on the basis of the results of exatninations ofseveral protein families.     

Fast, optimal alignment of three sequences using linear gap costs

Alignment algorithms can be used to infer a relationship between sequences when the true relationship is unknown. Simple alignment algorithms use a cost function that gives a fixed cost to each possible point mutation-mismatch, deletion, insertion. These algorithms tend to find optimal alignments that have many small gaps. It is more biologically plausible to have fewer longer gaps rather than many small gaps in an alignment. To address this issue, linear gap cost algorithms are in common use for aligning biological sequence data. More reliable inferences are obtained by aligning more than two sequences at a time. The obvious dynamic programming algorithm for optimally aligning k sequences of length n runs in O(n(k)) time. This is impractical if k>/=3 and n is of any reasonable length. Thus, for this problem there are many heuristics for aligning k sequences, however, they are not guaranteed to find an optimal alignment. In this paper, we present a new algorithm guaranteed to find the optimal alignment for three sequences using linear gap costs. This gives the same results as the dynamic programming algorithm for three sequences, but typically does so much more quickly. It is particularly fast when the (three-way) edit distance is small. Our algorithm uses a speed-up technique based on Ukkonen's greedy algorithm (Ukkonen, 1983) which he presented for two sequences and simple costs.     

Grammar-based distance in progressive multiple sequence alignment

Background  

We propose a multiple sequence alignment (MSA) algorithm and compare the alignment-quality and execution-time of the proposed algorithm with that of existing algorithms. The proposed progressive alignment algorithm uses a grammar-based distance metric to determine the order in which biological sequences are to be pairwise aligned. The progressive alignment occurs via pairwise aligning new sequences with an ensemble of the sequences previously aligned.     

Accurate Simulation and Detection of Coevolution Signals in Multiple Sequence Alignments

Background

While the conserved positions of a multiple sequence alignment (MSA) are clearly of interest, non-conserved positions can also be important because, for example, destabilizing effects at one position can be compensated by stabilizing effects at another position. Different methods have been developed to recognize the evolutionary relationship between amino acid sites, and to disentangle functional/structural dependencies from historical/phylogenetic ones.

Methodology/Principal Findings

We have used two complementary approaches to test the efficacy of these methods. In the first approach, we have used a new program, MSAvolve, for the in silico evolution of MSAs, which records a detailed history of all covarying positions, and builds a global coevolution matrix as the accumulated sum of individual matrices for the positions forced to co-vary, the recombinant coevolution, and the stochastic coevolution. We have simulated over 1600 MSAs for 8 protein families, which reflect sequences of different sizes and proteins with widely different functions. The calculated coevolution matrices were compared with the coevolution matrices obtained for the same evolved MSAs with different coevolution detection methods. In a second approach we have evaluated the capacity of the different methods to predict close contacts in the representative X-ray structures of an additional 150 protein families using only experimental MSAs.

Conclusions/Significance

Methods based on the identification of global correlations between pairs were found to be generally superior to methods based only on local correlations in their capacity to identify coevolving residues using either simulated or experimental MSAs. However, the significant variability in the performance of different methods with different proteins suggests that the simulation of MSAs that replicate the statistical properties of the experimental MSA can be a valuable tool to identify the coevolution detection method that is most effective in each case.     

Dynamic use of multiple parameter sets in sequence alignment

The level of conservation between two homologous sequences often varies among sequence regions; functionally important domains are more conserved than the remaining regions. Thus, multiple parameter sets should be used in alignment of homologous sequences with a stringent parameter set for highly conserved regions and a moderate parameter set for weakly conserved regions. We describe an alignment algorithm to allow dynamic use of multiple parameter sets with different levels of stringency in computation of an optimal alignment of two sequences. The algorithm dynamically considers various candidate alignments, partitions each candidate alignment into sections, and determines the most appropriate set of parameter values for each section of the alignment. The algorithm and its local alignment version are implemented in a computer program named GAP4. The local alignment algorithm in GAP4, that in its predecessor GAP3, and an ordinary local alignment program SIM were evaluated on 257716 pairs of homologous sequences from 100 protein families. On 168475 of the 257716 pairs (a rate of 65.4%), alignments from GAP4 were more statistically significant than alignments from GAP3 and SIM.     

Automatic generation and evaluation of sparse protein signatures for families of protein structural domains

We identified key residues from the structural alignment of families of protein domains from SCOP which we represented in the form of sparse protein signatures. A signature-generating algorithm (SigGen) was developed and used to automatically identify key residues based on several structural and sequence-based criteria. The capacity of the signatures to detect related sequences from the SWISSPROT database was assessed by receiver operator characteristic (ROC) analysis and jack-knife testing. Test signatures for families from each of the main SCOP classes are described in relation to the quality of the structural alignments, the SigGen parameters used, and their diagnostic performance. We show that automatically generated signatures are potently diagnostic for their family (ROC50 scores typically >0.8), consistently outperform random signatures, and can identify sequence relationships in the "twilight zone" of protein sequence similarity (<40%). Signatures based on 15%-30% of alignment positions occurred most frequently among the best-performing signatures. When alignment quality is poor, sparser signatures perform better, whereas signatures generated from higher-quality alignments of fewer structures require more positions to be diagnostic. Our validation of signatures from the Globin family shows that when sequences from the structural alignment are removed and new signatures generated, the omitted sequences are still detected. The positions highlighted by the signature often correspond (alignment specificity >0.7) to the key positions in the original (non-jack-knifed) alignment. We discuss potential applications of sparse signatures in sequence annotation and homology modeling.     

Frequency of gaps observed in a structurally aligned protein pair database suggests a simple gap penalty function

Gap penalty is an important component of the scoring scheme that is needed when searching for homologous proteins and for accurate alignment of protein sequences. Most homology search and sequence alignment algorithms employ a heuristic ‘affine gap penalty’ scheme q + r × n, in which q is the penalty for opening a gap, r the penalty for extending it and n the gap length. In order to devise a more rational scoring scheme, we examined the pattern of gaps that occur in a database of structurally aligned protein domain pairs. We find that the logarithm of the frequency of gaps varies linearly with the length of the gap, but with a break at a gap of length 3, and is well approximated by two linear regression lines with R² values of 1.0 and 0.99. The bilinear behavior is retained when gaps are categorized by secondary structures of the two residues flanking the gap. Similar results were obtained when another, totally independent, structurally aligned protein pair database was used. These results suggest a modification of the affine gap penalty function.     

Local multiple alignment by consensus matrix

A new algorithm for aligning several sequences based on thecalculation of a consensus matrix and the comparison of allthe sequences using this consensus matrix is described. Thisconsensus matrix contains the preference scores of each nucleotideøaminoacid and gaps in every position of the alignment. Two modificationsof the algorithm corresponding to the evolutionary and functionalmeanings of the alignment were developed. The first one solvesthe best-fitting problem without any penalty for end gaps andwith an internal gap penalty function independent on the gaplength. This algorithm should be used when comparing evolutionary-relatedproteins for identifying the most conservative residues. Theother modification of the algorithm finds the most similar segmentsin the given sequences. It can be used for finding those partsof the sequences that are responsible for the same biologicalJunction. In this case the gap penalty function was chosen tobe proportional to the gap length. The result of aligning aminoacid sequences of neutral proteases and a compilation of 65allosteric effectors and substrates of PEP carboxylase are presented.     

Post-processing long pairwise alignments

MOTIVATION: The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments. RESULTS: We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.     

<Emphasis Type="Italic">Phylo-mLogo</Emphasis>: an interactive and hierarchical multiple-logo visualization tool for alignment of many sequences

Background  

When aligning several hundreds or thousands of sequences, such as epidemic virus sequences or homologous/orthologous sequences of some big gene families, to reconstruct the epidemiological history or their phylogenies, how to analyze and visualize the alignment results of many sequences has become a new challenge for computational biologists. Although there are several tools available for visualization of very long sequence alignments, few of them are applicable to the alignments of many sequences.     

On comparing two structured RNA multiple alignments

We present a method, called BlockMatch, for aligning two blocks, where a block is an RNA multiple sequence alignment with the consensus secondary structure of the alignment in Stockholm format. The method employs a quadratic-time dynamic programming algorithm for aligning columns and column pairs of the multiple alignments in the blocks. Unlike many other tools that can perform pairwise alignment of either single sequences or structures only, BlockMatch takes into account the characteristics of all the sequences in the blocks along with their consensus structures during the alignment process, thus being able to achieve a high-quality alignment result. We apply BlockMatch to phylogeny reconstruction on a set of 5S rRNA sequences taken from fifteen bacteria species. Experimental results showed that the phylogenetic tree generated by our method is more accurate than the tree constructed based on the widely used ClustalW tool. The BlockMatch algorithm is implemented into a web server, accessible at http://bioinformatics.njit.edu/blockmatch. A jar file of the program is also available for download from the web server.     

Pattern-induced multi-sequence alignment (PIMA) algorithm employing secondary structure-dependent gap penalties for use in comparative protein modelling.

A multiple sequence alignment algorithm is described that uses a dynamic programming-based pattern construction method to align a set of homologous sequences based on their common pattern of conserved sequence elements. This pattern-induced multi-sequence alignment (PIMA) algorithm can employ secondary-structure dependent gap penalties for use in comparative modelling of new sequences when the three-dimensional structure of one or more members of the same family is known. We show that the use of secondary structure information can significantly improve the accuracy of aligning structure boundaries in a set of homologous sequences even when the structure of only one member of the family is known.     

NTRS, a new family of highly repetitive DNAs specific for the T1 chromosome of tobacco

Species-specific repeated DNAs are important for identifying genomic components of hybrid organisms in plant breeding and in taxonomic studies, and we have previously described the HRS60 and GRS families of highly repetitive DNA sequences in tobacco. Here we describe a new family of highly repetitive DNA sequences termed NTRS (SspI family) that we have isolated from Nicotiana tomentosiformis (Goodspeed) and characterized and that is specific for the genomes of several species of the subgenus Tabacum. In situ hybridization showed that NTRS sequences are present in three pairs of chromosomes of N. tomentosiformis, six pairs of chromosomes of N. kawakamii, and only one pair of chromosomes of N. tabacum at an intercalary site. The NTRS family is not present in the N. otophora genome. The majority of NTRS sequences appeared to be organized in tandem arrays in which local DNA structures sensitive to single strand-specific chemical probes, potassium permanganate, and osmium tetroxide complexed with pyridine revealed a periodicity of 220 bp, equal to the length of the repeat unit. The inner cytosine in CCGG and CC(A/T)GG sequences of the NTRS family is frequently methylated. Cloned and sequenced NTRS monomeric units are 212–219 bp in length and show 83.5%–95% mutual homology. They exhibit properties characteristic for molecules that possess stable intrinsic curvature, but there are differences among individual monomers in the degree of curvature. NTRS sequences like HRS60 and GRS sequences, were found to specify nucleosome positions. Received: 12 November 1996 / in revised form: 12 May 1997 / Accepted: 12 May 1997     

Assessment of homology with the helical mimicry algorithm

Homologies based on structural motifs characterize conserved structures and mechanisms of maintaining function. An algorithm was developed to quantitate homology among segments of two proteins based upon structural characteristics of an amphipathic α-helix. This helical mimicry algorithm scored homology among sequences of two proteins in terms of: (i) presence of Leu, Ile, Val, Phe, or Met in a longitudinal, hydrophobic strip-of-helix at positions n, n + 4, n + 7, n + 11, etc. in the primary sequence, (ii) identity or chemical similarity of amino acids at intervening positions and (iii) exchanges of amino acids from positions n to n − 1, n + 3, n + 4, n + 1, n − 3, n − 4 around n (on the surface of a putative helix). While such exchanges of amino acids on the surfaces of homologous helices may conserve function, they did not maintain specific interactions of those residues with apposing groups.