Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/39595
DC FieldValue
dc.titleOn all-substrings alignment problems
dc.contributor.authorFu, W.
dc.contributor.authorHon, W.-K.
dc.contributor.authorSung, W.-K.
dc.date.accessioned2013-07-04T07:45:10Z
dc.date.available2013-07-04T07:45:10Z
dc.date.issued2003
dc.identifier.citationFu, W.,Hon, W.-K.,Sung, W.-K. (2003). On all-substrings alignment problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2697 : 80-89. ScholarBank@NUS Repository.
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39595
dc.description.abstractConsider two strings A and B of lengths n and m respectively, with n ≪ m. The problem of computing global and local alignments between A and all m2 substrings of B can be solved by the classical Needleman-Wunsch and Smith-Waterman algorithms, respectively, which takes O(m2n) time and O(m2) space. This paper proposes faster algorithms that take O(mn2) time and O(mn) space. The improvement stems from a compact way to represent all the alignment scores. © Springer-Verlag Berlin Heidelberg 2003.
dc.sourceScopus
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume2697
dc.description.page80-89
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

85
checked on Sep 9, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.