Please use this identifier to cite or link to this item:
|Title:||On all-substrings alignment problems||Authors:||Fu, W.
|Issue Date:||2003||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)||URI:||http://scholarbank.nus.edu.sg/handle/10635/39595||ISSN:||03029743|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Apr 19, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.