File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Time and space efficient algorithms for constrained sequence alignment

TitleTime and space efficient algorithms for constrained sequence alignment
Authors
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, 22-24 July 2004. In Lecture Notes In Computer Science, 2005, v. 3317, p. 237-246 How to Cite?
AbstractIn this paper, we study the constrained sequence alignment problem, which is a generalization of the classical sequence alignment problem with the additional constraint that some characters in the alignment must be positioned at the same columns. The problem finds important applications in Bioinformatics. Our major result is an O(ℓn2)-time and O(ℓn)-space algorithm for constructing an optimal constrained alignment of two sequences where n is the length of the longer sequence and ℓ is the length of the constraint. Our algorithm matches the best known time complexity and reduces the best known space complexity by a factor of n for solving the problem. We also apply our technique to design time and space efficient heuristic and approximation algorithm for aligning multiple sequences. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/93048
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorPeng, ZSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:49:19Z-
dc.date.available2010-09-25T14:49:19Z-
dc.date.issued2005en_HK
dc.identifier.citationThe 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, 22-24 July 2004. In Lecture Notes In Computer Science, 2005, v. 3317, p. 237-246en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93048-
dc.description.abstractIn this paper, we study the constrained sequence alignment problem, which is a generalization of the classical sequence alignment problem with the additional constraint that some characters in the alignment must be positioned at the same columns. The problem finds important applications in Bioinformatics. Our major result is an O(ℓn2)-time and O(ℓn)-space algorithm for constructing an optimal constrained alignment of two sequences where n is the length of the longer sequence and ℓ is the length of the constraint. Our algorithm matches the best known time complexity and reduces the best known space complexity by a factor of n for solving the problem. We also apply our technique to design time and space efficient heuristic and approximation algorithm for aligning multiple sequences. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.titleTime and space efficient algorithms for constrained sequence alignmenten_HK
dc.typeConference_Paperen_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-23944466035en_HK
dc.identifier.hkuros92462en_HK
dc.identifier.hkuros109464-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-23944466035&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3317en_HK
dc.identifier.spage237en_HK
dc.identifier.epage246en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridPeng, ZS=8853602300en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.customcontrol.immutablesml 160111 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats