Full metadata record
DC FieldValueLanguage
dc.contributor.authorChung, Yun-Shengen_US
dc.contributor.authorLu, Chin Lungen_US
dc.contributor.authorTang, Chuan Yien_US
dc.date.accessioned2014-12-08T15:13:14Z-
dc.date.available2014-12-08T15:13:14Z-
dc.date.issued2007-11-01en_US
dc.identifier.issn0166-218Xen_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.dam.2007.06.016en_US
dc.identifier.urihttp://hdl.handle.net/11536/10212-
dc.description.abstractImposing 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.en_US
dc.language.isoen_USen_US
dc.subjectconstrained sequence alignmenten_US
dc.subjectnonapproximabilityen_US
dc.subjectNPO-completenessen_US
dc.titleConstrained sequence alignment: A general model and the hardness resultsen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/j.dam.2007.06.016en_US
dc.identifier.journalDISCRETE APPLIED MATHEMATICSen_US
dc.citation.volume155en_US
dc.citation.issue18en_US
dc.citation.spage2471en_US
dc.citation.epage2486en_US
dc.contributor.department生物科技學系zh_TW
dc.contributor.departmentDepartment of Biological Science and Technologyen_US
dc.identifier.wosnumberWOS:000251779100008-
dc.citation.woscount0-
Appears in Collections:Articles


Files in This Item:

  1. 000251779100008.pdf