Improved approximation algorithms for reconstructing the history of tandem repeats
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 | 4685890 |
Pages (from-to) | 438-453 |
Journal / Publication | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
Volume | 6 |
Issue number | 3 |
Publication status | Published - Jul 2009 |
Link(s)
Abstract
Abstract Some genetic diseases in human beings are dominated by short sequences repeated consecutively called tandem repeats. Once a region containing tandem repeats is found, it is of great interest to study the history of creating the repeats. The computational problem of reconstructing the duplication history of tandem repeats has been studied extensively in the literature. Almost all previous studies focused on the simplest case where the size of each duplication block is 1. Only recently we succeeded in giving the first polynomial-time approximation algorithm with a guaranteed ratio for a more general case where the size of each duplication block is at most 2; the algorithm achieves a ratio of 6 and runs in O(n11) time. In this paper, we present two new polynomial-time approximation algorithms for this more general case. One of them achieves a ratio of 5 and runs in O(n9) time, while the other achieves a ratio of 2.5 + ε for any constant ε 0 but runs slower. © 2009 IEEE.
Research Area(s)
- Approximation algorithms, Computational biology
Citation Format(s)
Improved approximation algorithms for reconstructing the history of tandem repeats. / Chen, Zhi-Zhong; Wang, Lusheng.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 6, No. 3, 4685890, 07.2009, p. 438-453.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 6, No. 3, 4685890, 07.2009, p. 438-453.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review