doi: 10.1073/pnas.69.1.4.
Matching sequences under deletion-insertion constraints
- PMID: 4500555
- PMCID: PMC427531
- DOI: 10.1073/pnas.69.1.4
Item in Clipboard
Matching sequences under deletion-insertion constraints
Proc Natl Acad Sci U S A.
1972 Jan.
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.
Similar articles
-
Efficient Computation of Longest Common Subsequences with Multiple Substring Inclusive Constraints.J Comput Biol. 2019 Sep;26(9):938-947. doi: 10.1089/cmb.2019.0008. Epub 2019 Apr 8. J Comput Biol. 2019. PMID: 30958704
-
Pattern recognition in nucleic acid sequences. I. A general method for finding local homologies and symmetries.Nucleic Acids Res. 1982 Jan 11;10(1):247-63. doi: 10.1093/nar/10.1.247. Nucleic Acids Res. 1982. PMID: 6801626 Free PMC article.
-
Comparative biosequence metrics.J Mol Evol. 1981;18(1):38-46. doi: 10.1007/BF01733210. J Mol Evol. 1981. PMID: 7334527
-
New t-gap insertion-deletion-like metrics for DNA hybridization thermodynamic modeling.J Comput Biol. 2006 May;13(4):866-81. doi: 10.1089/cmb.2006.13.866. J Comput Biol. 2006. PMID: 16761916 Review.
-
Finding homologs to nucleic acid or protein sequences using the framesearch program.Curr Protoc Bioinformatics. 2002 Aug;Chapter 3:Unit 3.2. doi: 10.1002/0471250953.bi0302s00. Curr Protoc Bioinformatics. 2002. PMID: 18792937 Review.
Cited by
-
Exact global alignment using A* with chaining seed heuristic and match pruning.Bioinformatics. 2024 Mar 4;40(3):btae032. doi: 10.1093/bioinformatics/btae032. Bioinformatics. 2024. PMID: 38265119 Free PMC article.
-
A survey of multiple sequence comparison methods.Bull Math Biol. 1992 Jul;54(4):563-98. doi: 10.1007/BF02459635. Bull Math Biol. 1992. PMID: 1591533
-
Homologous inhibitors from potato tubers of serine endopeptidases and metallocarboxypeptidases.Proc Natl Acad Sci U S A. 1976 Jun;73(6):1941-4. doi: 10.1073/pnas.73.6.1941. Proc Natl Acad Sci U S A. 1976. PMID: 1064864 Free PMC article.
-
Model-driven engineering city spaces via bidirectional model transformations.Softw Syst Model. 2021;20(6):2003-2022. doi: 10.1007/s10270-020-00851-0. Epub 2021 Feb 16. Softw Syst Model. 2021. PMID: 34924920 Free PMC article.
-
Rapid similarity searches of nucleic acid and protein data banks.Proc Natl Acad Sci U S A. 1983 Feb;80(3):726-30. doi: 10.1073/pnas.80.3.726. Proc Natl Acad Sci U S A. 1983. PMID: 6572363 Free PMC article.
References
MeSH terms
LinkOut - more resources
Full Text Sources
Other Literature Sources
