Constrained sequence alignment

Kun Mao Chao, Ross C. Hardison, Webb Miller

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


This paper presents a dynamic programming algorithm for aligning two sequeces 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.

Original languageEnglish (US)
Pages (from-to)503-524
Number of pages22
JournalBulletin of Mathematical Biology
Issue number3
StatePublished - May 1993

All Science Journal Classification (ASJC) codes

  • General Neuroscience
  • Immunology
  • General Mathematics
  • General Biochemistry, Genetics and Molecular Biology
  • General Environmental Science
  • Pharmacology
  • General Agricultural and Biological Sciences
  • Computational Theory and Mathematics


Dive into the research topics of 'Constrained sequence alignment'. Together they form a unique fingerprint.

Cite this