text: 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.
  @cite_5: The non-statistical, non-Markovian model of protein mutational variability is described. There are presented the essential features of the algorithm of genetic semihomology and some examples of its application. The results of genetic semihomology approach are compared with the results obtained by using statistical algorithms and matrices which are assumed in widely used programs such as ClustalW, FASTA, MultAlin and BLAST. The aim of the new algorithm elaboration is to improve the accuracy of the results of protein sequence comparison, avoid the wrong assumptions and misinterpretation of the results, and increase the amount of information available from such study. © 2000 Elsevier Science Ireland Ltd. All rights reserved.
  @cite_4: 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.
summary: A non-statistical approach for analyzing the homology and the genetic semihomology'' in protein sequences was presented in @cite_4 @cite_5 . Instead of using a statistically computed scoring matrix, amino acid similarities are scored according to the complexity of the substitution process at the DNA level, depending on the number and type (transition transversion) of nucleotide changes that are necessary for replacing one amino acid by the other. This ensures a differentiated treatment of amino acid substitutions at different positions of the protein sequence, thus avoiding possible rough approximations resulting from scoring them equally, based on a classic scoring matrix. The main drawback of this approach is that it was not designed to cope with frameshift mutations..