Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/39595
Title: | On all-substrings alignment problems | Authors: | Fu, W. Hon, W.-K. Sung, W.-K. |
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.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.