TY - GEN

T1 - On the complexity of constrained sequences alignment problems

AU - Zhang, Yong

AU - CHAN, Joseph W T

AU - Chin, Francis Y.L.

AU - Ting, Hing Fung

AU - Ye, Deshi

AU - Zhang, Feng

AU - Shi, Jianyu

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2014

Y1 - 2014

N2 - We consider the problem of aligning a set of sequences subject to a given constrained sequence, which has applications in computational biology. In this paper we show that sequence alignment for two sequences A and B with a given distance function and a constrained sequence of k identical characters (say character c) can be solved in O( min {kn 2,(t - k)n 2}) time, where n is the length of A and B, and t is the minimum number of occurrences of character c in A and B. We also prove that the problem of constrained center-star sequence alignment (CCSA) is NP-hard even over the binary alphabet. Furthermore, for some distance function, we show that no polynomial-time algorithm can approximate the CCSA within any constant ratio.

AB - We consider the problem of aligning a set of sequences subject to a given constrained sequence, which has applications in computational biology. In this paper we show that sequence alignment for two sequences A and B with a given distance function and a constrained sequence of k identical characters (say character c) can be solved in O( min {kn 2,(t - k)n 2}) time, where n is the length of A and B, and t is the minimum number of occurrences of character c in A and B. We also prove that the problem of constrained center-star sequence alignment (CCSA) is NP-hard even over the binary alphabet. Furthermore, for some distance function, we show that no polynomial-time algorithm can approximate the CCSA within any constant ratio.

UR - http://www.scopus.com/inward/record.url?scp=84903603807&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08016-1_28

DO - 10.1007/978-3-319-08016-1_28

M3 - Conference contribution

AN - SCOPUS:84903603807

SN - 9783319080154

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 309

EP - 319

BT - Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings

PB - Springer Verlag

T2 - 8th International Frontiers of Algorithmics Workshop, FAW 2014

Y2 - 28 June 2014 through 30 June 2014

ER -