Fast exact algorithms for the closest string and substring problems with application to the planted (L,d)-motif model
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Article number | 5708134 |
Pages (from-to) | 1400-1410 |
Journal / Publication | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
Volume | 8 |
Issue number | 5 |
Publication status | Published - 2011 |
Link(s)
Abstract
We present two parameterized algorithms for the closest string problem. The first runs in O(nL + nd · 17.97 d) time for DNA strings and in O(nL + nd · 61.86 d) time for protein strings, where n is the number of input strings, L is the length of each input string, and d is the given upper bound on the number of mismatches between the center string and each input string. The second runs in O(nL + nd · 13.92 d) time for DNA strings and in O(nL + nd · 47.21 d) time for protein strings. We then extend the first algorithm to a new parameterized algorithm for the closest substring problem that runs in O((n-1)m 2(L + d · 17.97 d · m ⌊log2(d+1)⌋)) time for DNA strings and in O((n-1)m 2(L + d · 61.86 d · m ⌊log2(d+1)⌋)) time for protein strings, where n is the number of input strings, L is the length of the center substring, L - 1 + m is the maximum length of a single input string, and d is the given upper bound on the number of mismatches between the center substring and at least one substring of each input string. All the algorithms significantly improve the previous bests. To verify experimentally the theoretical improvements in the time complexity, we implement our algorithm in C and apply the resulting program to the planted (L, d)-motif problem proposed by Pevzner and Sze in 2000. We compare our program with the previously best exact program for the problem, namely PMSPrune (designed by Davila et al. in 2007). Our experimental data show that our program runs faster for practical cases and also for several challenging cases. Our algorithm uses less memory too. © 2006 IEEE.
Research Area(s)
- closest string, closest substring, DNA motif discovery, Parameterized algorithm
Citation Format(s)
Fast exact algorithms for the closest string and substring problems with application to the planted (L,d)-motif model. / Chen, Zhi-Zhong; Wang, Lusheng.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 8, No. 5, 5708134, 2011, p. 1400-1410.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 8, No. 5, 5708134, 2011, p. 1400-1410.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review