On the complexity of constrained sequences alignment problems

Yong Zhang; Joseph Wun Tat Chan; Francis Y.L. Chin; Hing Fung Ting; Deshi Ye; Feng Zhang; Jianyu Shi

doi:10.1007/978-3-319-08016-1_28

On the complexity of constrained sequences alignment problems

Yong Zhang, Joseph Wun Tat Chan, Francis Y.L. Chin, Hing Fung Ting, Deshi Ye, Feng Zhang, Jianyu Shi

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

1 Citation (Scopus)

Abstract

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 ²,(t - k)n ²}) 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.

Original language	English
Title of host publication	Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
Publisher	Springer Verlag
Pages	309-319
Number of pages	11
ISBN (Print)	9783319080154
DOIs	https://doi.org/10.1007/978-3-319-08016-1_28
Publication status	Published - 2014
Event	8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China Duration: 28 Jun 2014 → 30 Jun 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8497 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Frontiers of Algorithmics Workshop, FAW 2014
Country/Territory	China
City	Zhangjiajie
Period	28/06/14 → 30/06/14

Scopus Subject Areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Zhang, Y., Chan, J. W. T., Chin, F. Y. L., Ting, H. F., Ye, D., Zhang, F., & Shi, J. (2014). On the complexity of constrained sequences alignment problems. In Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings (pp. 309-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8497 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08016-1_28

Zhang, Yong ; Chan, Joseph Wun Tat ; Chin, Francis Y.L. et al. / On the complexity of constrained sequences alignment problems. Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Springer Verlag, 2014. pp. 309-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2bdabe42db4b4f7e92f76da193a03d09,

title = "On the complexity of constrained sequences alignment problems",

abstract = "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.",

author = "Yong Zhang and Chan, {Joseph Wun Tat} and Chin, {Francis Y.L.} and Ting, {Hing Fung} and Deshi Ye and Feng Zhang and Jianyu Shi",

year = "2014",

doi = "10.1007/978-3-319-08016-1_28",

language = "English",

isbn = "9783319080154",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "309--319",

booktitle = "Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings",

address = "Germany",

}

Zhang, Y, Chan, JWT, Chin, FYL, Ting, HF, Ye, D, Zhang, F & Shi, J 2014, On the complexity of constrained sequences alignment problems. in Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8497 LNCS, Springer Verlag, pp. 309-319, 8th International Frontiers of Algorithmics Workshop, FAW 2014, Zhangjiajie, China, 28/06/14. https://doi.org/10.1007/978-3-319-08016-1_28

On the complexity of constrained sequences alignment problems. / Zhang, Yong; Chan, Joseph Wun Tat; Chin, Francis Y.L. et al.
Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Springer Verlag, 2014. p. 309-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8497 LNCS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - On the complexity of constrained sequences alignment problems

AU - Zhang, Yong

AU - Chan, Joseph Wun Tat

AU - Chin, Francis Y.L.

AU - Ting, Hing Fung

AU - Ye, Deshi

AU - Zhang, Feng

AU - Shi, Jianyu

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 proceeding

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 -

Zhang Y, Chan JWT, Chin FYL, Ting HF, Ye D, Zhang F et al. On the complexity of constrained sequences alignment problems. In Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Springer Verlag. 2014. p. 309-319. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08016-1_28

On the complexity of constrained sequences alignment problems

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this