Matching Sequences under Deletion/Insertion Constraints
AUTOR(ES)
Sankoff, David
RESUMO
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.
ACESSO AO ARTIGO
http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=427531Documentos Relacionados
- A deletion/insertion polymorphism in the human BCR gene on chromosome 22.
- Hereditary hepatic and systemic amyloidosis caused by a new deletion/insertion mutation in the apolipoprotein AI gene.
- Spontaneous deletion of citrate-utilizing ability promoted by insertion sequences.
- Genetic instability in Drosophila melanogaster: deletion induction by insertion sequences.
- Insertion and/or deletion of many repeated DNA sequences in human and higher ape evolution.