File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.ipl.2004.02.008
- Scopus: eid_2-s2.0-1842736946
- WOS: WOS:000221008500003
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A simple algorithm for the constrained sequence problems
Title | A simple algorithm for the constrained sequence problems |
---|---|
Authors | |
Keywords | Algorithms Constrained longest common subsequence Dynamic programming Sequence alignment |
Issue Date | 2004 |
Publisher | Elsevier 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/88930 |
ISSN | 2015 Impact Factor: 0.605 2015 SCImago Journal Rankings: 0.698 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | De Santis, A | en_HK |
dc.contributor.author | Ferrara, AL | en_HK |
dc.contributor.author | Ho, NL | en_HK |
dc.contributor.author | Kim, SK | en_HK |
dc.date.accessioned | 2010-09-06T09:50:16Z | - |
dc.date.available | 2010-09-06T09:50:16Z | - |
dc.date.issued | 2004 | en_HK |
dc.identifier.citation | Information Processing Letters, 2004, v. 90 n. 4, p. 175-179 | en_HK |
dc.identifier.issn | 0020-0190 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88930 | - |
dc.description.abstract | In 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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl | en_HK |
dc.relation.ispartof | Information Processing Letters | en_HK |
dc.rights | Information Processing Letters. Copyright © Elsevier BV. | en_HK |
dc.subject | Algorithms | en_HK |
dc.subject | Constrained longest common subsequence | en_HK |
dc.subject | Dynamic programming | en_HK |
dc.subject | Sequence alignment | en_HK |
dc.title | A simple algorithm for the constrained sequence problems | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Problems | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.ipl.2004.02.008 | en_HK |
dc.identifier.scopus | eid_2-s2.0-1842736946 | en_HK |
dc.identifier.hkuros | 91365 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-1842736946&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 90 | en_HK |
dc.identifier.issue | 4 | en_HK |
dc.identifier.spage | 175 | en_HK |
dc.identifier.epage | 179 | en_HK |
dc.identifier.isi | WOS:000221008500003 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | De Santis, A=7101704104 | en_HK |
dc.identifier.scopusauthorid | Ferrara, AL=8379365500 | en_HK |
dc.identifier.scopusauthorid | Ho, NL=7102776259 | en_HK |
dc.identifier.scopusauthorid | Kim, SK=8093343800 | en_HK |