Paper Info
Title
Constrained sequence alignment: A general model and the hardness results
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.
Year
DOI
Venue
2007
10.1016/j.dam.2007.06.016
Discrete Applied Mathematics
Keywords
Field
DocType
objective function value,general model,hardness result,sequence alignment procedure,generalized formulation,different pattern definition,polynomial time algorithm,previous work,practical interest,output alignment,npo-completeness result,sequence alignment,objective function
Sequence alignment,Discrete mathematics,Pairwise comparison,Combinatorics,Algorithm,Time complexity,Completeness (statistics),Mathematics
Journal
Volume
Issue
ISSN
155
18
Discrete Applied Mathematics
Citations 
PageRank 
References 
0
0.34
11
Authors
3
Name
Order
Citations
PageRank
Yun-Sheng Chung1201.84
Chin Lung Lu242334.59
Chuan Yi Tang370479.25