Frameshift mutations in protein-coding DNA sequences produce a drastic change in the resulting protein sequence, which prevents classic protein alignment methods from revealing the proteins' common origin. Moreover, when a large number of substitutions are additionally involved in the divergence, the homology detection becomes difficult even at the DNA level. To cope with this situation, we propose a novel method to infer distant homology relations of two proteins, that accounts for frameshift and point mutations that may have affected the coding sequences. We design a dynamic programming alignment algorithm over memory-efficient graph representations of the complete set of putative DNA sequences of each protein, with the goal of determining the two putative DNA sequences which have the best scoring alignment under a powerful scoring system designed to reflect the most probable evolutionary process. This allows us to uncover evolutionary information that is not captured by traditional alignment methods, which is confirmed by biologically significant examples.
An interesting approach for handling frameshifts at the protein level was developed in @cite_9 . Several substitution matrices were designed for aligning amino acids encoded on different reading frames, based on nucleotide pair matches between respective codons. This idea has the advantage of being easy to use with any classic protein alignment tool. However, it lacks flexibility in gap positioning.
@cite_9
2082309149
Theproteinsequencedatabasewas analyzed for evidence that some distinct sequence families might be distantly related in evolution by changes in frame of translation. Sequences were compared using special amino acid substitution matrices for the alternate frames of translation. The statistical significance of alignment scores were computed in the true database and shuffled versions of the database that preserve any potential codon bias. The comparison of results from these two databases provides a very sensitive method for de- tecting remote relationships. We find a weak but measurable relatedness within the database as a whole, supporting the notion that some proteins may have evolved from others through changes in frame of translation. We also quantify residual ho- mology in the ordinary sense within a database of generally unrelated sequences. Proteins 1999;37: Single nucleotide polymorphism (SNP) studies and random mutagenesis projects identify amino acid substitutions in protein-coding regions. Each substitution has the potential to affect protein function. SIFT (Sorting Intolerant From Tolerant) is a program that predicts whether an amino acid substitution affects protein function so that users can prioritize substitutions for further study. We have shown that SIFT can distinguish between functionally neutral and deleterious amino acid changes in mutagenesis studies and on human polymorphisms. SIFT is available at http: blocks.fhcrc.org sift SIFT.html. Abstract A new algorithm for analysis of the homology and genetic semihomology in protein sequence is described. It assumes the close relation between the compared amino acids and their codons in related proteins. The algorithm is based on the network of the genetic relationship between amino acids and, thus differs from the commonly used statistical matrices. The results obtained by using this method are more comprehensive than used at present, and reflect the actual mechanism of protein differentiation and evolution. They concern: (1) location of homologous and semihomologous sites in compared proteins; (2) precise estimation of insertion deletion gaps in non-homologous fragments; (3) analysis of internal homology and semihomology; (4) precise location of domains in multidomain proteins; (5) estimation of genetic code of non-homologous fragments; (6) construction of genetic probes; (7) studies on differentiation processes among related proteins; (8) estimation of the degree of relationship among related proteins; (9) studies on the evolution mechanism within homologous protein families and (10) confirmation of actual relationship of sequences showing low degree of homology. Here we present a novel technique for the alignment of flexible proteins. The method does not require an a priori knowledge of the flexible hinge regions. The FlexProt algorithm simultaneously detects the hinge regions and aligns the rigid subparts of the molecules. Our technique is not sensitive to insertions and deletions. Numerous methods have been developed to solve rigid structural comparisons. Unlike FlexProt, all previously developed methods designed to solve the protein flexible alignment require an a priori knowledge of the hinge regions. The FlexProt method is based on 3-D pattern-matching algorithms combined with graph theoretic techniques. The algorithm is highly efficient. For example, it performs a structural comparison of a pair of proteins with 300 amino acids in about 7 s on a 400-MHz desktop PC. We provide experimental results obtained with this algorithm. First, we flexibly align pairs of proteins taken from the database of motions. These are extended by taking additional proteins from the same SCOP family. Next, we present some of the results obtained from exhaustive all-against-all flexible structural comparisons of 1329 SCOP family representatives. Our results include relatively high-scoring flexible structural alignments between the C-terminal merozoite surface protein vs. tissue factor; class II aminoacyl-tRNA synthase, histocompatibility antigen vs. neonatal FC receptor; tyrosine-protein kinase C-SRC vs. haematopoetic cell kinase (HCK); tyrosine-protein kinase C-SRC vs. titine protein (autoinhibited serine kinase domain); and tissue factor vs. hormone-binding protein. These are illustrated and discussed, showing the capabilities of this structural alignment algorithm, which allows un-predefined hinge-based motions. Proteins 2002;48:242–256. © 2002 Wiley-Liss, Inc.