File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A simple algorithm for the constrained sequence problems

TitleA simple algorithm for the constrained sequence problems
Authors
KeywordsAlgorithms
Constrained longest common subsequence
Dynamic programming
Sequence alignment
Issue Date2004
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2004, v. 90 n. 4, p. 175-179 How to Cite?
AbstractIn this paper we address the constrained longest common subsequence problem. Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is the longest subsequence of X and Y such that P is a subsequence of Z. Recently, Tsai [Inform. Process. Lett. 88 (2003) 173-176] proposed an O(n 2·m2·r) time algorithm to solve this problem using dynamic programming technique, where n, m and r are the lengths of X, Y and P, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in O(n·m·r) time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved with the same time complexity. © 2004 Published by Elsevier B.V.
Persistent Identifierhttp://hdl.handle.net/10722/88930
ISSN
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorDe Santis, Aen_HK
dc.contributor.authorFerrara, ALen_HK
dc.contributor.authorHo, NLen_HK
dc.contributor.authorKim, SKen_HK
dc.date.accessioned2010-09-06T09:50:16Z-
dc.date.available2010-09-06T09:50:16Z-
dc.date.issued2004en_HK
dc.identifier.citationInformation Processing Letters, 2004, v. 90 n. 4, p. 175-179en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88930-
dc.description.abstractIn this paper we address the constrained longest common subsequence problem. Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is the longest subsequence of X and Y such that P is a subsequence of Z. Recently, Tsai [Inform. Process. Lett. 88 (2003) 173-176] proposed an O(n 2·m2·r) time algorithm to solve this problem using dynamic programming technique, where n, m and r are the lengths of X, Y and P, respectively. In this paper, we present a simple algorithm to solve the constrained longest common subsequence problem in O(n·m·r) time and show that the constrained longest common subsequence problem is equivalent to a special case of the constrained multiple sequence alignment problem which can also be solved with the same time complexity. © 2004 Published by Elsevier B.V.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.en_HK
dc.subjectAlgorithmsen_HK
dc.subjectConstrained longest common subsequenceen_HK
dc.subjectDynamic programmingen_HK
dc.subjectSequence alignmenten_HK
dc.titleA simple algorithm for the constrained sequence problemsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=90&issue=4&spage=175&epage=179&date=2004&atitle=A+Simple+Algorithm+for+the+Constrained+Sequence+Problemsen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.ipl.2004.02.008en_HK
dc.identifier.scopuseid_2-s2.0-1842736946en_HK
dc.identifier.hkuros91365en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-1842736946&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume90en_HK
dc.identifier.issue4en_HK
dc.identifier.spage175en_HK
dc.identifier.epage179en_HK
dc.identifier.isiWOS:000221008500003-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridDe Santis, A=7101704104en_HK
dc.identifier.scopusauthoridFerrara, AL=8379365500en_HK
dc.identifier.scopusauthoridHo, NL=7102776259en_HK
dc.identifier.scopusauthoridKim, SK=8093343800en_HK
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats