Constrained sequence alignment |
| |
| Authors: | Kun-Mao Chao Ross C Hardison Webb Miller |
| |
| Institution: | (1) Department of Computer Science, The Pennsylvania State University, 16802 University Park, PA, U.S.A.;(2) Department of Molecular and Cell Biology, The Pennsylvania State University, 16802 University Park, PA, U.S.A.;(3) Institute for Molecular Evolutionary Genetics, The Pennsylvania State University, 16802 University Park, PA, U.S.A. |
| |
| Abstract: | 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 onlyO(F) computation time andO(M+N) space, whereF is the area of the feasible region andM andN are the sequence lengths. The result extends to concave gap penalties, with somewhat increased time and space bounds.
K.-M. C. and W. M. were supported in part by grant R01 LM05110 from the National Library of Medicine. R. C. H. was supported
by PHS grant R01 DK27635. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
