完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Chung, Yun-Sheng | en_US |
dc.contributor.author | Lu, Chin Lung | en_US |
dc.contributor.author | Tang, Chuan Yi | en_US |
dc.date.accessioned | 2014-12-08T15:13:14Z | - |
dc.date.available | 2014-12-08T15:13:14Z | - |
dc.date.issued | 2007-11-01 | en_US |
dc.identifier.issn | 0166-218X | en_US |
dc.identifier.uri | http://dx.doi.org/10.1016/j.dam.2007.06.016 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/10212 | - |
dc.description.abstract | 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. | en_US |
dc.language.iso | en_US | en_US |
dc.subject | constrained sequence alignment | en_US |
dc.subject | nonapproximability | en_US |
dc.subject | NPO-completeness | en_US |
dc.title | Constrained sequence alignment: A general model and the hardness results | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1016/j.dam.2007.06.016 | en_US |
dc.identifier.journal | DISCRETE APPLIED MATHEMATICS | en_US |
dc.citation.volume | 155 | en_US |
dc.citation.issue | 18 | en_US |
dc.citation.spage | 2471 | en_US |
dc.citation.epage | 2486 | en_US |
dc.contributor.department | 生物科技學系 | zh_TW |
dc.contributor.department | Department of Biological Science and Technology | en_US |
dc.identifier.wosnumber | WOS:000251779100008 | - |
dc.citation.woscount | 0 | - |
顯示於類別: | 期刊論文 |