Abstract
Given two finite sequences, we wish to find the longest common subsequences satisfying certain deletion/insertion constraints. Consider two successive terms in the desired subsequence. The distance between their positions must be the same in the two original sequences for all but a limited number of such pairs of successive terms. Needleman and Wunsch gave an algorithm for finding longest common subsequences without constraints. This is improved from the viewpoint of computational economy. An economical algorithm is then elaborated for finding subsequences satisfying deletion/insertion constraints. This result is useful in the study of genetic homology based on nucleotide or amino-acid sequences.
Keywords: algorithm, genetic homology, nucleotide sequence, amino-acid sequence
Full text
PDF
Selected References
These references are in PubMed. This may not be the complete list of references from this article.
- Gibbs A. J., McIntyre G. A. The diagram, a method for comparing sequences. Its use with amino acid and nucleotide sequences. Eur J Biochem. 1970 Sep;16(1):1–11. doi: 10.1111/j.1432-1033.1970.tb01046.x. [DOI] [PubMed] [Google Scholar]
- Haber J. E., Koshland D. E., Jr An evaluation of the relatedness of proteins based on comparison of amino acid sequences. J Mol Biol. 1970 Jun 28;50(3):617–639. doi: 10.1016/0022-2836(70)90089-6. [DOI] [PubMed] [Google Scholar]
- Margoliash E., Fitch W. M., Dickerson R. E. Molecular expression of evolutinary phenomena in the primary and tertiary structures of cytochrome c. Brookhaven Symp Biol. 1968 Jun;21(2):259–305. [PubMed] [Google Scholar]
- Needleman S. B., Wunsch C. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970 Mar;48(3):443–453. doi: 10.1016/0022-2836(70)90057-4. [DOI] [PubMed] [Google Scholar]