Full metadata record
DC FieldValueLanguage
dc.contributor.authorChung, Yun-Shengen_US
dc.contributor.authorLu, Chin Lungen_US
dc.contributor.authorTang, Chuan Yien_US
dc.date.accessioned2014-12-08T15:05:33Z-
dc.date.available2014-12-08T15:05:33Z-
dc.date.issued2007-09-15en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.ipl.2007.04.007en_US
dc.identifier.urihttp://hdl.handle.net/11536/4085-
dc.description.abstractImposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expressions. In an alignment of protein sequences it is natural to expect that functional motifs should be aligned together. Due to this motivation, Arslan introduced the regular expression constrained sequence alignment problem and proposed an algorithm which, if implemented naively, can take time and space up to O(vertical bar Sigma vertical bar V-2 vertical bar vertical bar(4)n(2)) and O(vertical bar Sigma vertical bar(2)vertical bar V vertical bar(4)n), respectively, where Sigma is the alphabet, n is the sequence length, and V is the set of states in an automaton equivalent to the input regular expression. In this paper we propose a more efficient algorithm solving this problem which takes O(vertical bar V vertical bar(3)n(2)) time and O(vertical bar V vertical bar(2n)) space in the worst case. If vertical bar V vertical bar = O(log n) we propose another algorithm with time complexity O(vertical bar V vertical bar(2)log vertical bar V vertical bar n(2)). The time complexity of our algorithms is independent of Sigma, which is desirable in protein applications where the formulation of this problem originates; a factor of vertical bar Sigma vertical bar(2) = 400 in the time complexity of the previously proposed algorithm would significantly affect the efficiency in practice. (c) 2007 Elsevier B.V All rights reserved.en_US
dc.language.isoen_USen_US
dc.subjectconstrained sequence alignmenten_US
dc.subjectalgorithmsen_US
dc.subjectregular expressionen_US
dc.subjectdynamic programmingen_US
dc.titleEfficient algorithms for regular expression constrained sequence alignmenten_US
dc.typeArticle; Proceedings Paperen_US
dc.identifier.doi10.1016/j.ipl.2007.04.007en_US
dc.identifier.journalINFORMATION PROCESSING LETTERSen_US
dc.citation.volume103en_US
dc.citation.issue6en_US
dc.citation.spage240en_US
dc.citation.epage246en_US
dc.contributor.department生物科技學系zh_TW
dc.contributor.departmentDepartment of Biological Science and Technologyen_US
dc.identifier.wosnumberWOS:000248490700006-
Appears in Collections:Conferences Paper


Files in This Item:

  1. 000248490700006.pdf