File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: On the Complexity of Constrained Sequences Alignment Problems

TitleOn the Complexity of Constrained Sequences Alignment Problems
Authors
Issue Date2014
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 8th International Frontiers of Algorithmics Workshop (FAW 2014), Zhangjiajie, China, 28-30 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 309-319 How to Cite?
AbstractWe 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.
DescriptionLecture Notes in Computer Science, vol. 8497 entitled: Frontiers in algorithmics : 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014: proceedings
Persistent Identifierhttp://hdl.handle.net/10722/205525
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_US
dc.contributor.authorChan, Jen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorYe, Den_US
dc.contributor.authorZhang, Fen_US
dc.contributor.authorShi, JYen_US
dc.date.accessioned2014-09-20T03:33:27Z-
dc.date.available2014-09-20T03:33:27Z-
dc.date.issued2014en_US
dc.identifier.citationThe 8th International Frontiers of Algorithmics Workshop (FAW 2014), Zhangjiajie, China, 28-30 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 309-319en_US
dc.identifier.isbn9783319080154-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/205525-
dc.descriptionLecture Notes in Computer Science, vol. 8497 entitled: Frontiers in algorithmics : 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014: proceedings-
dc.description.abstractWe 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.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleOn the Complexity of Constrained Sequences Alignment Problemsen_US
dc.typeConference_Paperen_US
dc.identifier.emailZhang, Y: yongzh@hku.hken_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.identifier.doi10.1007/978-3-319-08016-1_28-
dc.identifier.scopuseid_2-s2.0-84903603807-
dc.identifier.hkuros237899en_US
dc.identifier.volume8497-
dc.identifier.spage309-
dc.identifier.epage319-
dc.publisher.placeGermany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats