標題: Constrained sequence alignment: A general model and the hardness results
作者: Chung, Yun-Sheng
Lu, Chin Lung
Tang, Chuan Yi
生物科技學系
Department of Biological Science and Technology
關鍵字: constrained sequence alignment;nonapproximability;NPO-completeness
公開日期: 1-Nov-2007
摘要: Imposing constraints is a way to incorporate information into the sequence alignment procedure. In this paper, a general model for constrained alignment is proposed so that analyses admitted are more flexible and that different pattern definitions can be treated in a simple unified way. We give a polynomial time algorithm for pairwise constrained alignment for the generalized formulation, and prove the inapproximability of the problem when the number of sequences can be arbitrary. In addition, previous works deal only with the case that the patterns in the constraint have to occur in the output alignment in the same order as that specified by the input. It is of both theoretical and practical interest to investigate the case when the order is no longer limited. We show that the problem is not approximable even when the number of sequences is two. We also give the NPO-completeness results for the problems with bounds imposed on the objective function value. (c) 2007 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2007.06.016
http://hdl.handle.net/11536/10212
ISSN: 0166-218X
DOI: 10.1016/j.dam.2007.06.016
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 155
Issue: 18
起始頁: 2471
結束頁: 2486
Appears in Collections:Articles


Files in This Item:

  1. 000251779100008.pdf