Name
Title | ||
|---|---|---|
Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats |
Abstract | ||
|---|---|---|
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics
86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block
is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n
5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n
11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block
is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00453-008-9209-8 | Algorithmica |
Keywords | Field | DocType |
Tandem repeats,Duplication models,Approximation algorithms | Tandem repeat,Approximation algorithm,Discrete mathematics,Combinatorics,Gene duplication,Mathematics | Journal |
Volume | Issue | ISSN |
54 | 4 | 0178-4617 |
Citations | PageRank | References |
1 | 0.37 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhi-Zhong Chen | 1 | 51 | 5.23 |
| Lusheng Wang | 2 | 2433 | 224.97 |
| Zhanyong Wang | 3 | 50 | 7.04 |