Please use this identifier to cite or link to this item:
|Title:||On all-substrings alignment problems|
|Citation:||Fu, 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.|
|Abstract:||Consider 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.|
|Source Title:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 16, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.