Constrained sequence alignment

This paper presents a dynamic programming algorithm for aligning two sequences when the alignment is constrained to lie between two arbitrary boundary lines in the dynamic programming matrix. For affine gap penalties, the algorithm requires only O(F) computation time and O(M+N)space, where F is the...

Full description

Saved in:
Bibliographic Details
Published in:Bulletin of mathematical biology 1993-05, Vol.55 (3), p.503-524
Main Authors: Chao, K.M, Hardison, R.C, Miller, W
Format: Article
Language:English
Subjects:
Algorithms
Biological and medical sciences
Chloroplasts
computer techniques
Fundamental and applied biological sciences. Psychology
General aspects
Genome
Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects)
Nicotiana - genetics
nucleotide sequences
Plants - genetics
Plants, Toxic
Sequence Alignment
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a dynamic programming algorithm for aligning two sequences when the alignment is constrained to lie between two arbitrary boundary lines in the dynamic programming matrix. For affine gap penalties, the algorithm requires only O(F) computation time and O(M+N)space, where F is the area of the feasible region and M and N are the sequence lengths. The result extends to concave gap penalties, with somewhat increased time and space bounds.
ISSN:0092-8240
1522-9602
DOI:10.1007/BF02460648