On the complexity of constrained sequences alignment problems

Yong Zhang, Joseph W T CHAN, Francis Y.L. Chin, Hing Fung Ting, Deshi Ye, Feng Zhang, Jianyu Shi

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
PublisherSpringer Verlag
Pages309-319
Number of pages11
ISBN (Print)9783319080154
DOIs
Publication statusPublished - 2014
Event8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China
Duration: 28 Jun 201430 Jun 2014

Publication series

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

Conference

Conference8th International Frontiers of Algorithmics Workshop, FAW 2014
Country/TerritoryChina
CityZhangjiajie
Period28/06/1430/06/14

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On the complexity of constrained sequences alignment problems'. Together they form a unique fingerprint.

Cite this